Question? Leave a message!




A* Search Algorithm

A* Search Algorithm
ECE 250 Algorithms and Data Structures A search Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.A search 2 Outline In this topic, we will look at the A search algorithm: – It solves the singlesource shortest path problem – Restricted to physical environments – First described in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael – Similar to Dijkstra’s algorithm – Uses a hypothetical shortest distance to weight the pathsA search 3 Background Assume we have a heuristic lower bound for the length of a path between any two vertices E.g., a graph embedded in a plane – the shortest distance is the Euclidean distance ―as the crow flies‖ – use this to guide our search for a path ―as the fox runs‖A search 4 Idea Consider this map of SloveniaA search 5 Idea Suppose we want to go from Kamnik to BohinjA search 6 Idea A lower bound for the length of the shortest path to Bohinj is h(Kamnik, Bohinj) = 53 kmA search 7 Idea Any actual path must be at least as long as 53 kmA search 8 Idea Suppose we have a 28 km shortest path from Kamnik to Kranj: d(Kamnik, Kranj) = 28 km 28 kmA search 9 Idea A lower bound on the shortest distance from Kranj to the destination is now h(Kranj, Bohinj) = 32 km 28 kmA search 10 Idea Thus, we weight of the path up to Kranj is w(Kranj) = d(Kamnik, Kranj) + h(Kranj, Bohinj) = 60 km 28 kmA search 11 Idea Any path extending this given path to Bohimj must be at least 60 km 28 kmA search 12 Idea The value w(Kranj) represents the shortest possible distance from Kamnik to Bohinj given that we follow the path to Kranj As with Dijkstra’s algorithm, we must start with the null path starting at Kamnik: w(Kamnik) = d(Kamnik, Kamnik) + h(Kamnik, Bohimj) = 0 km + 53 km Bohimj KamnikA search 13 Algorithm Description Suppose we are finding the shortest path from vertex a to a vertex z The A search algorithm initially: – Marks each vertex as unvisited – Starts with a priority queue containing only the initial vertex • The priority of any vertex v in the queue is the weight w(v) which assumes we have found the a shortest path to v • Shortest weights have highest priorityA search 14 Algorithm Description The algorithm then iterates: – Pops the vertex u with highest priority • Mark the vertex u of the path as visited – Ignore all visited adjacent vertices v – For each remaining unenqueued adjacent vertex v: • Push v with w(v) = d(a, u) + d(u, v) + h(v, z) – For each enqueued adjacent vertex v: • Determine if w(v) = d(a, u) + d(u, v) + h(v, z) is less than the current weight/priority of v, and if so, update the path leading to v and its priority Continue iterating until the item popped from the priority queue is the destination vertex zA search 15 Comparison of Priorities Suppose we have a path with w(Smarca) = 4 km + 52 km = 56 km 4 kmA search 16 Comparison of Priorities We can extend this path to Moste: w(Moste) = 4 km + 5 km + 48 km = 57 km 9 kmA search 17 Comparison of Priorities We can also extend this path to Menges: w(Menges) = 4 km + 4 km + 51 km = 59 km 8 kmA search 18 Comparison of Priorities The smaller weight path to Moste has priority—extend it first 9 kmA search 19 Comparison with Dijkstra’s Algorithm This differs from Dijkstra’s algorithm which gives weight only to the known path – Dijkstra would chose Menges next: d(Kamnik, Moste) = 9 km 8 km = d(Kamnik, Menges) Difference: – Dijkstra’s algorithm radiates out from the initial vertex – The A search algorithm directs its search towards the destinationA search 20 Comparison with Dijkstra’s Algorithm Graphically, we can suggest the behaviour of the two algorithms as follows: – Suppose we are moving from a to z: a a z z Representative search patterns for Dijkstra’s and the A search algorithmsA search 21 Comparison with Dijkstra’s Algorithm Dijkstra’s algorithm is the A search algorithm when 0 uv  h(u,v) using the discrete distance  1 uv  – No vertex is better than any other vertex a a z z Representative search patterns for Dijkstra’s and the A search algorithmsA Search Algorithm Optimally Guarantees The A search algorithm will not always find the optimal path with a poor heuristic distance – Find the shortest path from A to C: • B is enqueued with weight w(B) = 1 + 5 = 6 • C is enqueued with weight w(C) = 3 + 0 = 3 – Therefore, C is dequeued next and as it is the destination, we are finished Reference: Andrew Moore, Carnegie Mellon University 22A Search Algorithm Admissible Heuristics This heuristic overestimates the actual distance from B to C – The Euclidean distance doesn’t suffer this problem: The path the crow flies is always shorter than the road the wolf runs Reference: Andrew Moore, Carnegie Mellon University 23A Search Algorithm Admissible Heuristics Admissible heuristics h must always be optimistic: – Let d(u, v) represent the actual shortest distance from u to v – A heuristic h(u, v) is admissible if h(u, v) ≤ d(u, v) – The heuristic is optimistic or a lower bound on the distance Using the Euclidean distance between two points on a map is clearly an admissible heuristic – The flight of the crow is shorter than the run of the wolf 24A search 25 Optimality Conditions The effectiveness of the A search algorithm depends on the heuristic h(v) Can be shown to run in polynomial time if h(u, v) – d(u, v) = O(ln(d(u, v))) where d(u, v) is the length of the actual shortest path – I.e., doubling the length of the optimal solution only increases the error by a constant – Not likely with a road map and the Euclidean distanceA Search Algorithm The N Puzzle Consider find the solution to the following puzzle – Take a random permutation of 8 or 15 numbered tiles and a blank formed in a rigid square Reference: Andrew Moore, Carnegie Mellon University 26A Search Algorithm The N Puzzle You are allowed to move a tile adjacent to the blank into the location of the blank 27A Search Algorithm The N Puzzle The objective is to find a minimum number of moves which will transform the tiles into a standard solution 28A Search Algorithm The N Puzzle There are 9 and 16 initial permutations – Half of these, through a sequence of moves, can be transformed into the desired solutions 29A Search Algorithm The N Puzzle Each solution defines a vertex in a graph with edges denoting allowable moves – It is not a tree, but the smallest cycle has a length of 12 • E.g., cycle 8, 7, and 3 30A Search Algorithm The N Puzzle The graph of solvable eight puzzles has: – 181 440 vertices – 241 920 edges The fifteen puzzle graph has: – 10 461 394 944 000 vertices – 15 692 092 416 000 edges In general and in the limit: – (N + 1)/2 vertices – (N + 1) edges 31A Search Algorithm The N Puzzle Finding a solution requires one to find the shortest path – All edges have weight 1 Dijkstra’s algorithm is painfully slow – This puzzle requires that 179680 vertices be searched To use the A search, we need a heuristic lower bound on the distance 32A Search Algorithm The N Puzzle We will consider three distances which we will use with the A search: – The discrete distance • If two objects are equal, the distance is 0, otherwise it is 1 – The Hamming distance • The number of tiles (including the blank) which are in an incorrect location – The Manhattan distance • The sum of the minimum number of moves required to put a tile in its correct location 33A Search Algorithm The N Puzzle For example, consider this permutation: – It does not equal the solution, so the discrete distance is 1 – 8 out of 9 tiles/blanks are in the incorrect location; therefore the Hamming distance is 8 – It requires 2 + 0 + 4 + 2 + 1 + 1 + 2 + 3 + 1 = 16 moves to move each tile into the correct location, therefore the Manhattan distance is 16 34A Search Algorithm The N Puzzle As discussed before, the discrete distance does not improve the situation: it is equivalent to Dijkstra’s algorithm Using the same permutation as before: – The Hamming distance isn’t much better: • It reduces the vertices searched from 179 680 to 178 005 • It is only useful when we are very close to the actual solution – The Manhattan distance, however, allows the A search to find the minimal path with only 6453 vertices searched 35A search 36 The N Puzzle How much better is it to use the Manhattan distance over the Hamming or discrete – With the Hamming distance, there is only a small change – For 100 random puzzles, we have a plot the number of vertices visited using the discrete distance versus the number of vertices visited using the Hamming distance – The line is the identity function – The colour, blue to red, indicates the length of the solution; from 13 to 28A search 37 The N Puzzle However, comparing the number of vertices visited when using the Manhattan distance, there is a significant reduction by a factor of almost 100 – A more significant improvement with shorter pathsA search 38 The N Puzzle An implementation of N puzzles are located at http://ece.uwaterloo.ca/dwharder/aads/Algorithms/Npuzzles/ This includes: – An N puzzle class: Npuzzleint N – An updatable heap class: Updatableheaptypename T, int MA search 39 Summary This topic has presented the A search algorithm – Assumes a hypothetical lower bound on the length of the path to the destination – Requires an appropriate heuristic • Useful for Euclidean spaces (vector spaces with a norm) – Faster than Dijkstra’s algorithm in many cases • Directs searches towards the solutionA search 40 References Wikipedia, http://en.wikipedia.org/wiki/Asearchalgorithm 1 Andrew Moore, Carnegie Mellon University, ―A Heuristic Search‖, http://www.autonlab.org/tutorials/astar08.pdf nd 2 Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 2 Ed., Prentice Hall, Chapters 4 and 5. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment