3

标准方法如下：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，因此忽略其他成本较高的重复状态是无害的。

合理吗？

更新

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

4

2 回答 2

3

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

  > if node is in explored then continue

如果启发式函数不是单调的（与可接受性不矛盾），这条线可能会导致失败。

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

continue仅当新成本“更大”时，才应该与附加到顶点 in 的成本相比explored，而不是仅在它存在的情况下。

编辑：（基于评论问题和问题编辑）

对于h=0，A* 实际上会衰减到 Dijkstra 的算法中，并且由于 Dijkstra 的算法永远不需要修改已经“探索”的节点（当然，假设权重为正） - 该算法对于这些情况是正确的。

一般来说，重新访问已经访问过的节点不会在单调启发式函数中发生，因此这不是问题，并且该方法对于这些情况是正确的 - 但请注意不要将其与非单调启发式函数一起应用。

于 2012-10-02T13:37:43.457 回答
1

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

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

于 2012-10-02T13:34:27.850 回答