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


Sequential Search Algorithms Is the search space a tree or a graph?



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

Sequential Search Algorithms

  • Is the search space a tree or a graph?

  • The space of a 0/1 integer program is a tree, while that of an 8-puzzle is a graph.

  • This has important implications for search since unfolding a graph into a tree can have significant overheads.



Sequential Search Algorithms

  • Two examples of unfolding a graph into a tree.



Depth-First Search Algorithms

  • Applies to search spaces that are trees.

  • DFS begins by expanding the initial node and generating its successors. In each subsequent step, DFS expands one of the most recently generated nodes.

  • If there exists no success, DFS backtracks to the parent and explores an alternate child.

  • Often, successors of a node are ordered based on their likelihood of reaching a solution. This is called directed DFS.


  • Yüklə 0,99 Mb.

    Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   ...   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