Astar可以多次访问节点吗? [英] Can Astar visit nodes more than once?

问题描述

我一直在阅读Wikipedia的Astar 文章.在实现中，他们检查每个节点是否在closed集中，如果是，则跳过该节点.如果启发式是可以接受的，但不同是一致的，是否可能需要两次(或多次)重新访问一个节点以提高其f值? 这是相关代码

I've been reading wikipedia's Astar article. In their implementaion, they check each node if it's in the closed set, and if so they skip it. Isn't it possible, that if the heuristic is admissible but NOT consistent, that we might need to revisit a node twice (or more) in order to improve it's f value? This is the relevant code

for each neighbor in neighbor_nodes(current)
    if neighbor in closedset //This if condition bothers me
        continue
    tentative_g_score := g_score[current] + dist_between(current,neighbor)
    if neighbor not in openset or tentative_g_score < g_score[neighbor] 
        came_from[neighbor] := current 
        g_score[neighbor] := tentative_g_score
        f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
        if neighbor not in openset
            add neighbor to openset

推荐答案

问题的答案在链接页面的伪代码下方，以及该页面的描述"部分中.从伪代码下面的注释中:

The answer to your question is below the psuedocode on the linked page, and also in the Description section on that page. From the remark below the psuedo code:

备注:上面的伪代码假定启发式函数为 单调的(或一致的，请参见下文)，这在许多情况下是很常见的情况 实际问题，例如道路上的最短距离路径 网络.但是，如果假设不成立，则封闭的节点 可以重新发现该设备，并可以提高其成本.换句话说， 如果 解决方案被保证存在，或者如果算法被修改为如此 仅当新节点具有较低的f时，才将它们添加到开放集中 值比任何先前迭代都高.

Remark: the above pseudocode assumes that the heuristic function is monotonic (or consistent, see below), which is a frequent case in many practical problems, such as the Shortest Distance Path in road networks. However, if the assumption is not true, nodes in the closed set may be rediscovered and their cost improved. In other words, the closed set can be omitted (yielding a tree search algorithm) if a solution is guaranteed to exist, or if the algorithm is adapted so that new nodes are added to the open set only if they have a lower f value than at any previous iteration.

所以，是的，伪代码确实假定启发式方法是一致的，如果不一致，则必须对其进行修改.

So yes, the pseudocode does assume the heuristic is consistent and would have to be modified if it was not.

这篇关于Astar可以多次访问节点吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！