Process
Like all informed search algorithms, it first searches the routes that appear to be most likely to lead towards the goal. What sets A* apart from a greedy best-first search is that it also takes the distance already traveled into account; the part of the heuristic is the cost from the starting point, not simply the local cost from the previously expanded node.
Starting with the initial node, it maintains a priority queue of nodes to be traversed, known as the open set. The lower for a given node, the higher its priority. At each step of the algorithm, the node with the lowest value is removed from the queue, the and values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a goal node has a lower value than any node in the queue (or until the queue is empty). (Goal nodes may be passed over multiple times if there remain other nodes with lower values, as they may lead to a shorter path to a goal.) The value of the goal is then the length of the shortest path, since at the goal is zero in an admissible heuristic. If the actual shortest path is desired, the algorithm may also update each neighbor with its immediate predecessor in the best path found so far; this information can then be used to reconstruct the path by working backwards from the goal node. Additionally, if the heuristic is monotonic (or consistent, see below), a closed set of nodes already traversed may be used to make the search more efficient.
Read more about this topic: A* Search Algorithm
Famous quotes containing the word process:
“In contrast to revenge, which is the natural, automatic reaction to transgression and which, because of the irreversibility of the action process can be expected and even calculated, the act of forgiving can never be predicted; it is the only reaction that acts in an unexpected way and thus retains, though being a reaction, something of the original character of action.”
—Hannah Arendt (1906–1975)
“I’m not suggesting that all men are beautiful, vulnerable boys, but we all started out that way. What happened to us? How did we become monsters of feminist nightmares? The answer, of course, is that we underwent a careful and deliberate process of gender training, sometimes brutal, always dehumanizing, cutting away large chunks of ourselves. Little girls went through something similarly crippling. If the gender training was successful, we each ended up being half a person.”
—Frank Pittman (20th century)
“We are in the process of creating what deserves to be called the idiot culture. Not an idiot sub-culture, which every society has bubbling beneath the surface and which can provide harmless fun; but the culture itself. For the first time, the weird and the stupid and the coarse are becoming our cultural norm, even our cultural ideal.”
—Carl Bernstein (b. 1944)