机器人送货问题

[chaoxu]

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

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

[zer0fire]

贪心算法
```
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]

@zer0fire 暂时没想出来好的解法，但是我感觉你这个是个全枚举，并且是没有优化的。
比如 1 ，2 ，3 ，4 ，5 ，其中 1 ，2 完全相同的起点和终点；先搬 1 ，后搬 2 ，和先搬 2 ，后搬 1 ，你都会算一遍 345.

另外做了一下简单的转换，这个问题，可以忽略 si 与 ti 的关系，因为 si 和 ti 之间的距离是一定要走的；如果 sj 表示第 j 次搬哪个，这个问题就转换为 tj 与 s(j+1)的关系；就是看如何缩短货物终点与下个货物起点之间的路程之和的问题。

[polymer]

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

[chaoxu]

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