貪婪算法的一般算法

我一直在貪婪算法刷新算法設計技術。我已經閱讀了很多來源來解釋什麼是貪婪算法，因爲我想將一般的貪婪算法放在一起。貪婪算法的一般算法

在閱讀這些資源時，我已經收集了所有重要的概念，以嘗試爲貪婪選擇技術提出這種通用算法。所謂「一般」，我的意思是它總結了技術的行爲針對所有可能的問題，這種技術會產生一個正確的解決方案。

我想對它做一些輸入。這裏取1：

設f是從S到任意集合的函數。下面的算法試圖每個S的元素的每個搜索迭代進行貪心選擇，以儘量拿出最好的點在f S1上給定一組約束條件C：

Select p0 from S; 
i := 1; 
Let P be a set of already chosen points from S to be initialized to {} 
Let F be the set of values of f for each element of P to be initialize to {}; 
while S != {}: 
    Make a greedy choice for p_i based on p_{i - 1}; 
    if f(p_i) is feasible based on constraints from C and has improved: 
     p_{i - 1} := p_i; 
    Add f_i := f(p_i) to F; 
    Remove p_{i - 1} from S and save it in P; 
return P, F;

我的具體問題是：這首先從算法設計的貪婪選擇技術的正確概括起步有多遠？

在我們研究了這種方法後，我想看看如何將一般算法實例化爲經典的貪婪算法問題。

這應該很有趣:)

來源

2017-09-02 Eduardo

這很有趣，我很確定它超出了Stack Overflow的範圍。 [計算機科學S.E.]（https://cs.stackexchange.com/）可能會更好地問這個問題。 – stybl

你的問題是什麼？ –

通用貪婪算法是什麼意思。這完全取決於問題類型 –

IMO會回答你的問題。

即使不是不可能，也很難精確定義貪婪算法的含義。如果一個算法在小步驟中建立了一個解決方案，則該算法是貪婪的。在每個步驟中選擇一個決策，以便優化一些基本標準。人們通常可以針對同一問題設計許多不同的貪婪算法，每個算法在本地增量式地優化一些不同的度量方法，以實現解決方案。

算法設計手冊，作者：Jon Kleinberg和ÉvaTardos。第4章貪婪算法。

來源

2017-09-03 09:19:17

貪婪算法的一般算法

回答

相關問題