計算在具有多個輸入圖形和一個輸出的所有路徑

Question

我要計算的一個輸出在從多個輸入（X1，...，XN）向無環圖的所有路徑。圖形具有相同的深度d和輸入同時到達圖形（形狀類似於具有許多輸入和一個輸出的人工神經網絡）。你能告訴我是否有一些算法可以計算這樣的路徑嗎？

問候，

Answer 1

1）運行的深度優先搜索，從輸出開始和在相反的方向遍歷每個邊緣，以找到從中可以得到對輸出的所有節點。

2）刪除從你不能到輸出的所有節點。

3）運行所述經修改的圖表遞歸搜索開始，依次每個輸入節點，以找到輸出的所有路徑。

因爲您已經刪除了所有死角，所以應該儘可能快地生成所有路徑，但應該警告您可能會有大量不同的路徑，即使是從小圖上 - 一個繪製梯子的形狀和長度n可能有大約2^n個路徑 - 在每個梯級中，您可以選擇是在梯子的左側還是右側，因此有2 ^（梯級的數量）不同的路徑。