Scribd
Upload
5 views2 pages

Graph Search Algorithms Explained

This document discusses graph searching algorithms and best first search. It presents a general graph searching algorithm that can implement either depth first or breadth first search depending on the data structure used for the agenda. For best first search, a heuristic function is needed to estimate how close a node is to the goal. The algorithm is modified for best first search by always removing the element from the agenda that has the smallest heuristic value. If the heuristic is guaranteed to never overestimate, it will find the shortest path.

Uploaded by

Phanindra Babu Pabba
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Graph Search Algorithms Explained

This document discusses graph searching algorithms and best first search. It presents a general graph searching algorithm that can implement either depth first or breadth first search depending on the data structure used for the agenda. For best first search, a heuristic function is needed to estimate how close a node is to the goal. The algorithm is modified for best first search by always removing the element from the agenda that has the smallest heuristic value. If the heuristic is guaranteed to never overestimate, it will find the shortest path.

Uploaded by

Phanindra Babu Pabba
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithms and Complexity 2003 Graph searching algorithms

October 2, 2003

General graph searching algorithm

The text book covers the depth rst and breadth rst algorithms separately, giving separate pseudocode for these two methods of searching a graph. However, we can also use the following algorithm to implement either of these: Initialise agenda with starting node while agenda not empty get v from agenda (pop/dequeue/etc) visit, mark and expand v for every edge vw if w is not marked add w to agenda (push/enqueue/etc) end if end for end while The behaviour of this algorithm will depend on the data structure used for the agenda. If it is a stack, with the last element pushed onto the stack being the rst element popped o it again, the result is a depth rst search. (Check this yourself!) If the agenda is implemented as a queue, with the rst element added to the queue being the rst element taken o it, the result is a breadth rst search. (Again, check this yourself!) Finally, it is also possible to get any other order of searching the graph by removing the elements from the agenda in a dierent order. In particular, if we use a heuristic to guide our search, we can obtain best rst search.

Heuristics and best rst search

For best rst search, we need a heuristic function that will tell us which nodes are the most promising ones to investigate. A heuristic is a guess or an estimate,

in this case an estimate of how close a particular node is to the goal we are searching for. In some applications it is possible to dene a sensible heuristic, which then helps us to nd not just any path to the goal state, but the shortest path. Alternatively, we can also choose the heuristic so that it helps us nd the goal more quickly. In fact, it will usually do both of these things. If we are interested in minimising the remaining search time, the heuristic should be an estimate of the expected remaining distance from the current node to the goal. Alternatively, if we are interested in minimising the total length of the path found, the heuristic should be an estimate of the expected total length from the starting point to the goal. In other words, it should be the sum of the length of the path so far and the length of the path to the goal. Once we have a heuristic function implemented, we can use our search algorithm to implement best rst search as follows: whenever we need to remove an element from the agenda, choose (instead of the rst or the last element) the one for which the heuristic function is smallest. If our heuristic function is such that we are guarranteed that it will never be an overestimate, it is guarranteed to nd the shortest path.

You might also like