这是一个创建于 819 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近遇到了一个好玩的问题。
数轴上原点有个送货机器人。已知有货物 n 个分布在数轴上，其中 s_i 是货物 i 的起始地点，t_i 是货物 i 应该被送去的终点。机器人一次可以拿起一个货物，并且拿到了货物就必须把货物送去终点（不能中途放下）。求机器人的最短路径使得机器人能送所有的货物，并且回到原点。
 |
1
zer0fire 2022-08-26 18:51:34 +08:00
贪心算法
``` int getDistance(List<货物数据> list, point 当前坐标){ if(list.size() == 1){return list.get(0).距离+距离原点距离} int min=0; foreach(Good g : list){ int distance = 先取第 n 个货物的距离+getDistance(list(去除第 n 个货物), 第 n 个货物终点); min = Match.min(min, distance); } } ``` |
 |
2
stuazt 2022-09-05 16:19:45 +08:00
@zer0fire 暂时没想出来好的解法，但是我感觉你这个是个全枚举，并且是没有优化的。
比如 1 ，2 ，3 ，4 ，5 ，其中 1 ，2 完全相同的起点和终点；先搬 1 ，后搬 2 ，和先搬 2 ，后搬 1 ，你都会算一遍 345. 另外做了一下简单的转换，这个问题，可以忽略 si 与 ti 的关系，因为 si 和 ti 之间的距离是一定要走的；如果 sj 表示第 j 次搬哪个，这个问题就转换为 tj 与 s(j+1)的关系；就是看如何缩短货物终点与下个货物起点之间的路程之和的问题。 |
 |
3
polymer 2023-06-14 06:21:32 +08:00
可以转化为哈密顿环问题，是 NP-Complete 。
|
Select Language