退火算法 貪婪算法
介紹 (Introduction)
The solution is determined by a sequence of steps each step has given a particular solution and later a complete solution to given the problem can be achieved. In short, while making a choice there should be a greed for the optimum solution. Some points about Greedy strategy:
該解決方案由一系列步驟確定，每個步驟都給出了特定的解決方案，隨后可以實現針對給定問題的完整解決方案。 簡而言之，在做出選擇時，應該有一個貪婪的最佳解決方案。 有關貪婪策略的一些要點 ：
Look for the optimal solution and assumes it as best.
尋找最佳解決方案，并假定它是最佳解決方案。
Solves the sub-problems in Top-down manner.
以自上而下的方式解決子問題。
This approach is less powerful programming techniques.
這種方法是功能較弱的編程技術。
It is not applicable to a wider area like dynamic programming approach.
它不適用于動態編程方法等更廣泛的領域。
It is useful for solving optimization problems.
這對于解決優化問題很有用。
It generates only one solution sequences.
它僅生成一個解決方案序列。
In greedy Strategy following activities are performed,
在貪婪策略中，執行以下活動，
First, select some solutions from input domain.
首先，從輸入域中選擇一些解決方案。
Then check whether the solution is feasible or not.
然后檢查該解決方案是否可行。
In this, we find an optimum solution which satisfies the objective of the function and it can be obtained from a particular solution out of the set of feasible solution.
在此，我們找到了一個滿足函數目標的最優解，并且可以從可行解集中的特定解中獲得。
As greedy method works in stages only one stage is considered at a time. Based on this input it is decided whether a particular input is given the optimal solution or not.
由于貪婪方法分階段進行，因此一次只考慮一個階段。 基于此輸入，確定是否為特定輸入提供了最佳解決方案。
貪婪策略算法 (Algorithm for Greedy Strategy)
In greedy approach D is domain, from which solution is to be obtained of size n...
在貪婪方法中， D是域，將從中獲得大小為n的解 。
Initially assume
Solution ← 0
For i ← 1 to n do
{
S ← select(D) // section of solution from D
If (Feasible (solution) then
Solution ← Union (solution, s);
}
Return solution
貪婪策略的要素 (Elements of Greedy Strategy)
Greedy Choice property
貪婪選擇酒店
A global optimal solution can be arrived by local optimal choice.
全局最優解可以通過局部最優選擇來獲得。
For finding the solutions to the problem the subproblems are solved and best from these sub-problems is considered.
為了找到問題的解決方案，解決了子問題，并考慮了這些子問題中的最佳問題。
This choice may depend upon the previously made choices but it does not depend on any future choice.
該選擇可能取決于先前做出的選擇，但并不取決于任何將來的選擇。
Thus in the greedy method, greedy choices are made one after the another, reducing each given problem instances to smaller one.
因此，在貪婪方法中，貪婪的選擇是一個接一個地做出的，從而將每個給定的問題實例減少為較小的一個。
Optimal sub-structure
最佳子結構
If an optimal solution to the problem containing the optimal solution to the subproblem then the problem shows an optimal substructure.
如果問題的最優解包含子問題的最優解，那么問題將顯示最優子結構。
A problem has optimal substructure if has been next choices always leads to an optimal solution.
如果問題一直存在，則問題具有最佳的子結構，這通常會導致最佳解決方案。
貪心法的應用 (Applications of greedy method)
Problems that can be solved by greedy approach,
貪婪方法可以解決的問題，
Knapsack problem
背包問題
Prim’s algorithm for minimum spanning tree.
Prim的最小生成樹算法。
Kruskal’s algorithm for minimum spanning tree.
最小生成樹的Kruskal算法。
Finding shortest job
尋找最短的工作
Job sequencing with deadlines
有期限的工作排序
Optimal storage on taps
水龍頭的最佳存儲
Huffman coding
霍夫曼編碼
Feasible solution
可行的解決方案
The set of values for the decision problem which satisfies all of the constraints of an optimization problem then the solution is called feasible solution. Feasible solution satisfy all linear and non-linear constraints. The set of all feasible solution defines the feasible region of the problem. To solve a problem first find anyone feasible solution and then try to find another feasible solution which satisfies the values of the objective functions. The whole process is repeated until when no further improvement is achieved or other criteria are met.
滿足優化問題所有約束的決策問題的值集，然后將該解決方案稱為可行解。 可行的解決方案滿足所有線性和非線性約束。 所有可行解的集合定義了問題的可行區域。 為了解決問題，首先找到任何可行的解決方案，然后嘗試找到另一種滿足目標函數值的可行解決方案。 重復整個過程，直到沒有進一步的改善或滿足其他標準為止。
翻譯自: https://www.includehelp.com/algorithms/introduction-to-greedy-strategy-in-algorithms.aspx
退火算法 貪婪算法
