algorithm - 将 A* 更改为 dijkstra's

Question

function A*(start, goal)

closedSet := {}

openSet := {start}

cameFrom := an empty map

gScore := map with default value of Infinity

gScore[start] := 0

fScore := map with default value of Infinity

fScore[start] := heuristic_cost_estimate(start, goal)

while openSet is not empty
    current := the node in openSet having the lowest fScore[] value
    if current = goal
        return reconstruct_path(cameFrom, current)

    openSet.Remove(current)
    closedSet.Add(current)

    for each neighbor of current
        if neighbor in closedSet
            continue    

        if neighbor not in openSet  
            openSet.Add(neighbor)

        tentative_gScore := gScore[current] + dist_between(current, neighbor)
        if tentative_gScore >= gScore[neighbor]
            continue        

        cameFrom[neighbor] := current
        gScore[neighbor] := tentative_gScore
        fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) 

return failure

function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
    current := cameFrom[current]
    total_path.append(current)
return total_path

如果我采用这个 A* 算法而不是从 openset 中获取最低的 fScore，而是获取最低的 gscore 甚至不考虑 fScore 是否会有效地使这个 dijksta 的？

Answer 1

Dijkstra 的最短路径算法是 A* 的一个特例，其中启发式为零，尽管 Dijkstra 的算法(1958 年)是在 10 年前构思出来的。 A* 根据 f(v) 贪婪地选择下一个要查找的顶点，其中 f(v) = h(v) + g(v)。如果将启发式 (h(v)) 设置为零，A* 将变为仅考虑当前成本 (g(v)) 选择顶点，并且您可以实现将知情的 A* 转换为非知情的 Dijkstra。

简而言之，我对你的问题的回答是"is"。