We learned in the Search lecture notes that search problems have the following components: a starting state, possible actions, a transition model that describes how actions change one state to another, a goal criteria, and a way of calculating the cost of a sequence of actions (a “path” cost). We do not use the path cost when executing uninformed search.
The transition model defines a state space, which can be represented as a directed graph (vertices are states, edges are actions).
For example, consider the 8-puzzle game, which requires that tokens are shifted around until a particular goal state is reached.
Each “state” is a configuration of the puzzle. Each state can be followed by at most four other states, resulting from moving a neighboring token left, right, up, or down into the space (thus shifting the space). If the space is on an edge or in a corner, fewer than four movements are possible.
All searches essentially follow the same algorithm:
1. create an empty list called "closedset"; this list will contain
states that have been visited
2. create a list called "openset" that contains just the starting
state; this list contains states that have not been visited but are
known to exist
3. create an empty map (key/value pairs) called "parents"; this map
contains the previous state of each state that has been visited
4. while the openset is not empty:
a. grab a state from the openset (and remove it);
put it in the closedset (since we're now looking at it)
b. if that state is the goal, hey we're done!
i. return a reconstructed path from the goal state to the start
state (this is easy: recursively grab parent states from the
"parents" map)
c. it's not the goal state; for each next state that is accessible
from here:
i. if this next state is in the closedset (it has been visited
before), ignore it
ii. if this next state is not in the openset, put it in the
openset and record its parent
d. (repeat the loop)
5. if the openset is empty and we never found the goal, oops!
Step 4.a. is a key step. The “algorithm” above gives no guidance
about how to choose the next state to evaluate. You can imagine that
some choices are better (closer to the goal) than others…
A random search, while never practical as far as I know, is
nevertheless interesting to consider as a worst case search. To
program this search, modify step 4.a. so that a random state is
chosen. Given enough time, the goal state should be found, but a
random search will probably take more time (more states are checked)
than any other method.
In breadth-first search (BFS), we want to check all states (which we’ll call “children states”) accessible from the previous state (the “parent state”) before we check states accessible from the children. So if some state is to be checked, say state X, and there are 15 children of state X, then we will check all of those 15 children before checking any of their children.
Breadth-first search appears to search a tree horizontally before searching vertically.
To implement BFS, modify step 4.a. to pick out of the openset the
state that was added earliest (in time). For example, the children
of a state are checked before the their children, because the children
of the original state are discovered earlier. The openset in BFS is
essentially a queue.
Here is an example of BFS operating on the 8-puzzle:
A trivial change to breadth-first search gives us depth-first search
(DFS). For DFS, modify step 4.a. to pick out of the openset the
state that was added last (in time). So in DFS, the openset is
essentially a stack. The purpose is to check the a state’s first
discovered child, and then that child’s first child, etc. before
checking the original state’s second child. DFS appears to search a
tree vertically before it searches horizontally.
Depending on the search problem, DFS may go off into “never-never-land,” seemingly never arriving at a goal state, while say, BFS, arrives at the solution rather quickly. We see this behavior in the 8-puzzle problem because DFS just keeps trying moves that are built off prior moves until it either repeats a state (somewhat unlikely; there are 9! = 362,880 states) or finds the goal. If the true goal is only five moves away from the starting state, then BFS will find this goal in less than 1024 checks while DFS may require, well, 362,880 checks.
To solve the problem of DFS going to “deep” into “never-never-land,”
we can put a limit 4.c. is modified so
that only states that have depth less than the finite constant openset. The depth is calculated as the number of actions or
moves that have been applied to the starting state.
Because it is often difficult to know what the correct depth limit is, the iterative-deepening depth-first search (IDDFS if you like) first tries DFS with depth limit 1; if no goal state is found, DFS is run again with depth limit 2; and so on, until the goal state is found.
Breadth-first search is a good choice when you want to evaluate every
possible choice before deciding an action. BFS ensures that the shortest
path to the goal will be found (shortest in terms of number of moves
or number of “hops”), because no shorter path is left unchecked. However, BFS
suffers when, at each state, there is an enormous number of choices to
consider (a high branching factor
On the other hand, depth-first search might be better if the solution is very “deep,” such as in mazes.
Refer to the search notes (at the bottom) for an explanation of the variables
| Metric | Random | Breadth-first | Depth-first | IDDFS |
|---|---|---|---|---|
| Complete? | Yes | Yes | Yes | Yes |
| Always optimal? (uninformed search) | No | Yes | No | Yes |
| Time complexity | ||||
| Space complexity |
|