O'Reilly logo

Design and analysis of Algorithms, 2nd Edition by Himanshu B Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required