貪心算法

missonce 發(fā)布于2019-07-30 16:39 / 741人閱讀

摘要：貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是類(lèi)算法的一個(gè)共同點(diǎn)。

貪心算法的基本要素
對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。
但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

1、貪心選擇性質(zhì)
所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。
動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。
對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。

2、最優(yōu)子結(jié)構(gòu)性質(zhì)
貪心選擇是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終能得到問(wèn)題的最優(yōu)解。通常可以首先證明問(wèn)題的一個(gè)整體最優(yōu)解，是從貪心選擇開(kāi)始的，而且作了貪心選擇后，原問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的類(lèi)似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一步貪心選擇，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。

3、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異
貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類(lèi)算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，并以此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。

貪婪算法可解決的問(wèn)題通常大部分都有如下的特性：
隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過(guò)但被丟棄的候選對(duì)象。
有一個(gè)函數(shù)來(lái)檢查一個(gè)候選對(duì)象的集合是否提供了問(wèn)題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。
還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，也即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性。
選擇函數(shù)可以指出哪一個(gè)剩余的候選對(duì)象最有希望構(gòu)成問(wèn)題的解。
最后，目標(biāo)函數(shù)給出解的值。
為了解決問(wèn)題，需要尋找一個(gè)構(gòu)成解的候選對(duì)象集合，它可以?xún)?yōu)化目標(biāo)函數(shù)，貪婪算法一步一步的進(jìn)行。起初，算法選出的候選對(duì)象的集合為空。接下來(lái)的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對(duì)象中選出最有希望構(gòu)成解的對(duì)象。如果集合中加上該對(duì)象后不可行，那么該對(duì)象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個(gè)解通常是最優(yōu)的。