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

求一个最短行程的算法或思路

  •  
  •   elfive · 2017-12-27 13:06:18 +08:00 · 4840 次点击
    这是一个创建于 2525 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现在有一个存放了 n 个线段(起点和终点坐标)的数组,结构如下:
    [
    [(sx_1,sy_1),(ex_1,ey_1)],
    [(sx_2,sy_2),(ex_2,ey_2)],
    ......
    [(sx_n,sy_n),(ex_n,ey_n)]
    ]

    有没有这样一个,以其中某个点为起点,走过所有线段,并且使得总的行程最短的算法?

    这里的距离不仅包含线段的长度,还包含线段之间的跳转距离。

    要求就是:走线段的时候,必须从线段一端进入,从另一端退出,且不能有重复走某条线段。
    第 1 条附言  ·  2017-12-27 13:57:31 +08:00

    如图,黑色代表的是需要走过的线段,红色的是跳转线路; 现在就是有这些线段的起始点和终止点的坐标,需要求出一条路径来,使得红色的跳转距离最短(也就是总行程最短)。

    随意画了个图,意思一下就好了。

    39 条回复    2018-01-02 10:59:24 +08:00
    zjp
        1
    zjp  
       2017-12-27 13:34:59 +08:00 via Android
    可以转化为图的问题。并不能保证某个点可以到达所有边(不连通),也不能保证不重复走(有死端)
    hinate
        2
    hinate  
       2017-12-27 13:36:39 +08:00
    这是类似走迷宫吗?
    ynyounuo
        3
    ynyounuo  
       2017-12-27 13:41:13 +08:00
    这不是 MST ?
    ynyounuo
        4
    ynyounuo  
       2017-12-27 13:42:56 +08:00
    好吧,并不一样。
    zj299792458
        5
    zj299792458  
       2017-12-27 13:44:01 +08:00
    听起来是遍历所有点,直接深度优先搜索
    ynyounuo
        6
    ynyounuo  
       2017-12-27 13:44:25 +08:00
    感觉比较类似 TSP 问题,可以去参考一下
    aheadlead
        7
    aheadlead  
       2017-12-27 13:46:38 +08:00
    我觉得以后提问的时候最好多画几张图
    也便于别人看懂意思
    ladeo
        8
    ladeo  
       2017-12-27 13:53:35 +08:00 via Android
    ospf
    elfive
        9
    elfive  
    OP
       2017-12-27 13:58:17 +08:00
    @aheadlead
    @hinate
    简单补了个图,看看能不能稍微清楚点
    geelaw
        10
    geelaw  
       2017-12-27 13:59:49 +08:00 via iPhone
    什么是“线段之间的跳转距离”?
    xinhangliu
        11
    xinhangliu  
       2017-12-27 14:00:45 +08:00 via Android
    模拟退火
    Bryan0Z
        12
    Bryan0Z  
       2017-12-27 14:03:24 +08:00 via Android
    MST 的算法改一下?
    aheadlead
        13
    aheadlead  
       2017-12-27 14:03:24 +08:00
    @elfive 补的图很棒,有数据范围吗?

    N < 20,N<100 和 N<10000 的思路完全不一样了…
    luoshuangfw
        14
    luoshuangfw  
       2017-12-27 14:05:05 +08:00 via Android
    需要明确一下:从一条边的 end 出来,是否可以进入剩下所有边中任意一条边的 start,只要没走过?
    elfive
        15
    elfive  
    OP
       2017-12-27 14:05:39 +08:00
    @aheadlead 数据范围其实没啥限制,但是绝大多数情况应该是 N < 500
    elfive
        16
    elfive  
    OP
       2017-12-27 14:06:40 +08:00
    @geelaw 就是 线段某个端点 到 另一条线段某个端点 之间的最短距离;
    elfive
        17
    elfive  
    OP
       2017-12-27 14:08:41 +08:00
    @luoshuangfw 只要保证:1、走过所有线段; 2、不重复走任何一条线段; 3、线段不能拆分,这 3 个条件就 OK 了
    Bryan0Z
        18
    Bryan0Z  
       2017-12-27 14:12:01 +08:00 via Android
    找一个线段当起点
    依次判断其他线段端点到它的端点的距离,找到一个最小的加入
    重复步骤二

    反正就那个意思,把 prim 或者 d 算法改一下就好了
    Bryan0Z
        19
    Bryan0Z  
       2017-12-27 14:14:52 +08:00 via Android
    哦,不太一样
    luoshuangfw
        20
    luoshuangfw  
       2017-12-27 14:14:55 +08:00
    @Bryan0Z 这是不行的,不是 MST ;确切的说要求的不是一棵树,而是一个回路
    wafm
        21
    wafm  
       2017-12-27 14:15:57 +08:00
    曾经干游戏的时候做过一个类似的玩意

    我提供一条思路

    比如你说的图,如果从黑线的一端走到另一端,确定到达端点后,原地做一个半径算法,半径最短的黑点取点,再判断哪个点最优。
    Bryan0Z
        22
    Bryan0Z  
       2017-12-27 14:16:33 +08:00 via Android
    @luoshuangfw 再加一个条件,一旦连完,把那两个端点删掉就好了,基本思路肯定不会有问题
    luoshuangfw
        23
    luoshuangfw  
       2017-12-27 14:18:06 +08:00
    @Bryan0Z 这是不行的,树的端点(也就是叶子)有许许多多个,你到达叶子之后准备往哪里走?
    xingwing
        24
    xingwing  
       2017-12-27 14:22:48 +08:00
    bitmap
    geelaw
        25
    geelaw  
       2017-12-27 14:24:02 +08:00
    这个问题是 NP-困难的——考虑一个特殊情况,就是每个线段的长度都是 0 的时候。

    https://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP
    luoshuangfw
        26
    luoshuangfw  
       2017-12-27 14:27:19 +08:00
    @geelaw 我一开始也想到 TSP,但不知道咋 reduction ——蓝后看到你这个,才知道原来 Euclidean TSP 也是 NP-Hard= =
    Vinty
        27
    Vinty  
       2017-12-27 14:55:45 +08:00
    其实就是 tsp 问题啊,只不过原始 tsp 中是点,这里换成了线段而已,线段会多一个出入方向的二元参数,
    不过即使这类问题最常用的元启发算法,我自己的使用感受来看,对高维高相关的问题其实效率也是有限,但没办法没什么别的好方法
    Bryan0Z
        28
    Bryan0Z  
       2017-12-27 15:46:06 +08:00 via Android
    @luoshuangfw 很简单呀,生成的树肯定只有两个端点可以试,然后待定线段还有 n 个,无非是试 4n 次,总算法效率 n 方能接受
    Kilerd
        29
    Kilerd  
       2017-12-27 16:02:06 +08:00
    这不就是图的经典算法吗?

    把黑边当成图的点,然后存在全链接的图,代价就是距离,然后用最短距离算法就可以算出来了啊

    PS:好久没用过了,所以可能名词用得不是很对,所以大概意思懂了就行
    klesh
        30
    klesh  
       2017-12-27 16:39:54 +08:00
    最小生成树就行了吧.
    由于线都是要走完的, 它是不变的, 不用考虑. 唯一变化的就是两条线端点之间的距离. 把这个距离看作权值. 那就是最小生成树了
    arzterk
        31
    arzterk  
       2017-12-27 17:08:59 +08:00
    NP-Hard 的问题,没有稳定的算法吧
    arzterk
        32
    arzterk  
       2017-12-27 17:11:09 +08:00
    @klesh 端点之间的距离是和走的顺序有关的,TSP 扩展问题
    quinoa42
        33
    quinoa42  
       2017-12-27 17:21:26 +08:00
    粗略的大致思路如下:
    0 )为了解题需要建 graph
    1 )计算每个线段的长度,把线段长度记为 graph 中每个 node 的权值
    2 )对于任意的两条线段 s1, s2,求 s1 两端两点到 s2 两端两点,总共 4 段跳转线段的长度,并保留最短的那条作为 node s1 到 node s2 的 edge 的权值
    3 )这样题目的数据就转化成了一个 complete graph,因为要走过每个点,每个 node 的权值和结果无关(这部分永远是要加在一起,加入最短路径里的)
    4 )总结:预处理之后实际上是要找到一条路径遍历所有 node 且不重复经过其中一个 node,这个问题是 NP-complete 的,参见 https://en.wikipedia.org/wiki/Hamiltonian_path
    5 )具体做法我脑子笨,只能想到一个略暴力的动归:a[s][i][j]表示对于一个 graph 中所有 node 的子集 s,从 node i 到 node j 可得到的最短遍历路径
    如果指定起点的话就是 a[s][i],表示在子集 s 中从起点到终点 node i 可找到的最短遍历路径,但不管哪种,枚举 s 需要 O(2^n),500 的数据规模怎么看都不太现实
    gaohongyuan
        34
    gaohongyuan  
       2017-12-27 17:25:56 +08:00
    楼主的问题的一个特例是:所有的线段长度为 0 ——也就是旅行商问题 ( TSP )。所以,这个问题比 TSP 更加困难。

    因为 TSP 是 NP-Hard 问题,所以楼主的问题也是 NP-Hard 问题,即不存在高效(多项式时间复杂度)的解法。

    说错请指正。。
    zzl
        35
    zzl  
       2017-12-27 17:29:15 +08:00
    迪杰斯特拉算法???我 GIS 行业中最短距离算法
    quinoa42
        36
    quinoa42  
       2017-12-27 17:40:43 +08:00
    @zzl dijkstra 是用 priority queue,以一个类似广搜的模式寻找一个图中从某节点出发到某节点截止的最短路径,无法保证找到的最短路径遍历了所有节点
    klesh
        37
    klesh  
       2017-12-27 18:16:51 +08:00
    @arzterk 这个与 TSP 还是有区别的, 有些线已经被确定, 而且 TSP 是一个回路, 这个需要的是一个通路就够了. 复杂度低很多.

    题主请说明下起始点是随机指定的, 去求这个路径. 还是点和路径要一起求?
    elfive
        38
    elfive  
    OP
       2017-12-27 22:27:06 +08:00
    @klesh 起始点随机指定,不强制指定,任选。
    ordog
        39
    ordog  
       2018-01-02 10:59:24 +08:00
    添加一个虚拟的起始点 O,O 到所有线段两端的距离相同,比如都是 0。问题转化为一个全联通的 TSP 问题(包括 O 点在内),只是一些两两点之间路径固定(初始的黑色线段)。如果问题规模不大,是可以通过整数规划求精确解的。如果采用一些 tsp 的启发式方法求解,需要注意由于 O 点的存在,两边之和大于第三边的法则这里不适用。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1010 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 21:33 · PVG 05:33 · LAX 13:33 · JFK 16:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.