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


DFBB does not explore paths that are guaranteed to lead to solutions worse than current best solution



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

DFBB does not explore paths that are guaranteed to lead to solutions worse than current best solution.

  • On termination, the current best solution is a globally optimal solution.



  • Iterative Deepening Search

    • Often, the solution may exist close to the root, but on an alternate branch.

    • Simple backtracking might explore a large space before finding this.

    • Iterative deepening sets a depth bound on the space it searches (using DFS).

    • If no solution is found, the bound is increased and the process repeated.



    Iterative Deepening A* (IDA*)

    1   ...   4   5   6   7   8   9   10   11   ...   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