Question? Leave a message!

A* Search Algorithm

a* search algorithm in artificial intelligence ppt and a search algorithm example ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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 © 2006-2013 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 single-source 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 algorithms