O'Reilly logo

Design and Analysis of Algorithms by Himanshu B. Dave, Parag H. 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

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.1 Combinatorial Search

12.2 Search and Traversal

12.2.1 Breadth First Search (BFS)

12.2.2 Depth First Search (DFS)

12.3 The Backtracking Strategy

12.3.1 Example; 8-Queens Problem

12.4 Backtracking Framework

12.4.1 Efficiency of Backtracking ...

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