# 贪心算法

## 算法细节

1. 候选集，用于从中创建解
2. 选择函数，用于选择要添加到解中的最佳候选
3. 可行性函数，用于确定一个候选是否有助于解决问题
4. 目标函数，用于为解或部分解赋值
5. 解函数，当找到一个完整的解时，它会指示出来
1. A candidate set, from which a solution is created
2. A selection function, which chooses the best candidate to be added to the solution
3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
4. An objective function, which assigns a value to a solution, or a partial solution, and
5. A solution function, which will indicate when we have discovered a complete solution

### 最优子结构

“如果问题的最优解包含子问题的最优解，则问题具有最优子结构。”

• 纯贪心算法
• 正交贪心算法
• 松弛贪心算法

## 理论

• 怎样的问题可以保证贪心算法能产生最优解？
• 怎样的问题可以保证贪心算法能产生近似最优解？
• 怎样的问题可以保证贪心算法无法产生最优解？

### 其他有保证的问题

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

## 应用

Greedy algorithms mostly (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

Greedy algorithms mostly (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.

Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

## Examples

• The activity selection problem is characteristic to this class of problems, where the goal is to pick the maximum number of activities that do not clash with each other.
• The matching pursuit is an example of greedy algorithm applied on signal approximation.
• A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.
• A greedy algorithm is used to construct a Huffman tree during Huffman coding where it finds an optimal solution.
• In decision tree learning, greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
• One popular such algorithm is the ID3 algorithm for decision tree construction.
• A* search is conditionally optimal, requiring an "admissible heuristic" that will not overestimate path costs.