我正在尝试做 c++ 程序。我正在尝试解决我有很多点的问题。现在我需要找到通过所有点的路径。这实际上不是 TSP，因为根据我对 TSP 的了解，可以从所有点移动到其他所有点。但在我的情况下，点之间的路径网络是固定的，我只需要找到穿过所有点的合适路径，前提是所有点可能与其他点没有连接......所以我应该遵循什么算法。
问问题
591 次
2 回答
1
看来您正在寻找一种遍历图形的方法？如果是这样，您是否尝试过广度优先搜索http://en.wikipedia.org/wiki/Breadth-first_search或深度优先搜索http://en.wikipedia.org/wiki/Depth-first_search来遍历您的图表。
于 2012-12-02T02:42:33.030 回答
1
你想找到一个图的哈密顿路径。
在图论的数学领域中，哈密顿路径（或可追踪路径）是无向图中的一条路径，它只访问每个顶点一次。哈密顿循环（或哈密顿回路）是哈密顿路径，它是一个循环。确定图中是否存在这样的路径和循环是哈密顿路径问题，它是 NP 完全的。
存在的一些技术：
有n！不同的顶点序列可能是给定 n 顶点图中的哈密顿路径（并且在完整图中），因此测试所有可能序列的蛮力搜索算法将非常慢。有几种更快的方法。Frank Rubin 的搜索过程将图的边分为三类：必须在路径中的边、不能在路径中的边和未确定的边。随着搜索的进行，一组决策规则对未确定的边进行分类，并确定是停止还是继续搜索。该算法将图划分为可以单独求解的组件。此外，可以使用 Bellman、Held 和 Karp 的动态规划算法在 O(n2 2n) 时间内解决问题。在这种方法中，人们确定，
Andreas Björklund 提供了一种替代方法，使用包含 - 排除原则将计算哈密顿循环数的问题简化为更简单的计数问题，即计算循环覆盖，这可以通过计算某些矩阵行列式来解决。使用这种方法，他展示了如何通过蒙特卡罗算法在 O(1.657n) 时间内解决任意 n 顶点图中的哈密顿循环问题；对于二分图，该算法可以进一步改进到时间 O(1.414n)。
对于最大三阶图，仔细回溯搜索可以在时间 O(1.251n) 内找到哈密顿循环（如果存在）。
于 2012-12-02T02:45:32.227 回答