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


Defines function l(x) for each node x as g(x) + h(x)



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

Defines function l(x) for each node x as g(x) + h(x).

  • Here, g(x) is the cost of getting to node x and h(x) is an admissible heuristic estimate of getting from node x to the solution.

  • The open list is sorted on l(x).

  • The space requirement of BFS is exponential in depth!



  • Best-First Search: Example

    • Applying best-first search to the 8-puzzle: (a) initial configuration; (b) final configuration; and (c) states resulting from the first four steps of best-first search. Each state is labeled with its -value (that is, the Manhattan distance from the state to the final state).





    Search Overhead Factor

    • The amount of work done by serial and parallel formulations of search algorithms is often different.


    • Yüklə 0,99 Mb.

      Dostları ilə paylaş:
    1   ...   7   8   9   10   11   12   13   14   ...   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