Design and analysis of Algorithms, 2nd Edition

12

Abstract Algorithms 4— Backtracking, Branch and Bound

Objectives

After reading this chapter, you should understand:

• Various Searching Techniques
• The Backtracking Strategy and FrameWork
• 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
• What is Branch-and-Bound Method and How it Improves the Efficiency of Solution Search Problems.

If programs had multiple ways to think, then they wouldn’t so often get stuck—because they could change their points of view.

—Marvin Minsky ...