我可以在一致的启发式/统一成本/Dijkstra的搜索下修改标准A*(A星)吗，这样它就不必更新边界？

Question

标准方法如下：AI：现代方法

function UNIFORM-COST-SEARCH
node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
if frontier is empty then return failure
node <- POP frontier  /* chooses the lowest-cost node in frontier */
if GOAL-TEST(node) then return SOLUTION(node)
add node to explored
for each action in ACTIONS(node) do
child <- CHILD-NODE(problem, node, action)
if child is not in explored or frontier then
frontier.INSERT(child)
else if child is in frontier with higher PATH-COST then
replace that frontier node with child

在这里，这一步骤实现起来很复杂，正常的优先级队列无法有效地更新某个元素的优先级。

else if child is in frontier with higher PATH-COST then
replace that frontier node with child

我正在考虑以以下方式修改算法：

function UNIFORM-COST-SEARCH-Modified
node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
if frontier is empty then return failure
node <- POP frontier  /* chooses the lowest-cost node in frontier */
> if node is in explored then continue
if GOAL-TEST(node) then return SOLUTION(node)
add node to explored
for each action in ACTIONS(node) do
child <- CHILD-NODE(problem, node, action)
>     if child is not in explored then
frontier.INSERT(child)

所以我不在乎边界是否包含重复的状态。我只扩展了边境上重复出现的第一个州。由于路径成本是consistent，并且边界是使用priority queue来实现的，因此忽略成本较高的其他重复状态是无害的。

这合理吗？

更新

对不起，我忘了提一下，我对一致启发式案例特别感兴趣。

Answer 1

这个想法原则上是正确的，但有一个错误：

> if node is in explored then continue

如果启发式函数不是单调的(与可容许性不矛盾)，这条线可能会导致失败。

如果新成本比以前发现的成本高，A*允许重新探索节点。这些情况发生在非单调启发式函数中。

只有当新成本比explored中附加到顶点的成本"大"时，才应该continue，而不是当它只存在于那里时。

---

编辑：(基于评论问题和问题编辑)

对于h=0，A*实际上衰减为Dijkstra的算法，并且由于Dijkstra的算法从不需要修改已经"探索"的节点(当然，假设权重为正)，因此该算法对于这些情况是正确的。

通常，在单调启发式函数中不会重新访问已经访问的节点，因此这不是问题，并且该方法在这些情况下是正确的，但要注意不要将其应用于非单调启发式函数。

Answer 2

是的，这应该有效，我认为这就是AIMA第二版中对A*和UCS的解释。您将在优先级队列中获得重复的状态，但如果您只想生成一个解决方案/路径，则只会返回成本最低的版本。

编辑：误读您的程序。在扩展节点的邻居时，应跳过if child is not in explored步骤。