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

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