18Oct 2010
Vacuum Cleaner
DUST GENERATION
RANDOM NUMBER GENERATOR
BASIC ALGORITHM
SEARCHING AND PATH GENERATION
How It works?
DIVIDES THE ROOM IN A GRID
 |
 |
INITIAL ROOM STATE |
FINAL ROOM STATE |
- THE SIMPLEST TECHNIQUE CAN BE TO SEARCH ALL THE SQUARES.
THIS IS NOT AN EFFICIENT STRATEGY. - 3 PRACTICAL OPTIONS
- DEPTH FIRST
- BREADTH FIRST
- ITERATIVE DEEPENING
- DEPTH FIRST
Has modest memory requirements but may get stuck going down the wrong path. - BREADTH FIRST
It always comes up with the solution but takes too much memory and space. - ITERATIVE DEEPENDING
It combines both DFS and BFS in the sense that it is complete as BFS but requires less memory as DFS.
 |
 |
 |
 |
 |
 |