一般的想法，也许在图上的例子

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中插入和删除路径的位置。

没有冒犯，但这很简单，你在谈论咨询很多书的答案。我会建议玩简单的例子，直到它们变得更加明显。