V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Timefly
V2EX  ›  问与答

求助大佬们一个路径规划的问题

  •  
  •   Timefly · 2020-06-09 23:32:50 +08:00 · 1008 次点击
    这是一个创建于 1388 天前的主题,其中的信息可能已经有所发展或是发生改变。
    原数据结构 [ { from:a, to:b }, {from: b, to: c} , {from: a, to: d}, {from: c, to: d}, { from:c, to :a }, {from:a , to: a}]

    现在需要求起始点 a 到 目标点 d , 所有的路径数据 ,类似 结果 : [ [ a,b,c,d ], [a,d] ]
    数据中可能会有环的情况 {from:a , to: a}
    技术栈是 javascript
    用深度优先递归遍历了, 但是遍历的路径总有些问题,不知道写法有什么不对 , 第一次发帖不知道怎么贴图, 求大佬帮助,给个思路或者解答
    第 1 条附言  ·  2020-06-10 11:01:46 +08:00
    //s1.ax1x.com/2020/06/10/toKXXn.png 代码图床,https:
    9 条回复    2020-06-10 16:11:11 +08:00
    also24
        1
    also24  
       2020-06-09 23:44:59 +08:00
    『遍历的路径总有些问题』 具体是什么问题?

    是否正确处理了成环的情况?
    [ab, bc, ac, cd]
    [a, b, c, a, b, c, d]
    Timefly
        2
    Timefly  
    OP
       2020-06-09 23:51:23 +08:00
    @also24 目前我吧环的数据过滤掉了, 具体主要是路径保存问题,我用 childPaths=[ ]保存遍历路径, 深度递归到一个终点不是 目标值 d 的时候,就从 childPaths 中 pop 推出最后一个,理论上感觉没啥问题,但是结果保存了未指向 d 的路径记录,明天看看怎么贴图大佬看下, 或者大佬能给个大概写法不
    also24
        3
    also24  
       2020-06-10 00:06:35 +08:00
    @Timefly #2
    还是贴代码和样例直观一些。
    Timefly
        4
    Timefly  
    OP
       2020-06-10 11:00:41 +08:00
    密码忘了,图床链接放不上来, 尴尬
    Timefly
        5
    Timefly  
    OP
       2020-06-10 11:02:55 +08:00
    @also24 图床放楼里了, 回复链接要验证手机号,密码我给忘了
    also24
        6
    also24  
       2020-06-10 11:16:05 +08:00
    @Timefly #5
    啊,JS 我不熟…… 大概看思路没感觉到太大问题,贴下文本单步调一下看看。


    https://gist.github.com/

    https://pastebin.com/

    https://paste.ubuntu.com/
    Timefly
        7
    Timefly  
    OP
       2020-06-10 11:19:23 +08:00
    also24
        8
    also24  
       2020-06-10 13:56:27 +08:00
    @Timefly #7
    我看了一下,大概看到两个问题
    1 、你的 47 行 dfs(nextData .....) 这里,传入的 nextData,里面的 isVisit 似乎没有做处理,这导致 a->h->d->e 这条路径跑不出来。

    2 、我只看到你标记了已被使用的路径,但是似乎没有处理重复使用的点,这样还是存在成环的可能,建议用一个 map 直接把已经走过的点存起来,这样就可以不用标记路径的 isVisit 了。

    比如说在这样的情况下:
    a->b, b->c , c->a

    虽然没有走重复路径,但是 a 点被走了两次,实际上已经成环了。
    Timefly
        9
    Timefly  
    OP
       2020-06-10 16:11:11 +08:00
    @also24 刚看到,已经解决了,其实是边界条件没处理好,第一点就是 在 for 循环结束的时候, 需要执行 childRes.pop() 从 childRes 中推出一条记录, 不然会叠加无用记录, 第二点就是这个 isVisit 的问题, 代码 39 行已经过滤了 isVisit 的数据了, 但是需要多排除掉 a ->b b->a 的情况, 非常感谢大佬的回复~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1466 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 17:24 · PVG 01:24 · LAX 10:24 · JFK 13:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.