Design and Analysis of Algorithms

Backtracking ˜ Examples: • Maze problem • The bicycle lock problem: ü Consider a lock with N switches, each of which can be either 0 or 1. ü We know that the combination that opens the lock should have at least 2 N 1's. ü Note: The total number of combinations is 2 N ü The solution space can be modeled by a tree Finish Start ü Example: N=3 ˜ Characteristics • Backtracki

All courses in CS

Popular Documents