potrzebują pomocy w algorytm, aby znaleźć maksymalną ścieżkę DAG

Question

Załóżmy, że miał ten Directed Acyclic Graph (DAG), gdzie jest skierowany krawędziowych od każdego węzła (inne niż węzły w dolnym rzędzie), na dwóch węzłów pod nim:

 7 
     3 8 
    8 1 0 
    2 7 4 4 
4 5 2 6 5 

Potrzebuję znaleźć ścieżkę przez ten DAG, gdzie suma wag węzłów jest zmaksymalizowana. Możesz poruszać się tylko po przekątnej w dół - w lewo lub w dół - w prawo od węzła w tym drzewie. Na przykład 7, 3, 8, 7, 5 dałoby maksymalną ścieżkę w tym drzewie.

Plik wejściowy zawiera DAG sformatowany w ten sposób

7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5 

Moje pytanie brzmi, co algorytm byłoby najlepiej, aby znaleźć maksymalną ścieżkę, a także w jaki sposób to drzewo jest reprezentowana w C++?

Wagi węzłów są nieujemne.

Answer 1

Chciałbym reprezentować ten trójkąt z wektora wektorów int s.

Rozpocznij w dolnym wierszu i porównaj każdą dopasowaną parę liczb. Weź większy i dodać je do ilości powyżej pary:

5 3    13 3 
    \ 
7 8 6 becomes 7 8 6 
^^

        13 3    13 11 
        /
Next iteration 7 8 6 becomes 7 8 6 etc. 
        ^^ 

Swój sposób pracy do góry, a kiedy skończysz, wierzchołek trójkąta będzie zawierała największą sumę.

Answer 2

najlepszy algorytm byłoby

open the file, 
set a counter to 0. 
read each line in the file. 
for every line you read, 
    increment the counter. 
close the file. 
that counter is your answer. 

Najlepszy algorytm do reprezentowania drzewo byłoby nic. Ponieważ tak naprawdę nie robisz niczego, co wymaga respresentaiton drzewa.

Answer 3

Tablica dwuwymiarowa działałaby dobrze. Możesz podejść do tego, wykorzystując szerokość pierwszego przejścia i oznaczając każdy odwiedzany węzeł maksymalną sumą ścieżek dla tego węzła.

Na przykład:

• 7 może być osiągnięte jedynie przez zaczynając 7.
• 3 jest oznaczony 10, 8 jest oznaczona 15.
• 8 jest oznaczony 18 (10 + 8), 1 jest oznaczony jako 11, a następnie zastąpiony przez 16, a 0 jest oznaczony jako 15.

Po zaznaczeniu węzłów liści należy je szybko przejrzeć, aby zobaczyć, który z nich jest maksymalny. Następnie rozpoczyna się wycofywanie, porównując wagę bieżącego węzła, wagę węzłów nadrzędnych i wagę krawędzi.

Answer 4

Spoilery

Jeśli chciał rozwiązać ten problem, nie należy odczytać kodu.

---

Jeden sposób można go rozwiązać jest włączenie danych do drzewa (wykres faktycznie) i napisać rekurencyjny algorytm, który będzie znaleźć maksymalną drogę przez drzewa poprzez zmniejszenie drzewa na mniejsze poddrzew (do ciebie mieć drzewo z tylko jednym węzłem) i zaczynać od tego miejsca.

bardzo podoba mi algorytmów rekurencyjnych i pracy z drzew, więc poszedł do przodu i napisał program, aby to zrobić:

#include <algorithm> 
#include <iostream> 
#include <vector> 
#include <iterator> 

using namespace std; 

struct node { 
    node(int i, node* left = NULL, node* right = NULL) : data(i), left(left), right(right) { } 

    node* left, *right; 
    int data; 
}; 

/* 
     tree: 

     7 
     3 8 
    8 1 0 
    2 7 4 4 
4 5 2 6 5 

*/ 

std::vector<node*> maxpath(node* tree, int& sum) { 
    if (!tree) { 
     sum = -1; 
     return std::vector<node*>(); 
    } 

    std::vector<node*> path; 

    path.push_back(tree); 

    if (!tree->left && !tree->right) { 
     sum = tree->data; 
     return path; 
    } 

    int leftsum = 0, rightsum = 0; 

    auto leftpath = maxpath(tree->left, leftsum); 
    auto rightpath = maxpath(tree->right, rightsum); 

    if (leftsum != -1 && leftsum > rightsum) { 
     sum = leftsum + tree->data; 
     copy(begin(leftpath), end(leftpath), back_inserter<vector<node*>>(path)); 
     return path; 
    } 

    sum = rightsum + tree->data; 
    copy(begin(rightpath), end(rightpath), back_inserter<vector<node*>>(path)); 
    return path; 
} 

int main() 
{ 
    // create the binary tree 
    // yay for binary trees on the stack 
    node b5[] = { node(4), node(5), node(2), node(6), node(5) }; 
    node b4[] = { node(2, &b5[0], &b5[1]), node(7, &b5[1], &b5[2]), node(4, &b5[2], &b5[3]), node(4, &b5[3], &b5[4]) }; 
    node b3[] = { node(8, &b4[0], &b4[1]), node(1, &b4[1], &b4[2]), node(0, &b4[2], &b4[3]) }; 
    node b2[] = { node(3, &b3[0], &b3[1]), node(8, &b3[1], &b3[2]) }; 

    node n(7, &b2[0], &b2[1]); 

    int sum = 0; 

    auto mpath = maxpath(&n, sum); 

    for (int i = 0; i < mpath.size(); ++i) { 
     cout << mpath[i]->data; 

     if (i != mpath.size() - 1) 
      cout << " -> "; 
    } 

    cout << endl << "path added up to " << sum << endl; 
} 

on wydrukowany

7 -> 3 -> 8 -> 7 -> 5

ścieżka dodana do 30