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

问题描述

我一直在阅读维基百科的 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:

备注:上面的伪代码假设启发式函数是单调的(或一致的，见下文)，这是许多情况下的常见情况实际问题，例如道路中的最短距离路径网络.但是，如果假设不成立，则关闭的节点集可能会被重新发现并提高其成本.换句话说，如果 a 可以省略闭集(产生树搜索算法)解决方案保证存在，或者如果算法如此适应只有当新节点具有较低的 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屋！