首页 注册 登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Jhonson
V2EX  ›  程序员

面试找出最短路径

  •   
  •   Jhonson ·
    ileadall42 · 2018-06-27 19:49:28 +08:00 · 10520 次点击
    这是一个创建于 2339 天前的主题，其中的信息可能已经有所发展或是发生改变。

    题目描述如图链接

    题目大意就是给定一个 n x m 的矩阵，矩阵只含 0 或者 1，其中 0 代表连通，1 代表阻断，给定任意矩阵内两点 A B 坐标，要求找出 A->B 的最短路径（假设是可达的），大家有什么好的思路吗，多多益善，谢谢了。(如果描述不清楚，还请提出。)

    Talk is cheap,show your code!

  • 矩阵
  • 给定
  • 路径
  • 题目
    75 条回复  •  2018-12-23 21:50:56 +08:00
    classyk
        1
    classyk  
       2018-06-27 19:51:22 +08:00 via iPhone
    这个不就是 Astar 算法吗
    baiihcy
        2
    baiihcy  
       2018-06-27 19:55:16 +08:00
    BFS 就能实现了吧
    Jhonson
        3
    Jhonson  
    OP
       2018-06-27 19:56:01 +08:00
    @classyk 谢谢你，这个图算法真有意思，我在看相关资料了！
    Jhonson
        4
    Jhonson  
    OP
       2018-06-27 19:56:21 +08:00
    @baiihcy 应该是没有问题的，BFS 和 DFS 感觉是万能的呀- -
    LawlietZ
        5
    LawlietZ  
       2018-06-27 20:08:42 +08:00 via iPad
    裸 dijksta 啊 超级简单。。。哪个公司的面试啊。。。
    ayyll
        6
    ayyll  
       2018-06-27 20:08:51 +08:00 via Android
    @baiihcy bfs 解单源最短路吧。。他这任意两点 明显是多源 bfs 确定不会被询问哭？ 所以 Floyd 吧
    ayyll
        7
    ayyll  
       2018-06-27 20:11:21 +08:00 via Android
    @LawlietZ 难道不是裸 Floyd。。。任意两点 dij 是一点到任意点吧。。
    cbais7890
        8
    cbais7890  
       2018-06-27 20:27:49 +08:00   ❤️ 9
    推荐一个可视化: https://qiao.github.io/PathFinding.js/visual/
    takato
        9
    takato  
       2018-06-27 20:37:06 +08:00 via iPhone
    @classyk

    @Jhonson

    A*无法保证全局最优
    Linxing
        10
    Linxing  
       2018-06-27 20:48:57 +08:00
    @cbais7890 感谢 很形象
    Parallel
        11
    Parallel  
       2018-06-27 20:52:08 +08:00   ❤️ 2
    题目描述的表示图的方式叫，邻接矩阵。针对这个题目，对应不同的查询需求，可以扯的有很多。
    以下，n 为顶点数，e 为边数。
    O(n^3) Floyd
    O(n^2) Dijkstra
    O(n*e) Bellman-ford
    O(e) SPFA
    ballshapesdsd
        12
    ballshapesdsd  
       2018-06-27 20:53:09 +08:00
    你们都审题了没有啊，怎么迪杰斯特拉都出来了
    LawlietZ
        13
    LawlietZ  
       2018-06-27 20:59:40 +08:00 via iPad
    @ayyll 我觉得是表述问题，一般不会深问多源最短路
    Parallel
        14
    Parallel  
       2018-06-27 21:00:57 +08:00
    @ballshapesdsd 哦，点开链接才看到完整的题目，理解题目有误。
    LawlietZ
        15
    LawlietZ  
       2018-06-27 21:02:41 +08:00 via iPad
    @Parallel SPFA 是 ke，常数 k 不能省略
    takato
        16
    takato  
       2018-06-27 21:07:09 +08:00
    @ballshapesdsd 似乎好多人理解成了邻接矩阵。。。
    其实是张迷宫图。。。
    wannafly
        17
    wannafly  
       2018-06-27 21:27:27 +08:00 via Android
    @takato 当然可以。取决于你的 heuristic function 怎么取，比如退化成最简单的迷宫算法。
    HiJ2017
        18
    HiJ2017  
       2018-06-27 21:38:25 +08:00
    这是很经典的数据结构题,当时教材上给了 BFS 和 DFS 两种解法
    <数据结构教程>--李春葆
    takato
        19
    takato  
       2018-06-27 21:40:11 +08:00
    @wannafly A×这个优化是要建立在去掉“最”的情况下的，即如果你只要一个局部最优。
    takato
        20
    takato  
       2018-06-27 21:40:45 +08:00
    @wannafly fix "A*"..被输入法替换了符号。。
    silhouette
        21
    silhouette  
       2018-06-27 21:45:35 +08:00 via Android
    floyd，模板题
    yanaraika
        22
    yanaraika  
       2018-06-27 21:47:03 +08:00   ❤️ 1
    @LawlietZ 8102 年了还 SPFA O(kE)……搞个网格图就退化到 O(ve)了
    yanaraika
        23
    yanaraika  
       2018-06-27 21:48:02 +08:00
    @Parallel 别用 SPFA 了……随便搞搞就卡成 O(ne)了
    wizardforcel
        24
    wizardforcel  
       2018-06-27 22:15:31 +08:00
    floyd 有点浪费了，它最后就要 distance[A][B]
    takato
        25
    takato  
       2018-06-27 22:29:56 +08:00
    @wannafly 问题是如果退化了以后，状态数还是和 DFS,BFS 一样，那么这个 function 在这个例子中的意义在哪里？
    当然我可以理解想做一个 Universal Algorithm/Model 的决心，但是也别忘了 overfit 的存在。

    即如果只是要个 local minimum，你说的就是比较好的方法，但是源问题不是这样定义的。
    JohnSmith
        26
    JohnSmith  
       2018-06-27 22:37:27 +08:00 via Android
    动规问题 刚做过
    JohnSmith
        27
    JohnSmith  
       2018-06-27 22:46:12 +08:00 via Android
    @JohnSmith 审错题了
    IceCola1
        28
    IceCola1  
       2018-06-27 22:48:20 +08:00
    对于的矩阵转换为图，如果只是 0，1 的话，深搜或者广搜都可以，时间复杂度都是 OV2,如果有权重的话，用 Dijkstra,时间复杂度，OV2，如果有负权重的话，bellman-ford 算法 O(VE)，如果所有点对都要输出的话，floyd 算法 O(V3)
    Rico
        29
    Rico  
       2018-06-27 23:08:04 +08:00
    可以参考我之前写的 A*算法，有动图 https://hogwartsrico.github.io/2016/03/11/AStarPathFinding/
    lsmgeb89
        30
    lsmgeb89  
       2018-06-28 00:42:09 +08:00
    bfs
    crab
        31
    crab  
       2018-06-28 01:23:08 +08:00
    @Rico 页面点章节都空白
    Mirana
        32
    Mirana  
       2018-06-28 01:24:40 +08:00
    dp
    jedihy
        33
    jedihy  
       2018-06-28 01:37:01 +08:00
    这种题目就真的不 show code 了，BFS 送分题。
    jedihy
        34
    jedihy  
       2018-06-28 01:38:49 +08:00
    @Rico 你的博客 chrome 只看得到提纲和地下的 footer。
    wolegequ
        35
    wolegequ  
       2018-06-28 01:40:01 +08:00 via Android
    还 talk is cheap 😅
    jssyxzy
        36
    jssyxzy  
       2018-06-28 01:58:24 +08:00
    算法自己复习。
    laxenade
        37
    laxenade  
       2018-06-28 02:02:18 +08:00
    leetcode 64 的变种？
    xiadong1994
        38
    xiadong1994  
       2018-06-28 02:05:21 +08:00
    这种路径长度都相同的题，用不着 dijkstra，单纯的 BFS。另外面试一般不会考 Floyd 吧……
    thedrwu
        39
    thedrwu  
       2018-06-28 02:37:31 +08:00
    看需要查询几次。 是否需要“最”优解。 如果只考虑短时间内能简单实现的解法：

    若查询一次可以如楼上用广搜。

    若查询多次，整张 n×m 表一遍一遍的扫（递推），假设点 a->点 z, 每扫一遍更新上一歩的解(a->b->z 中的 b)和最优路径和歩数， 直到收敛。 空间只需要 O(n×m)。
    wannafly
        40
    wannafly  
       2018-06-28 03:01:23 +08:00 via Android
    @takato 只要能保证 heuristic cost 算出来小于等于实际的 cost，那么就能保证得到的解是全局最优解。这种情况下也是能减少所要搜索的状态数量的。
    greenmoon55
        41
    greenmoon55  
       2018-06-28 08:18:02 +08:00
    lc 675
    shiyouming91
        42
    shiyouming91  
       2018-06-28 08:25:41 +08:00
    BFS+DP，用另一个同样大矩阵保存到达某个点的已知最少的步数，BFS 的每一步检查新矩阵中当前的位置是不是记录了更小或相等的步数。如果是就不再展开这个位置了，否则记录步数到这个位置。空间复杂度是 m*n+BFS 用的栈，我直觉觉得栈肯定比 m*n 小，可以忽略。时间复杂度没分析过，不够一般情况下不会太差。我的直觉是因为 BFS 的初期很容易剪掉相邻的分支，应该是 m*n 或者最多是 m*n*log(m*n)级别的

    应该不是最快的解法，不过可扩展性很强，因为很容易处理经过每格格子的开销不一样的情况，以及类似战棋游戏里的移动力有限想知道哪些点是可达的情况，各种涂色的问题等等

    总之在十年前之后的硬件条件下我会无脑用这种解法
    p1094358629
        43
    p1094358629  
       2018-06-28 08:31:53 +08:00
    我连题目都看不懂。。。A 为啥是 1，0 按照 XY 坐标不应该是 0，1 吗？？？
    yxcoder
        44
    yxcoder  
       2018-06-28 08:48:32 +08:00
    相对较短其实就算可以的了，最短的收益感觉不大
    yxcoder
        45
    yxcoder  
       2018-06-28 08:49:08 +08:00
    @yxcoder 刚刚发出去就发现理解错误了，尴尬
    yylucifer
        46
    yylucifer  
       2018-06-28 09:12:13 +08:00
    基本算法都不熟悉,还甩:Talk is cheap, show your code!
    Jhonson
        47
    Jhonson  
    OP
       2018-06-28 09:17:26 +08:00
    @yylucifer 哈哈哈，这不学着网上的用语的嘛，要是冒犯到你了，我给你道歉~
    takato
        48
    takato  
       2018-06-28 09:42:33 +08:00 via iPhone
    @wannafly 可是不能保证该函数是凸函数呀。
    mbtfdwlx
        49
    mbtfdwlx  
       2018-06-28 09:46:56 +08:00
    如果两点之间权值都是定值 用 BFS 就可以了， 有权值的情况下 就可以考虑 Dijkstra SPFA A-star 都可以
    q397064399
        50
    q397064399  
       2018-06-28 09:49:16 +08:00
    @Jhonson #47
    @yylucifer #46

    你还不让人家装个逼过过瘾，大家都是在网上，装一装无所谓的。
    hisune
        51
    hisune  
       2018-06-28 09:58:05 +08:00
    https://github.com/hisune/php-astar
    ioth
        52
    ioth  
       2018-06-28 09:58:49 +08:00
    学校的题目用来面试，这公司技术了得。
    kzzhr
        53
    kzzhr  
       2018-06-28 10:09:59 +08:00 via Android
    都用矩阵存了，这不是 floyd 的标准模板么
    jetyang
        54
    jetyang  
       2018-06-28 10:41:16 +08:00
    游戏里常用的算法，英雄 A 怎么走可以最快的攻击到英雄 B
    stargazer
        55
    stargazer  
       2018-06-28 12:06:42 +08:00
    话说想起在爱奇艺面试的时候非让我手写出全部代码。。。。还是自己太渣。。。。
    Jhonson
        56
    Jhonson  
    OP
       2018-06-28 12:29:31 +08:00
    @stargazer 你最终写出来了吗那，我当时是说出了利用距离来定夺，但是我只考虑了距离终点的距离，没有考虑起点，还用的是欧氏距离，最终啥都没写出来。
    Jhonson
        57
    Jhonson  
    OP
       2018-06-28 12:30:09 +08:00
    @takato 真的没有办法全局最优吗，那只有靠搜索算法来更新的方法最靠谱了呀
    loryyang
        58
    loryyang  
       2018-06-28 13:09:54 +08:00
    首先想到的就是 BFS 打表，从 A 开始，一直广度搜索打表，更新步长，一直到接触到 B 就结束了
    Solarest
        59
    Solarest  
       2018-06-28 13:19:07 +08:00
    Floyd 吧
    yuriko
        60
    yuriko  
       2018-06-28 13:53:46 +08:00
    面试的话，能知道是广搜就行了吧……
    就是试探你有没有基本的算法基础……
    hackpro
        61
    hackpro  
       2018-06-28 14:10:41 +08:00
    @cbais7890 #8 为啥我拽不动绿色方块 也没找到红色方块？
    Win10 64bit Chrome 67.0
    zzj0311
        62
    zzj0311  
       2018-06-28 14:32:11 +08:00 via Android
    就是个 A*，哪那么多问题。。
    stargazer
        63
    stargazer  
       2018-06-28 15:05:58 +08:00
    @Jhonson 写啥，说了大体思路，不行，必须手写，写毛啊，前边各种问题已经问了一个多小时了，再写俩小时代码？
    lzhCoooder
        64
    lzhCoooder  
       2018-06-28 15:25:18 +08:00
    dijksta 和 A*都可以啊，选哪个看实际情况，面试的话把这两个算法都说出来没毛病
    salamanderMH
        65
    salamanderMH  
       2018-06-28 15:59:34 +08:00
    写文章记录过
    https://segmentfault.com/a/1190000010285088
    yao978318542
        66
    yao978318542  
       2018-06-28 17:03:19 +08:00
    https://anvaka.github.io/ngraph.path.demo/ 你可以看看这个
    mogami18
        67
    mogami18  
       2018-06-28 19:36:25 +08:00
    floyd
    zke1e
        68
    zke1e  
       2018-06-28 19:52:25 +08:00
    dijkstra 啊
    maggch
        69
    maggch  
       2018-06-28 21:37:55 +08:00
    这题边权都是 1,最优就是 BFS 了
    maggch
        70
    maggch  
       2018-06-28 21:39:27 +08:00
    Dijkstra 带 log ,Floyd 复杂度 n^3,做这题时间复杂度都非常的不优秀
    cbais7890
        71
    cbais7890  
       2018-06-28 21:57:48 +08:00
    @hackpro #61
    貌似大家都没问题, 如果要排除插件问题, 用隐身模式试试 ?
    LawlietZ
        72
    LawlietZ  
       2018-06-28 23:29:09 +08:00
    @yanaraika 与几几年有什么关系呢，退化不退化还是看数据吧，acm 里面不还是很多去使用 spfa 去做最短路的题。。当然我个人更倾向用队列优化的 Dij，SPFA 的 k 值是由算法中点的入队出队次数决定的，一般还是不容易直接降到 ne 吧
    classyk
        73
    classyk  
       2018-06-29 10:22:46 +08:00 via iPhone
    @takato 实际应用中 A 星算法就是最佳选择，除非你地图实在太小了，不需要注意任何效率问题了
    takato
        74
    takato  
       2018-06-29 11:44:27 +08:00 via iPhone
    @classyk 不不不，现实问题都不是全局最优问题，求全局最优用 A*基本就是.....那啥....

    建议打好基础.
    hobochen
        75
    hobochen  
       2018-12-23 21:50:56 +08:00
    @maggch fib 堆好像可以去掉 log ？
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3385 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 05:02 · PVG 13:02 · LAX 21:02 · JFK 00:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.