bisogno di assistenza con algoritmo per trovare il percorso massimo in un DAG

Question

Supponiamo avevo questo Directed Acyclic Graph (DAG), dove c'è un arco orientato da ciascun nodo (diversi dai nodi nella fila inferiore) per i due nodi sottostanti:

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

Ho bisogno di trovare un percorso attraverso questo DAG dove la somma dei pesi dei nodi è massimizzata. È possibile spostare solo diagonalmente in basso a sinistra o in basso a destra da un nodo in questo albero. Quindi, ad esempio, 7, 3, 8, 7, 5, darebbe il percorso massimo in questo albero.

Il file di input contiene il DAG formattato in questo modo

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

La mia domanda è, che cosa l'algoritmo sarebbe meglio per trovare massima del percorso e anche come sarebbe questo albero è rappresentato in C++?

I pesi del nodo sono non negativi.

Answer 1

Rappresenterei questo triangolo con un vettore di vettori di int s.

Inizia nella riga inferiore e confronta ogni coppia di numeri conteggiati. Prendete quello più grande e aggiungerlo al numero sopra la coppia:

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. 
        ^^ 

il tuo lavoro per la parte superiore e quando hai finito, la punta del triangolo conterrà la più grande somma.

Answer 2

il miglior algoritmo sarebbe quella di

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. 

il miglior algoritmo per rappresentare l'albero non sarebbe nulla. Dato che in realtà non stai facendo nulla che richieda un respresentaiton ad albero.

Answer 3

Un array bidimensionale funzionerebbe correttamente. È possibile avvicinarsi a questo utilizzando una larghezza trasversale prima e contrassegnando ogni nodo visitato con la somma massima del percorso per quel nodo.

Ad esempio:

• 7 possono essere raggiunti solo partendo 7.
• 3 è contrassegnato con 10, 8 è contrassegnato con 15.
• 8 è contrassegnato con 18 (10 + 8), 1 è contrassegnato con 11, quindi sostituito con 16 e 0 è contrassegnato con 15.

Quando i nodi foglia sono contrassegnati, eseguire una rapida corsa attraverso di essi per vedere quale è il massimo. Quindi, si avvia il backtracking confrontando il peso del nodo corrente, il peso dei nodi parent e il peso del bordo.

Answer 4

Spoiler

Se si voleva risolvere questo problema da soli, non leggere il codice.

---

Un modo si potrebbe risolverlo è quello di trasformare i dati in un albero (grafico in realtà) e scrivere un algoritmo ricorsivo che troverà il percorso massima attraverso l'albero, riducendo l'albero in sottoalberi più piccoli (fino a avere un albero con un solo nodo) e iniziare a salire da lì.

mi piace molto algoritmi ricorsivi e di lavoro con gli alberi, così sono andato avanti e ho scritto un programma per farlo:

#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; 
} 

E 'stampato

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

percorso aggiunto fino al 30