解释在维基百科上找到的瓦片网格应用程序中的 A* 伪代码

Question

我希望有人能帮助我澄清一下这个算法。下面是维基百科上为 A* 算法列出的伪代码。我很困惑 "an empty map" 和 "map with default value of Infinity" 在这种情况下是什么。如果节点是 xy 坐标，节点之间的路径是相邻的 xy 坐标（每个坐标都是整数），那么我可以得到关于在这种情况下地图是什么的解释吗？它会是一个空的坐标数组吗？那么我将如何表示以无穷大为值的地图呢？代码中有什么相关性。抱歉，如果这个问题不太适合这里，我只是想请熟悉 A* 算法的人提供更好的解释。

function A*(start, goal)
// The set of nodes already evaluated
closedSet := {}

// The set of currently discovered nodes that are not evaluated yet.
// Initially, only the start node is known.
openSet := {start}

// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := an empty map

// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity

// The cost of going from start to start is zero.
gScore[start] := 0

// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity

// For the first node, that value is completely heuristic.
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        // Ignore the neighbor which is already evaluated.

        if neighbor not in openSet  // Discover a new node
            openSet.Add(neighbor)

        // The distance from start to a neighbor
        //the "dist_between" function may vary as per the solution requirements.
        tentative_gScore := gScore[current] + dist_between(current, neighbor)
        if tentative_gScore >= gScore[neighbor]
            continue        // This is not a better path.

        // This path is the best until now. Record it!
        cameFrom[neighbor] := current
        gScore[neighbor] := tentative_gScore
        fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) 

return failure

这里是 reconstruct_path() 函数：

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

来源：wikipedia

Answer 1

I am very confused as to what "an empty map" and "map with default value of Infinity" are in this case. In the case that the nodes are xy coordinates, and the paths between the nodes are an adjacent xy coordinate (every coordinate being a whole number), then could I receive an explanation on what a map would be in that case? Would it be an empty array of coordinates? How would I represent map with infinity as its value then?

在这种情况下，对于 "map" 这个词，您不应该想到普通英语中的地图之类的东西（例如该区域的概览）。映射只是一种数据结构，您可以在其中存储 Key-Value 对，然后可以高效地查找任何给定键的值。有关这方面的更多信息，请参阅 tag info 页面。

当他们将 cameFrom 初始化为空地图时，他们只是表示地图最初还不包含任何 Key-Value 对。稍后在代码中，行

cameFrom[neighbor] := current

表示它们将(neighbor, current)存储为Key-Value对，其中neighbor是Key，current是value。存储这对可以稍后在 reconstruct_path() 函数中有效地重建路径。

当他们将 gScore 初始化为默认值为无穷大的映射时，这最初也只是一个空映射（不包含对）。但是，对于 "default value of infinity"，它们意味着如果您尝试使用尚不存在的键从中查询值，它将 return 无穷大作为值（默认值）。

在下面的代码行中

gScore[start] := 0

他们将 (Key, Value) 对 (start, 0) 添加到映射中。因此，在那之后，如果您要询问地图 Key = start 的值是什么，您会得到 0。如果您对任何其他键要求相同的值，您将获得默认值无穷大，因为此时代码中它不包含任何其他键（当然，随着添加更多对，稍后会发生变化） .

解释在维基百科上找到的瓦片网格应用程序中的 A* 伪代码

Explanation the A* pseudocode found on Wikipedia in a tile grid application

dictionary

pseudocode

a-star