Thuật toán biểu đồ để tính các giá trị nút dựa trên các nút lân cận

Question

Tôi muốn tạo một thuật toán đồ thị cập nhật/tính giá trị của một nút f(n) như một hàm của mỗi giá trị f(n) của các nút lân cận.

• Biểu đồ được hướng dẫn.
• Mỗi nút có giá trị f (n) ban đầu.
• Mỗi cạnh không có chi phí (0).
• Giá trị của mỗi nút là giá trị tối đa của giá trị hiện tại và giá trị của mỗi nút lân cận (biểu đồ được hướng dẫn, vì vậy hàng xóm là những người từ nơi nút có các cạnh đến).

Nhiều chính thức,

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k. 

tôi có thể hình dung một vài cách để làm như vậy, tuy nhiên tôi không biết những gì mở rộng họ là tối ưu.

Bất cứ ai có thể đưa ra đề xuất và bình luận (cho dù bạn nghĩ rằng đề xuất của bạn là tối ưu) hay đề xuất bất kỳ thuật toán đồ thị tồn tại nào tôi có thể thích ứng?

Answer 1

Claims:

1. Trong mỗi Strongly Connected ComponentV trong biểu đồ, các giá trị của tất cả các đỉnh trong SCC này có điểm số cuối cùng giống nhau.
   "Bằng chứng" (hướng dẫn): bằng cách thực hiện chuyển đổi trong SCC này, bạn có thể lặp lại thiết lập tất cả các điểm số thành giá trị tối đa được tìm thấy trong SCC này.

2. Trong một DAG, giá trị của mỗi đỉnh là max{v,parent(v) | for all parents of v} (định nghĩa) và điểm số có thể được tìm thấy trong một lần lặp từ đầu đến cuối.
   "Bằng chứng" (hướng dẫn): Không có "cạnh sau", vì vậy nếu bạn biết giá trị cuối cùng của tất cả các bậc cha mẹ, bạn biết giá trị cuối cùng của mỗi đỉnh. Bằng cách cảm ứng (cơ sở là tất cả các nguồn) - bạn có thể nhận được thực tế là một lần lặp đơn là đủ để xác định điểm số cuối cùng.

3. Ngoài ra, được biết rằng biểu đồ G' đại diện cho SCC của biểu đồ g là một DAG.

Từ trên chúng ta có thể lấy được một thuật toán đơn giản :

1. fing SCCS tối đa trong các đồ thị (có thể được thực hiện với Tarjan algorithm), và tạo ra các đồ thị SCC. Hãy để nó là G'. Lưu ý rằng G' là một DAG.
2. Đối với mỗi SCC V: đặt f'(V) = max{v | v in V} (theo trực giác - đặt giá trị của mỗi SCC làm giá trị tối đa trong SCC này).
3. Topological sort biểu đồ G'.
4. Thực hiện một lần truyền tải đơn theo kiểu tôpô được tìm thấy trong (3) - và tính f (V) cho mỗi đỉnh trong G' theo cha mẹ của nó.
5. Đặt f(v) = f'(V) (trong đó v là trong SCC V)

phức tạp:

1. Tarjan và tạo G' là O(V+E)
2. Tìm f' cũng là tuyến tính trong kích thước của biểu đồ - O(V+E)
3. Loại cấu trúc liên kết chạy trong O(V+E)
4. Đường truyền đơn lẻ - tuyến tính: O(V+E)
5. Đưa điểm số cuối cùng: tuyến tính!

Vì vậy, các thuật toán trên là tuyến tính trong kích thước của đồ thị-O(V+E)