gpt4 book ai didi

algorithm - 广度优先搜索与迷宫中曼哈顿距离的 A*

转载 作者:行者123 更新时间:2023-12-04 14:26:51 25 4
gpt4 key购买 nike

给定迷宫中的初始状态和单个最终状态,是否有可能设计一个迷宫,其中广度优先搜索扩展的节点少于 A*,并以曼哈顿距离作为启发式函数?扩展到所有节点的成本是 1。

最佳答案

不可能。直觉是你的启发式比 BFS 更明智。这也是证明的基础。

正式:

  • h'(n) = 0也是一个可接受的启发式函数。
  • BFS 基本上是 A* 使用 h'作为它的启发式函数(因为它总是基于 f'=g(n) + h'(n) = g(n) 扩展)
  • h称霸h' , 因为对于所有 n :h'(n) <= h(n) .
  • h称霸h' , 并且是单调的,那么使用 h 算法扩展的节点是使用 h' 的算法扩展的子集.更多信息和证明在this thread ,并在 original article

  • QED

    关于algorithm - 广度优先搜索与迷宫中曼哈顿距离的 A*,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61710370/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com