图的循环游
Circular tour of a graph
给定一个有向图，有N个节点和M个边，你需要找到图的最低成本循环游览，即，从特定城市 X 开始并在同一城市结束。
对于以下两种情况，最有效的方法是什么：
- 边缘没有权重
- 加权边（第i条边为Wi）
- 以上两种情况，但条件是每个城市最多只能访问一次。 （除了第一个城市）。如果这不可能，则输出将为 -1。
提前致谢！
1。边上没有权重。
如果边上没有成本，实际上所有电路都变得相等，所有成本都为 0。
按道理，如果隐含的说cost实际上是最小跳数，那么满足上述条件的任何电路也是等价的。然后，问题是找到一个电路，即Hamiltonian Circuit or Hamiltonian Cycle。找出图中的 哈密顿电路 是 NP 完全的。
有 n! 条可能的路线。蛮力方法的 运行时复杂度为 O(n!)，其中 n 表示边数。
现有的最佳算法之一是 here 中的模拟和代码。
2。加权边（Wi for ith edge）
当图有加权边时，问题就变成众所周知的TSP (Travelling Salesman Problem)，这是一个NP-hard问题。社区中存在围绕 TSP 复杂性的困惑。您必须区分 TSP-Optimize 和 TSP-Decide。
TSP-Optimize 是 NP-hard。
TSP 决策是 NP 完全的。
有关详细说明，请查看这些资源 1 2. You can find a discussion in here。
系统要求您实施 TSP-Optimize。
-动态规划
Bellman–Held–Karp 算法。您可以在 here 中找到伪代码。
运行时复杂度：O(2n n2)，其中 n表示边数。
尽管存在其他解决方案技术，使用分而治之或贪心法，但它们并不是最优的。
给定一个有向图，有N个节点和M个边，你需要找到图的最低成本循环游览，即，从特定城市 X 开始并在同一城市结束。
对于以下两种情况，最有效的方法是什么：
- 边缘没有权重
- 加权边（第i条边为Wi）
- 以上两种情况，但条件是每个城市最多只能访问一次。 （除了第一个城市）。如果这不可能，则输出将为 -1。
提前致谢！
1。边上没有权重。
如果边上没有成本，实际上所有电路都变得相等，所有成本都为 0。 按道理，如果隐含的说cost实际上是最小跳数，那么满足上述条件的任何电路也是等价的。然后，问题是找到一个电路，即Hamiltonian Circuit or Hamiltonian Cycle。找出图中的 哈密顿电路 是 NP 完全的。
有 n! 条可能的路线。蛮力方法的 运行时复杂度为 O(n!)，其中 n 表示边数。
现有的最佳算法之一是 here 中的模拟和代码。
2。加权边（Wi for ith edge）
当图有加权边时，问题就变成众所周知的TSP (Travelling Salesman Problem)，这是一个NP-hard问题。社区中存在围绕 TSP 复杂性的困惑。您必须区分 TSP-Optimize 和 TSP-Decide。
TSP-Optimize 是 NP-hard。
TSP 决策是 NP 完全的。
有关详细说明，请查看这些资源 1 2. You can find a discussion in here。
系统要求您实施 TSP-Optimize。
-动态规划
Bellman–Held–Karp 算法。您可以在 here 中找到伪代码。 运行时复杂度：O(2n n2)，其中 n表示边数。
尽管存在其他解决方案技术，使用分而治之或贪心法，但它们并不是最优的。