Solution
Optimization problems are computational problems where the goal is to find the best solution according to some criteria, not merely any valid solution.
They typically have:
- Input: data that describes the situation (for example cities and distances, or items with weights and values).
- Process: an algorithm that searches among feasible solutions.
- Output: a solution judged best by a measure such as shortest distance, fewest coins, or highest value.
Many optimization problems are tractable; others are intractable (NP-hard or NP-complete) and must be approximated for large inputs.
Examples of applications
-
Traveling Salesman Problem (TSP): Find the shortest route that visits a set of cities and returns to the origin. Used in delivery routing, logistics, and tour planning. Exact solution is infeasible for many cities because the number of routes grows factorially.
-
Knapsack Problem: A knapsack has a maximum weight, and each item has a weight and a value. The goal is the most valuable combination that does not exceed the weight. Used in packing, budgeting, and resource allocation. It is NP-complete.
-
Coin Change: Make a given amount with the fewest coins. A greedy algorithm chooses the largest denomination that does not exceed the remaining amount. Used in cash registers and vending machines.
-
Shortest path in a network: BFS (on unweighted graphs) can find the shortest path between two people in a social network (degree of separation) or between locations in a route-planning graph.
In each case the problem is not only to find a solution but to find one that is best, or good enough, under a stated measure.