Main content
Course: Computer science theory > Unit 1
Lesson 1: Intro to algorithmsRoute-finding
Sometimes, very different-sounding problems turn out to be similar when you think about how to solve them. What do Pac-Man, the royal family of Britain, and driving to Orlando have in common? They all involve route-finding or path-search problems:
- How is the current Prince William related to King William III, who endowed the College of William and Mary in 1693?
- What path should a ghost follow to get to Pac-Man as quickly as possible?
- What's the best way to drive from Dallas, Texas to Orlando, Florida?
We have to be given some information to answer any of these questions.
For example, a family tree of the royal family of Britain would show connections between people who were directly related. Prince William is the son of Charles Philip Arthur Windsor. Charles is the son of Queen Elizabeth II. The problem is to find a short chain on the family tree connecting Prince William and William III, using these direct connections. As you can see from the tree below, it might take quite a few connections.
For Pac-Man, we need a map of the maze. This map shows connections between adjacent open squares in the maze—or lack of connections, if there is a wall in between—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
In order to find a driving route from Dallas to Orlando, we might use a map of the United States, showing connections, roads, between nearby cities. No single road directly connects Dallas to Orlando, but several sequences of roads do.
Exploring a maze
Maze games are fun, so let's delve deeper into one. In our game, the main character can navigate to destinations in a maze.
As the human player, you control the main character by clicking on the next destination in the maze, and the computer figures out how to move the character there. The destination is marked with a red rectangle labeled "GOAL", and the character starts off on their first destination, the start square. Try playing it below:
Notice how the character moved to the goal? To make that happen, the program needs to determine the precise set of movements that the character should follow to get to where the user clicked and then animate those movements. There may be multiple paths for the character to follow, and the program needs to choose the best of those paths.
Before deciding on an algorithm, the movement rules first need to be established: walls are made of gray squares and legal locations to travel are empty. In each step, the character can move from one square to an adjacent square. This character, like a chess rook, cannot move diagonally.
Here's the idea behind the algorithm that this program uses: move 1 square closer to the goal—the place the user clicked on—in each step. But what does "closer to the goal" mean? Traveling in a straight line toward the goal will often cause the character to smack into a wall. The algorithm needs to determine which of the surrounding squares are indeed "closer to the goal", and we can do that by assigning a "cost" to each square that represents the minimum number of steps the character would have to take to get from that vertex to the goal. Here's an algorithm for assigning a cost to each square:
- Start on the goal square. How far is the goal from the goal? Zero steps, mark the goal with the number 0.
- Find all squares in the maze that are exactly one step away from the goal. Mark them with the number 1. In this maze, if the goal is the exit square, then there is only one square that is exactly one step away.
- Now find all squares in the maze that are exactly two steps away from the goal. These squares are one step away from those marked 1 and have not yet been marked. Mark these squares with the number 2.
- Mark all squares in the maze that are exactly three steps away from the goal. These squares are one step away from those marked 2 and have not yet been marked. Mark these squares with the number 3.
- Keep marking squares in the maze in order of increasing distance from the goal. After marking squares with the number
Eventually, the algorithm marks the square where the character starts. The program can then find a path to the goal by choosing a sequence of squares from the start such that the numbers on the squares always decrease along the path. If you view the number as the height of the square, it would be like going downhill.
You can play through the cost-marking algorithm below. Click "Restart algorithm" to start the steps over.
What if the user were trying to get from the start square to the goal? Using the square-marking algorithm, the start square is 13 steps away from the goal. Here's a picture showing the connections between possible locations for the character, the start, the goal, and the shortest distance of each location from the goal:
There's a square immediately to the south of the start that is only 12 steps from the goal. So the first move is "south". South of that square is an 11. South again. South again to a 10. Then east twice to an 8. North to a 7, east to a 6, then north five times to a 2. Finish up by going west once, to a 1, and finally north once, to the goal.
We won't discuss exactly how to implement this maze search algorithm right now, but you might find it fun to think about how you might represent the maze and the character using JavaScript and how you might implement the algorithm.
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Want to join the conversation?
I understand everything except step five, talking about the number k and assigning things to k + 1; went over my head a bit.(146 votes)
It bascially just means that you continue assigning cost function to further squares. Once you're done marking squares with cost 3 you move to squares with cost 3+1 = 4. And so on. "k" is just variable to denote cost of square that you marked last.(269 votes)
Would it not be equal or better in efficiency to step from both ends?
start = 0 , goal = n
Set values for each step...
+ 1 , stepping from start
- 1 , stepping from goal
Then solve for 'n' when a square is given a value by both paths.
In this case, one of the 7's in the bottom right corner would get picked.
You get n - 6 = 7 or n - 7 = 6 , depending on which path gave the square value first. Then you can stop assigning values to extraneous squares.(29 votes)
That's what is known as a bidirectional search, and it is more efficient. https://en.wikipedia.org/wiki/Bidirectional_search
If you had a maze that was constructed so that every square had the same number of unvisited neighbors (constant branching factor), the search would run in the square root of the time that the other search would.
Of course, a bidirectional search requires knowing both the starting point and the goal. Unfortunately, we often only know the starting point and we are searching for the goal.(24 votes)
So... I'm good with all that. But I played the game over from the end to get back to the beginning, and noticed it chooses the other number 7 square on the way back.
Why is that?(17 votes)
Using the hill analogy, that section of the maze would be like two even steps on the hill. Either 7 has the same value, so it doesn't actually matter in the search which way is taken. To code that, you could tell your algorithm to randomly select the path to take when the cost value is equal for two different paths.(28 votes)
- what are the basic steps that we need to write an algorithm(11 votes)
1. Determine what you need for the algorithm
2.Determine how to express a certain step
3. See step 2.
4. Run algorithm
5. If not working, see step 6. otherwise, finish
6. diagnose the problem
7. see step 2 if neccesary.(35 votes)
- If the general direction is given , in what way can we better this algorithm?Because it'll be faster with a (x,y)coordinate of each point .(14 votes)
- there seems to be a mistake in the second last paragraph. If you start from 6, you need to go four times north to get to 2, not five, right?(13 votes)
Should be four, might be a typo... good spotting.(9 votes)
- a meme algorithm would be so cool, wouldn't it?(14 votes)
Correct. There should be a meme algorithm.(5 votes)
what do you think the best language is(0 votes)- No such thing. It varies by what you want to do with programming.
If you're some kind of funky systems developer, C or Assembly
And if you want some kind of insane swiss-army chainsaw, then Perl or Common Lisp.
That being said, Clojure's access to Java libraries is pretty nice. Too bad those three look like a cat walked on your keyboard until you become a powerful lisp wizard.(16 votes)
- why are there other unneccacery numbers in the maze(4 votes)
- They are not unnecessary for the program unlike us the program can't understand what is necessary and with is not. Thus everything is important to it(23 votes)
what if I reverse the counting process, i.e setting the origin as 0 and keep adding marks until I find the goal, thus climbing uphill ? Is there any downside of this?(6 votes)- You can start from the origin and work towards the goal, but reconstructing the path becomes more difficult. If we started from the origin and worked out we would have:
************* G *****
**10 11 12 11 **
** 9 *********** 10 **
** 8 ** S ** 10 9 **
** 7 ** 1 ***** 8 **
** 6 ** 2 ** 6 7 **
** 5 4 3 4 5 6 **
**********************
If we move the circle towards the next higher number we come to a problem when we reach 3, because we don't know which 4 to take.
One way to resolve this is to also record in every square which path it took to get to that square. When the numbers reach the goal, we send a copy of the path we recorded in the goal square to the circle. The circle now knows which path to take.
Hope this makes sense(18 votes)
