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


The feasible space S is typically very large



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

The feasible space S is typically very large.

  • For this reason, a DOP can be reformulated as the problem of finding a minimum-cost path in a graph from a designated initial node to one of several possible goal nodes.

  • Each element x in S can be viewed as a path from the initial node to one of the goal nodes.

  • This graph is called a state space.



  • Discrete Optimization Basics

    • Often, it is possible to estimate the cost to reach the goal state from an intermediate state.

    • This estimate, called a heuristic estimate, can be effective in guiding search to the solution.

    • If the estimate is guaranteed to be an underestimate, the heuristic is called an admissible heuristic.

    • Admissible heuristics have desirable properties in terms of optimality of solution (as we shall see later).




    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