求最短路径算法

显示全部楼层 · 2021-1-27 06:31:07

这个问题比较复杂，编程是次要的，主要是数学模型
问题如下：
一张地图上有几十个点（不同的地点）
已知每个点之间的距离（不同地点之间的距离）
随机抽取其中几个点（要去几个不同的地方，通常是要去四到八个地点）
如果少于等于四个点，分两条线路走
如果大于四个点，分三条线路走
如果大于八个点，分四条线路走
求：计算出最短线路，而且每条线路经过的距离比较均衡
（实际应用：从仓库发货，有多个地点，已知每个地点之间距离，求发货最短路线，并且分派给多个人分发）
难点在于不是一条线，而是分多条线路分别进行
分 -->

千问 · 2021-1-27 06:31:07

这算法一点也不难，只要你能把你那些含糊不清似是而非的需求描述准确，比如，什么叫“最短”，是路程之和最短，还是路程平均值最短，还是什么，或者只是要近似最优解。“比较均衡”怎么个“比较”法，怎么叫“均衡”。等等。

千问 · 2021-1-27 06:31:07

引用1楼的回复:这算法一点也不难，只要你能把你那些含糊不清似是而非的需求描述准确，比如，什么叫“最短”，是路程之和最短，还是路程平均值最短，还是什么，或者只是要近似最优解。“比较均衡”怎么个“比较”法，怎么叫“均衡”。等等。
走过几个点，经过总路程最短
分几条线走，每条线经过的总路程差不多（近似）
看懂这句就知道是什么意思了
（实际应用：从仓库发货，有多个地点，已知每个地点之间距离，求发货最短路线，并且分派给多个人分发）

千问 · 2021-1-27 06:31:07

有算法的,记得读书时候就教过
都还给老师了,找一下算法书吧,算最短路径是经典的算法教程来的