What's a search problem?
Bad news! Within the last 2 days, someone stole your bike.
You want to find out when.
If you can find the timestamp, you can identify the thief (and maybe the police can arrest them). However, there are 2 days worth of CCTV film to watch to pinpoint the time of the theft. 1 2
That's your search problem -- you need to find 1 thing in an ocean of data.
Instead of watching every minute of CCTV recording, you use a search algorithm to find the time the thief struck.
You pull up the halfway point in the recording. Is the bike still there? Was it stolen yet?
No, your bike is gone.
Now you know that your bike was stolen within the first day of CCTV footage. There is no point in looking for the thief in the second half of the recording. The theft already happened. The thief isn't coming back.
In one simple check, you halved the amount of information we had to search through. You started with 2 days (48 hours) of film, and now know you only need to look through the first 24 hours.
Let's repeat that search technique.
You know the bike was stolen in the first 24 hours of the recording. You jump to the 12 hour mark in the recording. The bike is where you left it. The theft hadn't occurred yet.
The thief stole your bike between the 12th and 24th hour in the CCTV footage.
In 2 steps, you quartered the amount of time you had to search. You repeatedly check the halfway point in the possible period of the theft. Quickly, you discover when the thief stole your bike.
In this example, you see the binary search algorithm in action to crack the search problem.
Here's what you need to know to address a search problem:
- set of states
- the start state
- the goal state
- how to get to the next state (a function)
When searching for your bike, you know the bike could either be:
- where you left it
- actively being stolen
- missing You are starting with your bike missing and what to find the start, the time, when the thief stole your bike. You use the binary search algorithm to move through the film recording to find a change in the bike's state.
Search problems are unique because you often have heaps of information, but don't know how to sift through it.
You know all the possible states you could end up in. You know which of those possible states you want. The problem is you don't know how to get there.
What steps should you take? How do you pick what step is best when you have many options?
In many problems, you might not know what end state you desire? You don't know what you are pursuing. The challenge here instead is knowing what path to take.
Simply: a search problem is how to find Y in X 3.
Other interesting examples of search problems:
six degrees of separation: everyone human on this planet is 6 or fewer social connections away from any other person on the planetwikipedia game: how can we get from one wikipedia page to another seemingly unrelated page in as few steps as possible?- ex: if you start at Obi-Wan Kenobi's page, how many links do you need to click to get to Search Problem?