在具有特定代价的无向图中寻找路径

Question

假设我们有一个无向加权图。我们的任务是查找所有路径，这些路径的起点和终点相同，且总成本等于N。我认为可以使用修改后的Dijkstra算法结合BFS或DFS来完成，但我不知道如何实现这样的事情。感谢任何帮助。

- IlanMosheShimsoni

---

相等，还是最多相等？如果是前者，那么通过归约到哈密顿路径问题，该问题就是NP难的。 - John Dvorak

那么你的问题是NP难问题（NP完全问题甚至更糟），我似乎找不到一个NP解决方案来“计数”路径。 - John Dvorak

请注意，可能有多达(n-2)!个解决方案（完整图，所有边长度相等，需要汉密尔顿路径），因此枚举速度会非常慢。 - John Dvorak

我的目标不是计算路径，而是计算总路径值等于N。 - IlanMosheShimsoni

你想枚举长度为 N 的路径，对吗？可能会有_很多_这样的路径。 - John Dvorak

是的，这是我的目标。（我们的图形最多有30个顶点）谢谢。 - IlanMosheShimsoni

Answer 1

假设您有一个用于创建图形数据结构和遍历它的框架/库，您可以使用回溯深度优先搜索，并在跨越资源限制时进行早期返回。伪代码如下：

void DFS(Vertex current, Vertex goal, List<Vertex> path, int money_left) {
  // oops
  if (money_left < 0) 
     return;

  // avoid cycles
  if (contains(path, current)
     return;

  // got it!
  if (current == goal)) {
     if (money_left == 0)
         print(path);
     return;
  }

  // keep looking
  children = successors(current); // optionally sorted from low to high cost
  for(child: children)          
      DFS(child, add_path(path, child), money_left - cost(child));      
}

你可以这样调用它：DFS(start, goal, List<Vertex>(empty), N)

- TemplateRex

---

除非 money_left == 0，否则您应该只打印。否则看起来不错。 - Patashu

@Patashu 谢谢，已更新。如果没有那个子句，它会找到所有 cost <= N 的路径。 - TemplateRex

如果当前金额不等于0但是current == goal时，仍然应该返回结果，以免在目标之后进行无意义的搜索。 - Patashu

@Patashu 很高兴看到你在你的时区还没有快要睡着了;-) 已更新。 - TemplateRex