TA貢獻1824條經驗 獲得超6個贊
我已經實現了一個版本，它基本上找到了從一個節點到另一個節點的所有可能路徑，但它沒有計算任何可能的“周期”（我正在使用的圖形是循環的）。所以基本上，沒有一個節點會在同一路徑中出現兩次。如果圖是非周期性的，那么我想你可以說它似乎找到了兩個節點之間的所有可能路徑。它似乎工作得很好，并且對于我的圖形大小~150，它幾乎立即在我的機器上運行，雖然我確定運行時間必須是指數的，所以它會開始變得很慢，因為圖變大了。
這是一些Java代碼，演示了我實現的內容。我確信必須有更高效或更優雅的方式來做到這一點。
Stack connectionPath = new Stack();List<Stack> connectionPaths = new ArrayList<>();// Push to connectionsPath the object that would be passed as the parameter 'node' into the method belowvoid findAllPaths(Object node, Object targetNode) {
for (Object nextNode : nextNodes(node)) {
if (nextNode.equals(targetNode)) {
Stack temp = new Stack();
for (Object node1 : connectionPath)
temp.add(node1);
connectionPaths.add(temp);
} else if (!connectionPath.contains(nextNode)) {
connectionPath.push(nextNode);
findAllPaths(nextNode, targetNode);
connectionPath.pop();
}
}}
TA貢獻1845條經驗 獲得超8個贊
我會給你一個（有點?。┑陌姹荆ūM管可以理解，但我認為）是一個科學的證明，你不能在可行的時間內做到這一點。
我要證明的是，在任意圖中枚舉兩個選定節點和不同節點（例如s和t）之間的所有簡單路徑的時間復雜度G不是多項式的。請注意，由于我們只關心這些節點之間的路徑數量，因此邊緣成本并不重要。
當然，如果圖表具有一些選擇良好的屬性，這可能很容易。我考慮的是一般情況。
假設我們有一個多項式算法，列出s和之間的所有簡單路徑t。
如果G已連接，則列表為非空。如果G不是和s并且t在不同的組件中，列出它們之間的所有路徑真的很容易，因為沒有！如果它們在同一個組件中，我們可以假裝整個圖形僅包含該組件。所以我們假設G確實是連通的。
所列出的路徑數必須是多項式的，否則算法不能全部返回。如果它列舉了所有這些，它必須給我最長的一個，所以它就在那里。擁有路徑列表，可以應用一個簡單的過程指向我這是最長的路徑。
我們可以證明（盡管我不能想出一種有說服力的方式來表達它），這條最長的路徑必須遍歷所有的頂點G。因此，我們剛剛找到了一個帶有多項式過程的哈密頓路徑！但這是一個眾所周知的NP難題。
然后我們可以得出結論，我們認為我們所擁有的這種多項式算法不太可能存在，除非P = NP。
舉報