Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

The main advantage of DFS is that its storage requirement is linear in the depth of the state space being searched.

Depth-First Search Algorithms

• States resulting from the first three steps of depth-first search applied to an instance of the 8-puzzle.

DFS Algorithms: Simple Backtracking

• Simple backtracking performs DFS until it finds the first feasible solution and terminates.

• Not guaranteed to find a minimum-cost solution.

• Uses no heuristic information to order the successors of an expanded node.

• Ordered backtracking uses heuristics to order the successors of an expanded node.

Depth-First Branch-and-Bound (DFBB)

• DFS technique in which upon finding a solution, the algorithm updates current best solution.

•