I'm reading about the A * search algorithm to be able to implement it in the future. I know it is used to find a path in a graph, but I can not see very well how it is done.
However, I am having difficulty understanding certain aspects of it and having a simple view of its basic operation. Here are some questions about how this algorithm works:
How can algorithm A * find paths in a graph?
The algorithm receives:
Starting at the start 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 final node (usually used at Euclidean distance). The neighbor that has the lowest value is the one closest to the final 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, you have to get all the neighboring nodes of the current one. In a directed graph are all nodes "coming out" of the current one; in a non-directed graph are all nodes connected to the current one.
How does it determine the cost between the bound edges at the vertices of the graph?
This is done by the heuristic function. This function is very important because it is the one that will direct the search for the correct path. This depends entirely on how your graph is done, there is no "universal rule" on how to create the heuristic function. It needs to get per-node two nodes from the graph and return a number indicating how far these two nodes are.
For example: If the graph represents a square 2D maze, the cell indices 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 formula of the Euclidean distance .
Is there any mathematical formula used in this algorithm? If so, 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 ones are using two nested hashmaps or a 2D array. The A * algorithm itself is generally used with sets and hashmaps. (You have a example implementation on Wikipedia).
