yzX*_*yzX 1 algorithm search graph
我已经在互联网上查看了问题的实现,我有一个问题:每当你添加一个节点时,你需要在打开的列表中搜索它(为什么它不足以在封闭列表中搜索它？)？为什么要搜索它以查看是否可以最小化成本,因为您总是在打开列表中生成最小得分节点的邻居？打开列表中具有较旧父节点的节点的成本是否比同一节点小,但具有较新的父节点？
我将从与Best First Search的简短,与问题相关的背景开始,然后我将专门解决您的两个问题(希望到那时,它们已经得到了回答).
这种搜索以使用特殊评估函数而着称,该函数估计到目标节点的距离(估计"你离目标节点有多远？").此功能称为"启发式".例如,一个非常简单直观的导航问题启发式(从城市A到城市B的最短路径)将使用欧几里德距离的启发式,这是最短路径(就好像两个城市直接连接在一条道路上) ).此函数具有作为一个重要性质容许的,因为它是该距离的下估计.这对于Best First Search能够找到最佳解决方案的证据至关重要.
给定这样的启发式函数,该算法现在通过其成本(启发式函数)对所有发现的节点进行优先级排序.这是使用优先级队列完成的.实际上,您可以使用精确的BFS算法实现最佳优先搜索,只需使用优先级队列切换BFS的队列.该算法有时被称为知情搜索,因为它具有一些世界先验知识(通过启发式函数表示)并且它使用它来指导搜索(通过搜索节点通过其启发式值表示).
您经常可以听到搜索算法中的"扩展"操作.在大型域中,搜索实例太大而无法在内存中填充,这个概念至关重要.但是,这个想法也可以抽象地应用于小域,而无需任何额外的成本.这里的想法是每个节点都有一个运算符Expand,一旦被调用,就会返回(在大域中:创建并返回)所有邻居节点的列表.通过Expand操作到达的节点通常称为生成.
最佳优先搜索在搜索期间维护两个列表:打开列表和关闭列表.
打开列表是所有生成节点的集合.这意味着那些节点是扩展节点的邻居.如上所述,打开列表通常被实现为优先级队列,因此搜索可以简单地使嵌套最佳节点出列.
闭合列表是所有扩展节点的集合.这意味着那些已经被"搜索"的节点.这可以防止搜索一次又一次地访问节点.旁注:在大域中,封闭列表不能适合所有节点,因此必须巧妙地实现封闭列表.例如,可以使用布隆过滤器减少所需的内存.
1."为什么仅在封闭列表中搜索它是不够的？"
我希望你已经理解了这个问题的答案.关闭列表开始为空,在搜索期间,扩展节点被推入其中.这些节点不是目标节点.而是已经遍历过的"已访问"节点.
2."为什么你要搜索它,看看你是否可以最小化成本,因为你总是在开放列表中生成最小得分节点的邻居？"
如上所述,可接受的启发式方法仅承诺低估到达目标节点的实际成本.这意味着每次简单的最小化并不能保证找到最便宜/最短的路径.然而,该算法的一个巨大好处是,一旦找到路径,它就可以"截断"/"修剪"昂贵的路径.例如,找到了成本100的路径.我们仍然不知道它是否是最佳路径.我们需要继续搜索图形,但现在我们可以修剪任何路径,离开一个启发值为100或更大的节点,因为我们已经找到了类似或更便宜的路径.请注意,这使我们无需搜索所有图表即可完成搜索.