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



Yüklə 0,99 Mb.
səhifə7/23
tarix26.12.2016
ölçüsü0,99 Mb.
#3369
1   2   3   4   5   6   7   8   9   10   ...   23

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)

1   2   3   4   5   6   7   8   9   10   ...   23




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin