3D环境下150个节点建边及旅行商问题(TSP)求解最佳方案咨询

第一步：构建TSP所需的精简图结构 #

你的游戏世界虽有3.75亿个位置，但无需将整个世界转化为图，只需聚焦150个指定点位：

• 将每个指定点位作为图的节点，节点存储对应的Location信息。
• 计算每对节点间的最短路径长度：调用你已实现的双向A*寻路器，对每组点位对(A,B)执行getPath(A,B, walkHandler, teleportHandler)，取路径的步数（或实际距离，按需选择）作为图中A到B的边权值。
  • 优化：因TSP属于无向问题（A到B的最短路径长度与B到A相等），仅需计算150*149/2=11175次寻路，减少一半计算量。
  • 注意：你的寻路器已支持传送，计算出的最短路径会自动考虑传送的最优选择，直接复用即可。

第二步：求解TSP问题 #

150个节点的规模无法用精确算法（如动态规划，时间复杂度O(n²2ⁿ)）求解，需采用启发式近似算法，在可接受时间内得到足够优的解：

• 优先推荐：遗传算法
  实现简单，适配中等规模TSP，能快速收敛到较优解，核心步骤：
  1. 生成初始种群：随机生成若干条遍历所有150个点位的路径。
  2. 适应度计算：路径总长度越短，适应度越高。
  3. 选择：保留适应度较高的路径。
  4. 交叉：对两条路径执行交叉操作（如部分映射交叉PMX），生成新路径。
  5. 变异：随机交换路径中两个点位的位置，维持种群多样性。
  6. 迭代：重复上述步骤直到结果收敛。
• 备选：蚁群算法
  模拟蚂蚁觅食行为，适合离散路径优化，能找到优质解，但实现复杂度略高于遗传算法。
• 补充优化：2-opt局部优化
  在得到初始路径后，用2-opt算法迭代优化：遍历路径中所有可能的边对，若交换后总长度更短则保留，直到无法优化。可与遗传算法/蚁群算法结合，进一步提升解的质量。

第三步：将TSP路径转化为游戏实际行走路线 #

得到TSP的最优点位遍历顺序后，依次对每对相邻点位调用双向A*寻路器，获取包含传送节点的具体行走路径，将这些路径拼接即可得到完整的遍历路线。

关键优化细节 #

• 缓存寻路结果：将点位对的最短路径长度存入二维数组或Map<Pair<Location,Location>, Integer>，避免重复计算。
• 并行计算路径长度：利用Java的ExecutorService实现多线程并行处理1万余次寻路任务，缩短总耗时。
• 边权值选择：若游戏中移动成本按步数（Block数量）计算，用路径节点数作为边权；若按实际距离计算，累加路径中相邻节点的欧氏距离作为边权。

内容的提问来源于stack exchange，提问作者kmaxi