COMP1927 - (Graph) Searching

There are many ways of searching and traversing a tree, graph or other data structure in order to find the shortest path. The two main groups are set up here.

Uninformed Searches

There are two common uniformed searches; Breadth First Search and Depth First Search. Their goal is to locate a node (or path to a node) in a tree or graph. They do this by trying every possible path to the node in the order they see them.

Informed Searches

Informed searches work by collecting data and adjusting the route to take that into account. Data comes in the form of heuristics, whereby at each stage the probability of reaching the goal is calculated and the stage with the highest probability (lowest distance from it) is looked at next.

When we talk about informed shortest path searches here we normally mean A*.

Reasons For Informed Searches

Heuristics are useful when solutions are too complex (or time/memory intensive) to brute-force, or when due to the nature of the problem there is no exact solution.

Problems With Informed Searches

Any data we receive will have potential flaws (if it didn't we wouldn't need to search like this), which means that it could end up taking us longer than optimal to reach our goal.

Strategies To Reduce Problems

By using a globally-based heuristic (i.e. examining the probability of reaching the goal) we can ensure that we don't use a flawed-greedy approach (i.e. basing guesses locally on what is the best state at every time - e.g. picking the cheapest edge which may end up as the longest path).