TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超9個(gè)贊
找到所有可能的路徑是一個(gè)難題，因?yàn)榇嬖谥笖?shù)的簡(jiǎn)單路徑。即使找到第k個(gè)最短路徑[或最長(zhǎng)路徑]也是NP-Hard。
一個(gè)可能的解決方案，從找到的所有路徑[或所有路徑達(dá)到一定長(zhǎng)度] s來t為BFS，沒有保持visited一套，或加權(quán)版本-你可能想使用統(tǒng)一的搜索成本
注意，同樣在具有周期每圖表[它不是一個(gè)DAG ]可能存在的路徑之間無限多s到t。
TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超6個(gè)贊
我已經(jīng)實(shí)現(xiàn)了一個(gè)版本，它基本上找到了從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的所有可能路徑，但它沒有計(jì)算任何可能的“周期”（我正在使用的圖形是循環(huán)的）。所以基本上，沒有一個(gè)節(jié)點(diǎn)會(huì)在同一路徑中出現(xiàn)兩次。如果圖是非周期性的，那么我想你可以說它似乎找到了兩個(gè)節(jié)點(diǎn)之間的所有可能路徑。它似乎工作得很好，并且對(duì)于我的圖形大小~150，它幾乎立即在我的機(jī)器上運(yùn)行，雖然我確定運(yùn)行時(shí)間必須是指數(shù)的，所以它會(huì)開始變得很慢，因?yàn)閳D變大了。
這是一些Java代碼，演示了我實(shí)現(xiàn)的內(nèi)容。我確信必須有更高效或更優(yōu)雅的方式來做到這一點(diǎn)。
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貢獻(xiàn)1845條經(jīng)驗(yàn) 獲得超8個(gè)贊
我會(huì)給你一個(gè)（有點(diǎn)小）的版本（盡管可以理解，但我認(rèn)為）是一個(gè)科學(xué)的證明，你不能在可行的時(shí)間內(nèi)做到這一點(diǎn)。
我要證明的是，在任意圖中枚舉兩個(gè)選定節(jié)點(diǎn)和不同節(jié)點(diǎn)（例如s和t）之間的所有簡(jiǎn)單路徑的時(shí)間復(fù)雜度G不是多項(xiàng)式的。請(qǐng)注意，由于我們只關(guān)心這些節(jié)點(diǎn)之間的路徑數(shù)量，因此邊緣成本并不重要。
當(dāng)然，如果圖表具有一些選擇良好的屬性，這可能很容易。我考慮的是一般情況。
假設(shè)我們有一個(gè)多項(xiàng)式算法，列出s和之間的所有簡(jiǎn)單路徑t。
如果G已連接，則列表為非空。如果G不是和s并且t在不同的組件中，列出它們之間的所有路徑真的很容易，因?yàn)闆]有！如果它們?cè)谕粋€(gè)組件中，我們可以假裝整個(gè)圖形僅包含該組件。所以我們假設(shè)G確實(shí)是連通的。
所列出的路徑數(shù)必須是多項(xiàng)式的，否則算法不能全部返回。如果它列舉了所有這些，它必須給我最長(zhǎng)的一個(gè)，所以它就在那里。擁有路徑列表，可以應(yīng)用一個(gè)簡(jiǎn)單的過程指向我這是最長(zhǎng)的路徑。
我們可以證明（盡管我不能想出一種有說服力的方式來表達(dá)它），這條最長(zhǎng)的路徑必須遍歷所有的頂點(diǎn)G。因此，我們剛剛找到了一個(gè)帶有多項(xiàng)式過程的哈密頓路徑！但這是一個(gè)眾所周知的NP難題。
然后我們可以得出結(jié)論，我們認(rèn)為我們所擁有的這種多項(xiàng)式算法不太可能存在，除非P = NP。
舉報(bào)