|
Discrete Optimization: Example An admissible heuristic for 8-puzzle is as follows
|
səhifə | 5/23 | tarix | 26.12.2016 | ölçüsü | 0,99 Mb. | | #3369 |
|
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.
Dostları ilə paylaş: |
|
|