提问人：julio meza 提问时间：11/8/2023 最后编辑：ravenspointjulio meza 更新时间：11/9/2023 访问量：36
TSP的变体，只需要访问一组城市，但如有必要，可以访问集合以外的城市
Variation of TSP which needs to visit only a set of cities but can visit cities outside the set if necessary
问：
我需要解决 TSP 的变体，其中节点代表邻域。社区可以是中心社区，也可以是非中心社区。从非中心社区开始，我需要找到最短的路径，该路径恰好访问所有非中心社区一次，然后返回起点。请注意，如果最短路径有助于找到更短的路径，则最短路径可能包括一个或多个中心邻域。
输入：
- 加权无向图 G，其中节点表示邻域，边表示邻域之间的距离（行驶成本）。
- 一个列表指示社区是中心社区还是非中心社区。
- 一个起始的社区。
输出：
- 该路径仅访问每个非中心社区一次，同时最小化总行驶距离。
- 这种路径的成本
考虑到提供的输入和输出规范，我正在寻找有效解决上述问题的指导或算法。任何帮助或见解将不胜感激。
答：
0赞
ravenspoint
11/9/2023
#1
- 对每对非中心顶点进行 LOOP 操作
- 求对之间的最短路径
- LOOP 遍历路径中的中心顶点
- MARK 顶点
- LOOP 遍历路径中的中心顶点
- 求对之间的最短路径
- 中心顶点上的 LOOP
- IF 顶点未标记 删除顶点
- 将标准 TSP 算法应用于简化图
请注意，该算法将使用必要的中心顶点找到最短路径，它也可以使用可以避免的中心顶点（因为它们被标记在另一对非中心顶点之间的最短路径中）
评论
0赞
beaker
11/9/2023
@n.m.在评论中建议的算法使用标准的全对最短路径算法，唯一的修改是对图形本身的修改，并且不会冒引入不必要的中心顶点的风险。
评论