机器人送货问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 621 天前的主题，其中的信息可能已经有所发展或是发生改变。

（腾讯云最新优惠活动来了：云产品限时1折，云服务器低至88元/年，点击这里立即抢购：9i0i.cn/qcloud，更有2860元代金券免费领取，付款直接抵现金用，点击这里立即领取：9i0i.cn/qcloudquan）

（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）

最近遇到了一个好玩的问题。

数轴上原点有个送货机器人。已知有货物 n 个分布在数轴上，其中 s_i 是货物 i 的起始地点，t_i 是货物 i 应该被送去的终点。机器人一次可以拿起一个货物，并且拿到了货物就必须把货物送去终点（不能中途放下）。求机器人的最短路径使得机器人能送所有的货物，并且回到原点。

货物

机器人

数轴

原点

4 条回复 ? 2023-06-14 14:45:34 +08:00

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);
}
}
```

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)的关系；就是看如何缩短货物终点与下个货物起点之间的路程之和的问题。

polymer

330 天前

可以转化为哈密顿环问题，是 NP-Complete 。

chaoxu

329 天前

@polymer 不是 NP-complete 。这个问题有多项式时间算法。