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

#算法#,#图#,传送门如何描述?

  •  
  •   pyKun · 2015-03-16 11:46:46 +08:00 · 2561 次点击
    这是一个创建于 3572 天前的主题,其中的信息可能已经有所发展或是发生改变。
    元素是一个“传送门”

    图算法里构造x->y的权值的问题,a点是个传送门,出口在b点,o点在a点旁边(o点其他旁边的就o1, o2, o3)
    那o点周围的权值是不是说应该记录且仅记录
    o -> o1
    o -> o2
    o -> o3
    o -> b (a点是强制传送,所以到a了后直接换成b的位置)
    下次遍历的时候就是遍历 o1 o2 o3 和 b 的邻居了
    第 1 条附言  ·  2015-03-16 16:56:01 +08:00
    更新下,我看了下一班矩阵+障碍物组成的迷宫用 a* 算法去利用一个估算值来遍历

    但是传送门在这里,估算好难算了,当前节点和目标节点之间的估算不能用直线来判断了
    1 条回复    2015-03-16 18:39:37 +08:00
    cfan8
        1
    cfan8  
       2015-03-16 18:39:37 +08:00   ❤️ 1
    传送门既然强制传送,不就相当于没有a点只有b点么,直接把图里a点删了把入度全部改到b点上
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3040 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 13:00 · PVG 21:00 · LAX 05:00 · JFK 08:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.