Chapter 12
Abstract Algorithms 4 — Backtracking
Objectives
After reading this chapter, you should understand:
- Various Searching Techniques
- The Backtracking Strategy and Frame Work
- State Space : Representation of the Problem state
- When the use of backtracking is justified
- How efficient is backtracking
- Combinatorial Explosion
- Pruning: How can it lead to improved efficiency
- Solution of problems like: 8-Queens, The Convex Hull, the M-colouring and the Hamiltonian Circuit problem through Backtracking
Chapter Outline
12.2.1 Breadth First Search (BFS)
12.2.2 Depth First Search (DFS)
12.3 The Backtracking Strategy
Get Design and Analysis of Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
