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


Discrete Optimization: Example An admissible heuristic for 8-puzzle is as follows



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

Discrete Optimization: Example

  • An admissible heuristic for 8-puzzle is as follows:

  • Assume that each position in the 8-puzzle grid is represented as a pair.

  • The distance between positions (i,j) and (k,l) is defined as |i - k| + |j - l|. This distance is called the Manhattan distance.

  • The sum of the Manhattan distances between the initial and final positions of all tiles is an admissible heuristic.



Parallel Discrete Optimization: Motivation

  • DOPs are generally NP-hard problems. Does parallelism really help much?

  • For many problems, the average-case runtime is polynomial.

  • Often, we can find suboptimal solutions in polynomial time.

  • Many problems have smaller state spaces but require real-time solutions.

  • For some other problems, an improvement in objective function is highly desirable, irrespective of time.




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