找到多棵樹內的最佳路徑（多層多個節點）

Question

問題是在多層次的多個節點內找到最佳路徑（最低成本/高分）。換句話說，在共享相同節點的多個樹中。

例如如所見in the picture; 每個級別都有幾個節點。這些連接與邊緣（每邊也有距離值，但可能不會使用）。並且每條路徑都有來自邊緣值的分數值。得分是路徑的聯合概率。

所以我們的目標是找到這些層之間的最佳路徑。

數據如下所示; （第一級節點，第2級的節點，第3級的節點...）：得分

（1，1，1）：3

（1,2，1）：1

（ 1，2，2）：6

（1，2，3）：2

（2,2，1）：3

（2，2，2）：4

（2,2，3）：3

（2,3，2）：5

（2,3，3）：4

.....

結果應該給出5條路徑，這些路徑應該總體上最小成本。

這個問題應該用什麼樣的算法？

Answer 1

此問題可以模擬爲minimum cost flow網絡問題。設m爲每層中的節點數量。將人工源s放置在第一層之上; s連接到第一層的每個節點，並且這些m邊緣中的每一個邊緣的網絡容量受到1約束，並且成本爲0。同樣，最後一層下面有一個人造終端t; t連接到最後一層的每個節點，並且這些m邊緣中的每一個的網絡容量受到1約束，並且成本爲0。該問題可以通過確定最低成本流程來解決，其數量爲m，這可以通過network simplex算法來實現。