Problem Large Graphs CSE 326 Data Structures It is expensive to find optimal paths in large graphs using BFS or Dijkstra s algorithm for weighted graphs How can we search large graphs efficiently by using commonsense about which direction looks most promising Graph Algorithms Graph Search Lecture 23 1 2 Example Example 53nd St 53nd St 52nd St 52nd St G 51st St S 50th St G 51st St S 50th St 2nd Ave 3rd Ave 4th Ave 5th Ave 6th Ave 7th Ave 8th Ave 9th Ave 10th Ave 2nd Ave 3rd Ave 4th Ave 5th Ave 6th Ave 7th Ave 8th Ave 9th Ave 10th Ave Plan a route from 9th 50th to 3rd 51st Plan a route from 9th 50th to 3rd 51st 3 Best First Search 4 Best First Search Open Heap priority queue Criteria Smallest key highest priority h n heuristic estimate of distance from n to closest goal The Manhattan distance x y is an estimate of the distance to the goal It is a search heuristic Best First Search Start Goal test insert Start h Start heap repeat if empty heap then return fail Node deleteMin heap if Goal test Node then return Node for each Child of node do if Child not already visited then insert Child h Child heap end Mark Node as visited end Best First Search Order nodes in priority to minimize estimated distance to the goal Compare BFS Dijkstra Order nodes in priority to minimize distance from the start 5 6 Obstacles Non Optimality of Best First Best FS eventually will expand vertex to get back on the right track Path found by Best first 53nd St 52nd St S 52nd St S 51st St G G 50th St 51st St 2nd Ave 3rd Ave 4th Ave 5th Ave 6th Ave 7th Ave 8th Ave 9th Ave 10th Ave 50th St 2nd Ave 3rd Ave 4th Ave 5th Ave 6th Ave 7th Ave 8th Ave 9th Ave 10th Ave Shortest Path 7 8 Improving Best First A Best first is often tremendously faster than BFS Dijkstra but might stop with a non optimal solution How can it be modified to be almost as fast but guaranteed to find optimal solutions A Hart Nilsson Raphael 1968 Exactly like Best first search but using a different criteria for the priority queue minimize distance from start estimated distance to goal priority f n g n h n f n priority of a node g n true distance from start h n heuristic distance to goal One of the first significant algorithms developed in AI Widely used in many applications 9 10 Optimality of A A in Action h 7 3 h 6 2 Suppose the estimated distance is always less than or equal to the true distance to the goal 53nd St 52nd St heuristic is a lower bound S 51st St G 50th St 2nd Ave 3rd Ave 4th Ave 5th Ave 6th Ave 7th Ave 8th Ave 11 9th Ave H 1 7 10th Ave Then when the goal is removed from the priority queue we are guaranteed to have found a shortest path 12 Application of A Speech Recognition Speech Recognition as Shortest Path Convert to a shortest path problem Simplified Problem Utterance is a layered DAG Begins with a special dummy start node Next A layer of nodes for each word position one node for each word choice Edges between every node in layer i to every node in layer i 1 System hears a sequence of 3 words It is unsure about what it heard For each word it has a set of possible guesses E g Word 1 is one of hi high I What is the most likely sentence it heard Cost of an edge is smaller if the pair of words frequently occur together in real speech Technically log probability of co occurrence Finally a dummy end node Find shortest path from start to end node 13 W11 W12 14 Summary Graph Search W13 Depth First W21 Little memory required Might find non optimal path W23 Breadth First Much memory required Always finds optimal path W22 Iterative Depth First Search Repeated depth first searches little memory required W W3111 Dijskstra s Short Path Algorithm W33 Like BFS for weighted graphs Best First Can visit fewer nodes Might find non optimal path W41 A W43 Can visit fewer nodes than BFS or Dijkstra Optimal if heuristic estimate is a lower bound 15 Dynamic Programming 16 Floyd Warshall for int k 1 k V k for int i 1 i V i for int j 1 j V j if M i k M k j M i j M i j M i k M k j Algorithmic technique that systematically records the answers to sub problems in a table and re uses those recorded results rather than re computing them Simple Example Calculating the Nth Fibonacci number Fib N Fib N 1 Fib N 2 Invariant After the kth iteration the matrix includes the shortest paths for all pairs of vertices i j containing only vertices 1 k as intermediate vertices 17 18 Initial state of the matrix b 2 a 1 4 d a b c d e a 0 2 4 b 0 2 1 3 c 0 d e c 3 e 1 Floyd Warshall for All pairs shortest path 2 1 4 c 3 d 1 e 4 4 a b c d a 0 2 0 4 0 1 b 0 2 1 0 4 c 0 1 0 d 0 4 e 0 M i j min M i j M i k M k j b 2 a 2 e Final Matrix Contents 1 19 20 Network Flows Given a weighted directed graph G V E Treat the edge weights as capacities How much can we flow through the graph CSE 326 Data Structures Network Flow 1 A B 3 9 Network flow definitions 2 Value of a flow E 6 11 4 20 I 22 Conservation Flow entering any vertex must equal flow leaving that vertex f u v 0 for all u except source sink v V 13 Capacity you can t overload an edge f v w c v w 6 12 G 4 H 5 Network flow definitions Define special source s and sink t vertices Define a flow as a function on edges Capacity Conservation D 11 F C 10 21 7 f f s v We want to maximize the value of a flow subject to the above constraints v Saturated edge when f v w c v w 23 24 Network Flows A Good Idea that Doesn t Work Start flow at 0 While there s room for more flow push more flow across the network Given a weighted directed graph G V E Treat the edge weights as capacities How much can we flow through the graph 1 s B 3 9 7 While there s some path from s to t none of whose edges are saturated Push more flow along the path until some edge is saturated H 5 2 6 12 C G 10 D …