java - Java 中旅行商问题的最近邻启发式

Question

我想编写一个java程序，用最近邻启发法解决旅行商问题。算法的步骤如下:

第 1 步:从任意随机顶点开始，将其称为当前顶点

第2步:找到一条边，该边给出当前顶点和未访问顶点之间的最小距离，称之为V

第 3 步:现在将当前顶点设置为未访问的顶点 V 并将该顶点 V 标记为已访问

第4步:如果所有顶点都被访问过至少一次，则终止条件

第 5 步:转到第 2 步

我无法确定哪些数据结构适合解决这个问题。如何识别到当前节点距离最小的节点(步骤 2)？优先级队列是一个不错的选择吗？我还可以使用哪些其他数据结构？如何确保游览中的倒数第二个节点连接到起始节点？我应该使用堆栈吗？我还能用什么？

Answer 1

为了用最佳(最佳)解决方案解决旅行商问题，您必须在图中生成所有可能的路径，并找到成本最小的路径(顶点之间边的总和最小)。您所描述的最近邻方法接近于使用 Greedy alrogithms 。假设你有n图中的顶点并且每个顶点都是连接的，您可以按照以下步骤使用贪婪策略/最近邻方法解决旅行商问题(假设您有 Set 的 Vertex 类对象):

1. 创建 Set初始未访问的顶点。
2. 创建 Map喜欢 Map<Vertex, Integer>其中键是起始顶点，值是总体路径成本。
3. 创建 Map其中键为路径的起始顶点，值为 List<Vertex>代表路径 ( Map<Vertex, List<Vertex>> )。
4. 选择一个之前未选择过的随机顶点(出现在步骤 1 中的 Set 中)。
5. 选择与第 4 步中选择的顶点最接近的顶点(您必须检查所有未访问顶点的边成本并选择最少的一个)。将顶点添加到 List<Vertex>与当前起始顶点(在步骤 4 中选取)的键关联并存储在 Map 中在步骤 3 中创建。(注意:此处您将考虑与步骤 4 中选取的顶点不同的所有顶点)。
6. 增加与当前起始顶点相关的路径成本值，该值在步骤 4 中选取，存储在 Map 中在步骤 2 中创建。
7. 通过检查距当前最后一个顶点最近的边，重复步骤 5-6，直到没有可供访问的顶点(您必须访问从步骤 4 中选取的顶点开始的所有顶点)。
8. 删除第 4 步中选取的起始顶点，形式 Set在第 1 步创建。
9. 重复步骤 4-8，直到在步骤 4 中没有可供选取的顶点。

然后你可以排序 Map在步骤 2 中按值创建并选择成本最低的条目。然后你可以得到它的 key 并从Map中选择路径在步骤 2 中由先前选择的 key 创建，与最低的总体成本相关。这将是用该算法计算出的最佳路径。