Think together · Start with a little story
A girl loses a sticker. The robot lists the drawers where it might be, then decides in what order to check them.
Lay out the process
- CandidatesDrawers A, B, and C
- Check ANot there
- Check BFound it
- FinishReport where it was
Search looks through candidate states or positions to find a target that meets a condition.
Define the candidate set, the checking rule, and the stopping condition so you can tell whether any possibilities were missed.
01What exactly is search?
Search means looking for a target among a set of possibilities according to some rules.
For example:
- Find a number in an array.
- Find an exit in a maze.
- Find the next move on a game board.
- Find a path in a graph.
02Is search the same as lookup?
They are related, but search is broader.
Lookup
Often means finding an element in existing data, such as with linear or binary search.
Search
Can also explore a series of states and choices, as in DFS, BFS, and backtracking.
03What should you define before searching?
State
How do you describe where you are now?
Starting point
Where do you begin?
Goal
What counts as success?
Transitions
What can you do next?
Visited record
Which states have already been handled?
04Why record visited states?
States may form a cycle. For example, if A can lead to B and B can lead back to A, failing to record visited states may make the search loop repeatedly.
05Will search always find an answer?
Not necessarily. There may be no state that satisfies the condition.
So a search algorithm must do more than “find an answer”; it must also correctly determine when there is no solution.
06Must you examine every possibility?
Not always.
You can stop after finding the target, or use properties of the problem to rule out many impossible cases and reduce the amount of searching.
What have you learned?
- Search looks for a target among candidate states.
- Search covers more than finding an item in an ordinary array.
- State, starting point, goal, transitions, and visited records are common ingredients.
- A search must handle both solvable and unsolvable cases.
- Avoiding repeated states is an important way to improve search efficiency.
Next: Brute-Force Search: Try Every Possibility
Your turn to try
If you check only drawer A and say the sticker is missing, what is wrong with that conclusion?
Ready? Open to see the explanation
You have not checked B or C, and you have no reason to rule them out. You must check them or use a valid rule to eliminate every remaining candidate.