Question:
I'm reading about the A* search algorithm so I can implement it in the future. I know it's used to find a path in a graph, but I can't quite visualize how it's done.
However, I'm having difficulty understanding certain aspects of it and having a simple view of its basic functioning. Below are some questions about how this algorithm works.
Questions
- How can the A* algorithm find paths in a graph?
- Is it restricted to a specific type of graph?
- How does it determine the cost between the edges connected at the vertices of the graph?
- Is there any mathematical formula used in this algorithm? If yes, which one?
- What kind of data structure does it use?
Answer:
How can the A* algorithm find paths in a graph?
The algorithm receives:
- the graph
- the starting node
- the final node
- a heuristic function
Starting with the initial node, it takes all the neighbors of the current node and applies the heuristic function. This function returns a number that indicates the distance to the end node (usually used Euclidean distance). The neighbor with the smallest value is closest to the end node, so that neighbor becomes the current node. The same procedure is repeated until the current node is the final node.
Is it restricted to a specific type of graph?
No. As I explained above, it is necessary to get all the neighboring nodes of the current one. In a directed graph are all nodes "leaving" the current one; in an undirected graph are all nodes connected to the current one.
How does it determine the cost between the edges connected at the vertices of the graph?
This is done by the heuristic function. This function is very important, as it will direct the search to the correct path. It depends entirely on how your graph is made, there is no "universal rule" on how to create the heuristic function. It needs to take two nodes of the graph as a parameter and return a number indicating how far away these two nodes are.
For example: If the graph represents a square 2D maze, the indices of the cell represented by the node can be used to calculate the distance. The distance between the nodes of cells (1, 1) and (5, 4) can be calculated by the Euclidean distance formula.
Is there any mathematical formula used in this algorithm? If yes, which one?
This obviously varies from graph to graph. It is your responsibility to understand how the graph is formed to find a mathematical formula for the heuristic function.
What kind of data structure does it use?
A graph can be represented in several ways. The most common are using two nested hashmaps or with a 2D array. The A* algorithm itself is often used with sets and hashmaps. (There is an example implementation on Wikipedia in English).