We're searching a state graph. These are easiest to visualize when the states are locations, as in this example:
During search, the frontier contains states that have been seen but their outgoing edges have not yet been explored. BFS stores the frontier as a queue; DFS stores it as a stack. Iterative deepening is a hybrid that runs DFS with depth bound that gradually increases. Compared to BFS, iterative deepening does some redundant work but uses less memory.
All these search algorithms must be able to return best path to the solution. So implementations must store best path to each state in the frontier. Typical method is for each state to store a pointer to the previous state in the best path found so far. If you implement DFS using recursive function calls, this is done implicitly by the recursive calling stack.
We're about to see algorithms that explicitly take cost into account. For these, it's often helpful to store the current cost with each state so that (for example) it's easy to sort a list of states by cost.
Basically what it sounds like. Backwards search is like forwards search except that you start from the goal. In bidirectional search, you run two parallel searches, starting from start and goal states, in hopes that they will connect at a shared state.
Only applicable when you have relatively few goal states, known at the start. This often fails, e.g. chess has a huge number of winning board configurations. Also, actions must be easy to run backwards (often true).
Example: James Bond is starting off in central Boston and wants to get to Dr. Evil's lair in Pittsfield, MA. There's a vast number of ways to get out of Boston but only two significant roads going through Pittsfield. In that type of situation, working backwards from the goal might be much better than working forwards from the starting state.
BFS is primarily designed to handle graphs in which all edges have the same cost. If costs don't vary too much, it will tend to find a lost-cost path. But it's only guaranteed to find an optimal path when all edges have the same cost. Uniform Cost Search (UCS) is a modification of BFS which handles edges with varying costs.
Assumptions from now on:
These assumptions are almost always true. If they aren't true, algorithm design and analysis can get much harder in ways that are beyond the scope of this class.
The main change between BFS and UCS is that the frontier is stored as priority queue. In each iteration of our loop, we explore neighbors of the best state (the shortest path length) seen so far.
Example: suppose we are going from Westhampton to Florence in the road graph shown at top. When we look at Westhampton's neighbors, Williamsburg is closer than Northampton. So we'll first get to Florence via Williamsburg, a route that takes 15 miles. However, the best route is 12 miles, via Northampton.
So we need to make a couple changes to ensure that we have really found the best path when we halt and declare success:
Memory requirements are similar to BFS. They can be worse than BFS in some cases, because UCS can get stuck in extended areas of short edges rather than exploring longer but more promising edges.
As an example, consider going from Easthampton to Hatfield in our road map.
As with any of these search algorithms, our priority queue starts off containing Easthampton and we then remove Easthampton from the frontier and add its neighbors. However, since we're doing UCS, we add the neighbors in order of distance, not some arbitrary search ordering (e.g. left to right). Our search (states with distances) now looks like this:
DONE
Easthampton 0
FRONTIER
Northampton 6
Westhampton 10
South Hadley 11
Now we add Northampton's neighbors:
DONE
Easthampton 0
Northampton 6
FRONTIER
Florence 8
Westhampton 10 <-- Not clear if it's before or after Hadley
Hadley 10
South Hadley 11
Now we add Florence's neighbors:
DONE
Easthampton 0
Northampton 6
Florence 8
FRONTIER
Westhampton 10
Hadley 10
South Hadley 11
Hatfield 13 <-- GOAL! But don't stop yet
Williamsburg 14
We have a path to Hatfield, but we can't yet be sure that it's the best one. So we keep going, exploring neighbors of Westhampton, Hadley, and South Hadley.
DONE
Easthampton 0
Northampton 6
Florence 8
Westhampton 10
Hadley 10
South Hadley 11
FRONTIER
Hatfield 13 <-- GOAL
Williamsburg 14
Amherst 14
Chesterfield 19
Now our goal is at the top of the priority queue, so there can't be a better path. So we return the path: Easthampton, Northampton, Florence, Hatfield.
A good search algorithm must be coupled with a good representation of the problem. So transforming to a different state graph model may dramatically improve performance. We'll illustrate this with finding edit distance, and then see another example when we get to classical planning.
Problem: find the best alignment between two strings, e.g. "ALGORITHM" and "ALTRUISTIC". By "best," we mean the alignment that requires the fewest editing operations (delete char, add char, substitute char) to transform the first word into the second. We can get from ALGORITHM to ALTRUISTIC with six edits, producing the following optimal alignment:
A L G O R I T H M
A L T R U I S T I C
D S A A S S
D = delete character
A = add character
S = substitute
For more detail, see Wikipedia on edit distance and Jeff Erickson's notes.
Versions of this task appear in
Each state is a string. So the start state would be "algorithm" and the end state is "altruistic." Each action applies one edit operation, anywhere in the word.
In this model, each state has a very large number of successors. So there are about 289 single-character changes you could make to ALGORITHM, resulting in words like:
LGORITHM, AGORITHM, ..., ALGORIHM, ...
BLGORITHM, CLGORITHM, ....
AAGORITHM, ....
...
ALBORJTHM, ...
....
This massive fan-out will cause search to be very slow.
A better representation for this problem explores the space of partial matches. Each state is an alignment of the initial sections (prefixes) of the two strings. So the start state is an alignment of two empty strings, and the end state is an alignment of the full strings.
In this representation, each action extends the alignment by one character. From each state, there are only three legal moves:
In this specific case, we can pack our work into a nifty compact 2D table.
This algorithm can be adapted for situations where the search space is too large to maintain the full alignment table. for example, we may need to match DNA sequences that are 105 characters long.