旅行商问题

萌新苏苏 · 发表于 2022-12-6 16:17:19

假设有1个5*5的格子 x轴左上角为5 左下为0 右上为5 右下为0其中0,5坐标为自身坐标 5,5坐标为终点坐标,

其中途中有5个暂时停留点
请问如何取出其间的最优路径并到达重点!
脑袋有点大

第八号当铺 · 发表于 2022-12-6 16:17:20

萌新苏苏发表于 2022-12-6 19:35
A星寻路算法只是计算当前坐标到指定坐标的最优解,我的目的是在到达指定地点前计算路上所遇到的所有指定坐 ...

我觉得你这个是A星算法的一个变种,通过A星算法一般是在搜索起点到终点的最短路径,你也是在搜索起点到终点的路径,只不过路径上必须包含5个停留坐标,算法里把过滤的条件换一下.就可以得到一条路径最短,且经过全部停留点的路径

补充内容 (2022-12-6 22:39):
大致思想是在A星找到终点的时候做个补充判断,A星找到终点时,如果当前的路径未包含全部停留点,就不要返回了,继续寻找.

萌新苏苏 · 发表于 2022-12-6 16:17:58

说错了右上为0 右下为5

萌新苏苏 · 发表于 2022-12-6 16:19:26

x0=左下 x5 = 左上 y0=右上 y5=右下

走一回 · 发表于 2022-12-6 16:34:26

这个跟百du地图的搜索不同道路有点类似，要得到最优解，是不是要历遍所有可能的路线，再得出总长度呢？这个中间点一多，就是指数级增长的计算量吧。

一禅小和尚 · 发表于 2022-12-6 17:22:57

遍历所有可能，记录每种路径的代价，最后进行选择，深度优先或者广度优先

第八号当铺 · 发表于 2022-12-6 17:27:08

A星寻路算法应该能处理你这个问题你搜索下

云少i · 发表于 2022-12-6 18:27:09

A星寻路了解一下、

萌新苏苏 · 发表于 2022-12-6 19:35:21

第八号当铺发表于 2022-12-6 17:27
A星寻路算法应该能处理你这个问题你搜索下

A星寻路算法只是计算当前坐标到指定坐标的最优解,我的目的是在到达指定地点前计算路上所遇到的所有指定坐标最优路线,请麻烦您搜索一下旅行商的问题您就明白了!

		自动登录	找回密码
密码			注册

[已解决] 旅行商问题

最佳答案

点评