Shortest path and Informed Search Brian C. williams 16410-13 October 27th. 2003 Slides adapted from 6.034 Tomas Lozano Perez, Winston, and Russell and Norvig AIMA Assignment R adin Shortest path Cormen leiserson rivest Introduction to Algorithms"Ch 25. 1-.2 d search and explorati AIMA Ch 4.1-2 Homework Online problem set #6 due monday November Brian Williams, Spring 03
Shortest Path and Informed Search Brian C. Williams 16.410 - 13 October 27th, 2003 Slides adapted from: 6.034 Tomas Lozano Perez, Winston, and Russell and Norvig AIMA Brian Williams, Spring 03 2 Assignment • “Introduction to Algorithms” Ch. 25.1-.2 AIMA Ch. 4.1-2 • 3rd . Reading: Cormen Leiserson & Rivest, Homework: Brian Williams, Spring 03 – Shortest path: – Informed search and exploration: – Online problem set #6 due Monday November 1
How do we maneuver ImagestakenfromNasa'Swebsitehttp://www.nasa.gov/ Roadmaps are an effective state space abstraction Brian Williams, Spring 0 Courtesy of U.S. Geological survey
Brian Williams, Spring 03 3 How do we maneuver? 4 Roadmaps are an effective state space abstraction Brian Williams, Spring 03 Courtesy of U.S. Geological survey. Images taken from NASA's website: http://www.nasa.gov/
Weighted Graphs and Path Lengths 2|3 6 Graph G= Weight function w:E→ Path Path weight (p)=∑w(v1,v1) Shortest path weight b(u, v)=min w(p): u-P v) else oo Outline Creating road maps for path p Exploring roadmaps Shortest paths Single soure Dijkstra; s algorithm med searc · Uniform cost search Greedy search · Beam search Hill climbing Avoiding adversaries lext Lecture) Brian Williams, Spring 03
6 5 u v 1 x y 2 10 5 7 9 2 3 4 6 s Weighted Graphs and Path Lengths Graph G = Weight function w: E ĺ Path p = Path weight w(p) = Ȉ w(vi-1,vi ) Shortest path weight į(u,v) = min {w(p) : u ĺp v } else Outline • planning • Shortest Paths – • – • • • • • • Creating road maps for path Exploring roadmaps: Single Source Dijkstra;s algorithm Informed search Uniform cost search Greedy search A* search Beam search Hill climbing Avoiding adversaries – (Next Lecture) Brian Williams, Spring 03 Brian Williams, Spring 03
Single Source Shortest Path 2|3 6 Problem: Compute shortest path to all vertices from source s Brian williams, Spning 03 Single Source Shortest Path 2|3 7 Problem: Compute shortest path to all vertices from source estimate d v] estimated shortest path length from s to ian williams, Spring 03
Single Source Shortest Path u v 1 10 9 2 3 4 6 s 7 5 2 x y Problem: Compute shortest path to all vertices from source s Brian Williams, Spring 03 7 Single Source Shortest Path u v 1 10 8 9 9 2 3 4 6 s 0 7 5 5 7 2 x y Problem: Compute shortest path to all vertices from source s • estimate d[v] estimated shortest path length from s to v Brian Williams, Spring 03 8
Single Source shortest Path 6 Problem: Compute shortest path to all vertices from source s estimate dv estimated shortest path length from s to v predecessor iv final edge of shortest path to v induces shortest path tree Brian williams, Spning 03 Properties of Shortest Path 7 Subpaths of shortest paths are shortest paths S→pv ian williams, Spring 03 u→pv
8 9 Single Source Shortest Path u v 1 10 9 0 2 3 4 6 s 7 5 5 7 2 x y Problem: Compute shortest path to all vertices from source s • estimate d[v] estimated shortest path length from s to v • predecessor ʌ[v] final edge of shortest path to v • induces shortest path tree Brian Williams, Spring 03 9 Properties of Shortest Path u v 1 10 8 9 9 2 3 4 6 s 0 7 5 5 7 2 x y • Subpaths of shortest paths are shortest paths. • s ĺp v = • s ĺp u = • s ĺp x = • x ĺp v = •x ĺp v = Brian Williams, Spring 03 10 • u ĺp v =
Properties of Shortest Path 416 Corollary: Shortest paths are grown from shortest paths The length of shortest path s→pu→v is S(s, v)=8(s, m)+w(u, v) v∈Eδ(s,v)≤δ(s,u)+w(u) Idea: Start With Upper bound 23 6 Initialize-Single-Source(G, s) 1. for each vertex vE v/G/ do dul π[v]←ML 4.ds7←0 O(v) ian williams, Spring 03
8 9 Properties of Shortest Path u v 1 10 9 0 2 3 4 6 s 7 5 5 7 2 x y Corollary: Shortest paths are grown from shortest paths. • The length of shortest path s ĺp u ĺ v is į(s,v) = į(s,u) + w(u,v). • E į(s,v) į(s,u) + w(u,v) Brian Williams, Spring 03 11 Idea: Start With Upper Bound u v 1 10 9 2 3 4 6 s 0 7 5 2 x y Initialize-Single-Source(G, s) 1. for each vertex v V[G] 2. do d[u] ĸ 3. ʌ[v] ĸ NIL 4. d[s] ĸ 0 O(v) Brian Williams, Spring 03 12
Relax Bounds to shortest path Relax(u, v) Relax(u, v) 7 Relax(u, v, w) 1. if du]+w(u, v<dvI 2 dod/vy/←a]+ v7← Properties of relaxing bounds 2 2 Relax(u, v) Relax(u, v) (2 After calling Relax(u, v, w) d]+w(u,v)≥y d remains a shortest path upperbound after repeated calls Relax Once d[v] is the shortest path its value persists ian williams, Spring 03
Relax Bounds to Shortest Path u v u v 2 2 5 9 5 6 Relax(u, v) Relax(u, v) u v u v 2 2 5 7 5 6 Relax (u, v, w) 1. if d[u] + w(u,v) < d[v] 2. do d[v] ĸ d[u] + w(u,v) 3. ʌ[v] ĸ u Brian Williams, Spring 03 13 Properties of Relaxing Bounds u v u v 2 2 5 9 5 6 Relax(u, v) Relax(u, v) u v u v 2 2 5 9 5 6 After calling Relax(u, v, w) • d[u] + w(u,v) d[v] d remains a shortest path upperbound after repeated calls to Relax. Once d[v] is the shortest path its value persists Brian Williams, Spring 03 14
Dijkstras algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes y Q=s,u, v, x,yl Vertices to relax Vertices with shortest path value a williams, Spning 03 Dijkstras algorithm Assume all edges are non-negative Idea: Greedily relax out arcs of minimum cost nodes 46 Q=x,y, u, v) Vertices to relax Vertices with shortest path value ian williams, Spring 03
Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 9 0 2 3 4 6 s 7 5 2 x y Q = {s,u,v,x,y} Vertices to relax S = {} Vertices with shortest path value Brian Williams, Spring 03 15 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 9 2 3 4 6 s 0 7 5 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Brian Williams, Spring 03 16
Dijkstras algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes y Q=x,y, u, v! Vertices to relax s={s} Vertices with shortest path value Shortest path edge n[]=arrows Dijkstra's algorithm Assume all edges are non-negative Idea: Greedily relax out arcs of minimum cost nodes 10 46 0 Q=x,y, u, v) Vertices to relax Vertices with shortest path value Shortest path edge Ilvl=arrows ian williams, Spring 03
Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 10 9 0 2 3 4 6 s 7 5 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 17 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 10 9 2 3 4 6 s 0 7 5 5 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 18
Dijkstras algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes y Q=x,y, u, v! Vertices to relax s={s} Vertices with shortest path valu Shortest path edge nlv=arrows Dijkstras algorithm Assume all edges are non-negative Idea: Greedily relax out arcs of minimum cost nodes 8 14 46 Q=y, u,\ Vertices to relax Vertices with shortest path value Shortest path edge Ilvl=arrows ian williams, Spring 03
Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 10 9 0 2 3 4 6 s 7 5 5 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 19 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 8 14 9 2 3 4 6 s 0 7 5 5 7 2 x y Q = {y,u,v} Vertices to relax S = {s, x} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 20
