Cần giúp đỡ về thuật toán để tìm ra con đường tối đa trong một DAG

Question

Giả sử tôi đã Directed Acyclic Graph (DAG) này, nơi có một lợi thế cạnh đạo từ mỗi nút (trừ các nút ở hàng dưới) để hai nút dưới nó:

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

Tôi cần tìm một đường dẫn qua DAG này, nơi tổng trọng số của các nút được phóng to. Bạn chỉ có thể di chuyển theo đường chéo từ trái sang phải hoặc xuống dưới từ một nút trong cây này. Vì vậy, ví dụ, 7, 3, 8, 7, 5, sẽ cung cấp đường dẫn tối đa trong cây này.

Các tập tin đầu vào chứa DAG được định dạng theo cách này

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

Câu hỏi của tôi là, những gì thuật toán sẽ là tốt nhất để tìm con đường tối đa và cũng như thế nào cây này sẽ được đại diện trong C++?

Trọng số nút không âm.

Answer 1

Tôi đại diện cho tam giác này với vec tơ vectơ là int s.

Bắt đầu ở hàng dưới cùng và so sánh từng cặp số được điều chỉnh. Lấy cái lớn hơn và thêm nó vào số phía trên cặp:

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

Làm việc theo cách của bạn lên trên đầu và khi bạn hoàn thành, đầu tam giác sẽ chứa tổng lớn nhất.

Answer 2

thuật toán tốt nhất là nên

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. 

Thuật toán tốt nhất cho đại diện các cây sẽ không có gì. Vì bạn không thực sự làm bất cứ điều gì cần một respresentaiton cây.

Answer 3

Mảng hai chiều sẽ hoạt động tốt. Bạn có thể tiếp cận điều này bằng cách sử dụng chiều ngang đầu tiên trên bề rộng và đánh dấu từng nút được truy cập với tổng số đường dẫn tối đa cho nút đó.

Ví dụ:

• 7 chỉ có thể đạt được bằng cách bắt đầu tại 7.
• 3 được đánh dấu bằng 10, 8 được đánh dấu bằng 15.
• 8 được đánh dấu bằng 18 (10 + 8), 1 được đánh dấu bằng 11, sau đó được thay bằng 16 và 0 được đánh dấu bằng 15.

Khi các nút lá được đánh dấu, hãy chạy nhanh qua chúng để xem giá trị nào là cực đại. Sau đó, bạn bắt đầu backtracking bằng cách so sánh trọng lượng của nút hiện tại, trọng lượng của các nút cha và trọng lượng cạnh.

Answer 4

Spoilers

Nếu bạn muốn giải quyết vấn đề này cho mình, đừng đọc mã.

---

Một cách để bạn có thể giải quyết nó là để biến dữ liệu vào một cây (đồ thị thực) và viết một thuật toán đệ quy sẽ tìm ra con đường tối đa qua cây bằng cách giảm cây vào subtrees nhỏ hơn (cho đến khi bạn có một cây chỉ với một nút) và bắt đầu đi lên từ đó.

Tôi thực sự thích các thuật toán đệ quy và làm việc với cây, vì vậy tôi đã đi trước và đã viết một chương trình để làm điều đó:

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

Nó in

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

con đường bổ sung lên đến 30