一般的想法，也許在圖上的例子

Question

我正在尋找一個大概的想法（也許一些代碼示例或至少是僞代碼） 現在，這是從某人給我的問題，或者更確切地說給我看，不用爲了解決這個問題，但我確實大部分的問題，無論如何，說我遇到的問題是這樣的：

比方說，你有向加權圖與以下節點：

AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 

和問題是： 從C到C有多少個不同的路由，距離小於x。 （比如說10,20,30,40） 不同旅行的答案是：CDC，CEBC，CEBCDC，CDCEBC，CDEBC，CEBCEBC，CEBCEBCEBC。

我遇到的主要問題是，當我做DFS或BFS時，我的實現首先選擇節點並將其標記爲已訪問，因此我只能找到2個CDC和CEBC路徑，然後我的算法退出。如果我沒有將它標記爲訪問，那麼在下一次迭代（或遞歸調用）時，它將選擇相同的節點而不是下一個可用的路由，所以我必須始終將它們標記爲已訪問，但通過這樣做我怎麼能夠CEBCEBCEBC，這在節點之間非常複雜。

我已經看過所有不同的算法書，我在家裏，雖然每個算法都描述瞭如何做DFS，BFS和找到最短路徑（所有好的stufF），但沒有顯示如何無限循環迭代並僅停止當達到某個圖的權重或達到某個頂點次數時。

Answer 1

那麼爲什麼不保持分支和分支;在每個節點你會評估兩件事情;有這個特定的路徑超過了權重限制（如果是這樣，終止分支），並且是我開始的這個節點（在這種情況下將我的路徑歷史記錄到'可接受的解決方案'列表）;然後建立新的分支，每個分支在每個可能的方向上邁出一步。

Answer 2

其實你有兩個不同的問題：

• 查找從C到C中的所有不同的週期，我們會打電話給他們C_1，C_2，...，C_n（與DFS完成）
• 每C_i的權重爲w_i，那麼你需要每個總重量小於N的週期組合。這是一個組合問題（並且似乎可以通過動態編程輕鬆解決）。

Answer 3

您不應將節點標記爲已訪問;作爲MikeB指出，CDCDC是一個有效的解決方案，但是它重溫D.

我會做艾克這樣的：

 
Start with two lists of paths: 
Solutions (empty) and 
ActivePaths (containing one path, "C"). 
While ActivePaths is not empty, 
Take a path out of ActivePaths (suppose it's "CD"[8]). 
If its distance is not over the limit, 
    see where you are by looking at the last node in the path ("D"). 
    If you're at "C", add a copy of this path to Solutions. 
    Now for each possible next destination ("C", "E") 
    make a copy of this path, ("CD"[8]) 
    append the destination, ("CDC"[8]) 
    add the weight, ("CDC"[16]) 
    and put it in ActivePaths 
Discard the path. 

不管這原來是一個DFS，BFS一個或別的東西取決於在ActivePath中插入和刪除路徑的位置。

沒有冒犯，但這很簡單，你在談論諮詢很多書的答案。我會建議玩簡單的例子，直到它們變得更加明顯。