V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
chaoxu
V2EX  ›  算法

机器人送货问题

  •  
  •   chaoxu · 2022-08-26 16:39:46 +08:00 · 1090 次点击
    这是一个创建于 821 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    4 条回复    2023-06-14 14:45:34 +08:00
    zer0fire
        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);
    }
    }
    ```
    stuazt
        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)的关系;就是看如何缩短货物终点与下个货物起点之间的路程之和的问题。
    polymer
        3
    polymer  
       2023-06-14 06:21:32 +08:00
    可以转化为哈密顿环问题,是 NP-Complete 。
    chaoxu
        4
    chaoxu  
    OP
       2023-06-14 14:45:34 +08:00
    @polymer 不是 NP-complete 。这个问题有多项式时间算法。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1232 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 23:48 · PVG 07:48 · LAX 15:48 · JFK 18:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.