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


Best-First Search (BFS) Algorithms



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

Best-First Search (BFS) Algorithms

  • BFS algorithms use a heuristic to guide search.

  • The core data structure is a list, called Open list, that stores unexplored nodes sorted on their heuristic estimates.

  • The best node is selected from the list, expanded, and its off-spring are inserted at the right position.

  • If the heuristic is admissible, the BFS finds the optimal solution.



Best-First Search (BFS) Algorithms

  • BFS of graphs must be slightly modified to account for multiple paths to the same node.

  • A closed list stores all the nodes that have been previously seen.

  • If a newly expanded node exists in the open or closed lists with better heuristic value, the node is not inserted into the open list.



The A* Algorithm

  • A BFS technique that uses admissible heuristics.


  • Yüklə 0,99 Mb.

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