请求澄清维基百科A*伪代码中映射在网格坐标场景的含义

Hey there! Let's break down those map concepts from the A* pseudocode using your grid-based (XY integer coordinate) scenario—this is one of the most common use cases for A*, so it'll make things super concrete.

First, let's recap the relevant lines from the Wikipedia pseudocode you're referencing:

• came_from ← an empty map
• g_score ← map with default value of Infinity

1. What's the empty map (came_from)? #

In your XY coordinate scenario, this map is a lookup table that tracks which node you came from to reach each explored node. Think of it as a dictionary (if we're talking code terms) where:

• The keys are node coordinates, stored as a pair like (x, y) (e.g., (2, 3), (0, 1)).
• The values are the parent node's coordinates—the node you moved from to get to the key node.

It starts empty because we haven't explored any nodes yet. As we run A*:

• When we move from node (0, 0) to its neighbor (0, 1), we add an entry like (0, 1): (0, 0) to came_from.
• By the end of the algorithm, we can trace backward from the goal node through this map to reconstruct the full path.

2. What's the map with default value of Infinity (g_score)? #

This map keeps track of the actual cost to reach each node from the starting point (that's the g in A*'s f = g + h formula). The "default value of Infinity" means:

• Every node starts with an assumed cost of infinity (we haven't found a path to it yet, so it's effectively unreachable for now).
• The only exception is the starting node, which we immediately set to g_score[start_node] = 0 (since the cost to be at the start is zero).

In practice, for a grid of XY coordinates, you don't need to pre-populate this map with every possible (x, y) pair (that would waste space for large grids). Instead, you use a dynamic structure (like a dictionary) where:

• You only store entries for nodes you've actually calculated a g score for.
• If a node isn't in the dictionary, you treat its g score as infinity.

For example:

• Start at (1, 1): g_score starts with just {(1, 1): 0}.
• When we evaluate neighbor (1, 2), we calculate its g score as 0 + 1 = 1 (assuming each adjacent step has a cost of 1). We then add (1, 2): 1 to g_score.
• Any other node (like (5, 5) if it's a big grid) that we haven't touched yet is considered to have an infinite g score until we reach it.

Quick Clarification #

You were wondering if the "default infinity map" is empty at the start? Sort of—logically, all nodes have infinite cost, but in implementation, we only store the nodes we've processed. The empty map for came_from is literally empty because we haven't tracked any parent nodes yet.

内容的提问来源于stack exchange，提问作者Morgan