贪婪算法-Greedy algorithm

贪婪算法(greedy algorithm)

WIKI

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the intent of finding a global optimum.

定义

每步都采取最优的做法，即每步都选择局部最优解

背包问题(knapsack problem)

WIKI

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

集合覆盖问题(set cover problem)

WIKI

The set cover problem is a classical question in combinatorics, computer science and complexity theory.

NP完全问题(NP-completeness)

WIKI

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes. In this context, NPstands for "nondeterministic polynomial time".

旅行商问题(travelling salesman problem)

WIKI

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

集合覆盖问题和旅行商问题共同：都需要计算所有解，并从中选出最小/最短的那个

NP完全问题特点

元素较少时运行速度非常快，但随着元素数量的增加，速度会变得非常慢

涉及“所有组合”的问题通常是NP完全问题

不能将问题分成小问题，必须考虑各种可能的情况、

如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，可能是NP完全问题

如果问题涉及集合（如广播台集合）且难以解决，可能是NP完全问题

如果问题可转换为集合覆盖问题或旅行商问题，肯定是NP完全问题