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:

• 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.