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:
“The moralist and the revolutionary are constantly undermining one another. Marx exploded a hundred tons of dynamite beneath the moralist position, and we are still living in the echo of that tremendous crash. But already, somewhere or other, the sappers are at work and fresh dynamite is being tamped in place to blow Marx at the moon. Then Marx, or somebody like him, will come back with yet more dynamite, and so the process continues, to an end we cannot foresee.”
—George Orwell (1903–1950)
“You can read the best experts on child care. You can listen to those who have been there. You can take a whole childbirth and child-care course without missing a lesson. But you won’t really know a thing about yourselves and each other as parents, or your baby as a child, until you have her in your arms. That’s the moment when the lifelong process of bringing up a child into the fold of the family begins.”
—Stella Chess (20th century)
“Because her instinct has told her, or because she has been reliably informed, the faded virgin knows that the supreme joys are not for her; she knows by a process of the intellect; but she can feel her deprivation no more than the young mother can feel the hardship of the virgin’s lot.”
—Arnold Bennett (1867–1931)