貪心算法的圖文講解教學(xué)提綱

智能(zhìnénɡ)信息處理

-----貪心算法第一頁(yè)，共15頁(yè)。貪心算法(suànfǎ)的定義貪心算法(suànfǎ)的基本思想貪心算法(suànfǎ)的實(shí)現(xiàn)思路貪心算法(suànfǎ)的基本要素貪心算法(suànfǎ)的特點(diǎn)貪心算法(suànfǎ)存在的問(wèn)題第二頁(yè)，共15頁(yè)。貪心算法（又稱貪婪算法）可以簡(jiǎn)單描述為：對(duì)一組數(shù)據(jù)進(jìn)行排序，找出最小值，進(jìn)行處理，再找出最小值，再處理，也就是說(shuō)貪心算法是一種依據(jù)某種貪心標(biāo)準(zhǔn)，從問(wèn)題的初始狀態(tài)出發(fā)，在每一步選擇中都直接(zhíjiē)去求每一步的最優(yōu)解，最終通過(guò)若干次的貪心選擇得出整個(gè)問(wèn)題的最優(yōu)解的算法。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法，通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解，而它所做的每一次選擇都是當(dāng)前狀態(tài)下某種意義的最好或最優(yōu)的選擇，即貪心選擇，從而得到結(jié)果是最好或最優(yōu)的算法。第三頁(yè)，共15頁(yè)。

貪心的基本思想用局部解構(gòu)造全局解，即從問(wèn)題的某一個(gè)初始解逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)某個(gè)算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。貪心算法思想的本質(zhì)就是分治，或者說(shuō)：分治是貪心的基礎(chǔ)。每次都形成局部最優(yōu)解，換一種方法說(shuō)，就是每次都處理出一個(gè)最好的方案。利用貪心策略解題(jiětí)，需要解決兩個(gè)問(wèn)題：（1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標(biāo)準(zhǔn)，以得到問(wèn)題的最優(yōu)/較優(yōu)解。第四頁(yè)，共15頁(yè)。

貪心(tānxīn)算法的實(shí)現(xiàn)思路應(yīng)用同一規(guī)則F，將原問(wèn)題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問(wèn)題；從問(wèn)題的某一初始(chūshǐ)解出發(fā)：while能朝給定總目標(biāo)前進(jìn)一步Do求出可行解的一個(gè)解元素；由所有解元素組合成問(wèn)題的一個(gè)可行解。第五頁(yè)，共15頁(yè)。貪心(tānxīn)算法的基本要素貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有(jùyǒu)貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開(kāi)始。做了貪心選擇后，原問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一步做貪心選擇，最終可得到問(wèn)題的整體最優(yōu)解。其中，證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)。（先做選擇，再解問(wèn)題的自頂向下的方式）第六頁(yè)，共15頁(yè)。最優(yōu)子結(jié)構(gòu)性質(zhì)(xìngzhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運(yùn)用貪心策略在每一次轉(zhuǎn)化時(shí)都取得了最優(yōu)解。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生(chǎnshēng)直接影響，而動(dòng)態(tài)規(guī)劃則不是。貪心算法對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退；動(dòng)態(tài)規(guī)劃則會(huì)根據(jù)以前的選擇結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。動(dòng)態(tài)規(guī)劃主要運(yùn)用于二維或三維問(wèn)題，而貪心一般是一維問(wèn)題。第七頁(yè)，共15頁(yè)。在動(dòng)態(tài)規(guī)劃算法中，每步所做的選擇往往依賴于相關(guān)子問(wèn)題的解。因而只有在解出相關(guān)子問(wèn)題后，才能做出選擇。而在貪心(tānxīn)算法中，僅在當(dāng)前狀態(tài)下做出最好選擇，即局部最優(yōu)選擇。然后再去解做出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問(wèn)題。貪心(tānxīn)算法所做的貪心(tānxīn)選擇可以依賴于以往所做過(guò)的選擇，但決不依賴于將來(lái)所做的選擇，也不依賴于子問(wèn)題的解。正是由于這種差別，動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心(tānxīn)算法則通常以自頂向下的方式進(jìn)行，以迭代的方式做出相繼的貪心(tānxīn)選擇，每做一次貪心(tānxīn)選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。第八頁(yè)，共15頁(yè)。貪心算法的特點(diǎn)貪心算法最大的特點(diǎn)就是快，但同時(shí)存在兩大難點(diǎn)：（1）如何貪心具有應(yīng)當(dāng)采用貪心算法的問(wèn)題，當(dāng)“貪心序列”中的每項(xiàng)互異且當(dāng)問(wèn)題沒(méi)有重疊性時(shí)，看起來(lái)總能通過(guò)貪心算法取得（近似）最優(yōu)解的。當(dāng)一個(gè)(yīɡè)問(wèn)題具有多個(gè)最優(yōu)解時(shí)，貪心算法并不能求出所有最優(yōu)解。一般單純的貪心算法是順序處理問(wèn)題的，而且每個(gè)結(jié)果是可以在處理完一個(gè)(yīɡè)數(shù)據(jù)后即時(shí)輸出的。（2）貪心的正確性要證明貪心性質(zhì)的正確性，才是貪心算法的真正挑戰(zhàn)，因?yàn)椴⒉皇敲看尉植孔顑?yōu)解都會(huì)與整體最優(yōu)解之間有聯(lián)系，往往靠貪心算法生成的解不是最優(yōu)解。第九頁(yè)，共15頁(yè)。貪心(tānxīn)算法存在的問(wèn)題不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來(lái)是最優(yōu)的選擇，因此并不從整體上加以考慮；貪心算法只能用來(lái)求某些(mǒuxiē)最大或最小解的問(wèn)題；貪心算法只能確定某些(mǒuxiē)問(wèn)題的可行性范圍。第十頁(yè)，共15頁(yè)。汽車(qìchē)加油問(wèn)題問(wèn)題的提出一輛汽車加滿油后，可行使N千米。旅途中有若干個(gè)加油站。若要使沿途加油次數(shù)最少，設(shè)計(jì)一個(gè)有效算法，對(duì)于給定的N和k個(gè)加油站位置，指出應(yīng)在哪些加油站?？考佑筒拍苁辜佑痛螖?shù)最少。編碼分析(fēnxī)把兩加油站的距離放在數(shù)組中，a[1..k]表示從起始位置開(kāi)始跑，經(jīng)過(guò)k個(gè)加油站，a[i]表示第i-1個(gè)加油站到第i個(gè)加油站的距離。汽車在運(yùn)行的過(guò)程中如果能跑到下一個(gè)站則不加油，否則要加油。第十一頁(yè)，共15頁(yè)。對(duì)于這個(gè)問(wèn)題我們有以下幾種情況：設(shè)加油次數(shù)為k，每個(gè)加油站間距離為a[i]；i=0，1，2，3……n（1）始點(diǎn)到終點(diǎn)的距離小于N，則加油次數(shù)k=0；（2）始點(diǎn)到終點(diǎn)的距離大于N時(shí)：A加油站間的距離相等，即ａ[i]=a[j]=L=N，則加油次數(shù)最少k=n；B加油站間的距離相等，即ａ[i]=a[j]=L>N，則不可能到達(dá)終點(diǎn)；C加油站間的距離相等，即ａ[i]=a[j]=L<N，則加油次數(shù)k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；D加油站間的距離不相等，即ａ[i]！=a[j]，則加油次數(shù)k通過(guò)(tōngguò)貪心算法求解。第十二頁(yè)，共15頁(yè)。貪心算法策略由于汽車是由始向終點(diǎn)方向開(kāi)的，我們(wǒmen)最大的麻煩就是不知道在哪個(gè)加油站加油可以使我們(wǒmen)既可以到達(dá)終點(diǎn)又可以使我們(wǒmen)加油次數(shù)最少。（提出問(wèn)題）提出問(wèn)題是解決的開(kāi)始。為了著手解決遇到的困難，取得最優(yōu)方案。我們(wǒmen)可以假設(shè)不到萬(wàn)不得已我們(wǒmen)不加油，即除非我們(wǒmen)油箱里的油不足以開(kāi)到下一個(gè)加油站，我們(wǒmen)才加一次油。在局部找到一個(gè)最優(yōu)的解。每加一次油我們(wǒmen)可以看作是一個(gè)新的起點(diǎn)，用相同的遞歸方法進(jìn)行下去。最終將各個(gè)階段的最優(yōu)解合并為原問(wèn)題的解得到我們(wǒmen)原問(wèn)題的求解。第十三頁(yè)，共15頁(yè)。正確性證明(zhèngmíng)

該題設(shè)在加滿油后可行駛的N千米這段路程上任取兩個(gè)加油站Ａ、Ｂ，且Ａ距離始點(diǎn)比Ｂ距離始點(diǎn)近，則若在Ｂ加油不能到達(dá)終點(diǎn)那么在Ａ加油一定不能到達(dá)終點(diǎn)，因?yàn)閙+N<n+N，即在B點(diǎn)加油可行駛的路程比在A點(diǎn)加油可行駛的路程要長(zhǎng)n-m千米，所以只要終點(diǎn)不在B、C之間且在C的右邊的話，根據(jù)貪心選擇(xuǎnzé)，為使加油次數(shù)最少就會(huì)選擇(xuǎnzé)距離加滿油得點(diǎn)遠(yuǎn)一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇(xuǎnzé)性質(zhì)由于（b[1]，b[2]，……b[n]）是這段路程加油次數(shù)最少的一個(gè)滿足貪心選擇(xuǎnzé)性質(zhì)的最優(yōu)解，則易知若在第一個(gè)加油站加油時(shí)，b[1]=1，則（b[2]，b[3]，……b[n]）是從a[2]到a[n]這段路程上加油次數(shù)最少且這段路程上的加油站個(gè)數(shù)為（a[2]，a[3]，……a[n]）的最優(yōu)解，即每次汽車中剩下的油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油，每個(gè)過(guò)程從加油開(kāi)始行駛到再次加油滿足貪心且每一次加油后相當(dāng)于與起點(diǎn)具有相同的條件，每個(gè)過(guò)程都是相同且獨(dú)立，也就是說(shuō)加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。第十四頁(yè)，共15頁(yè)?？偨Y(jié)(zǒngjié)在對(duì)問(wèn)題求解時(shí)，會(huì)選擇當(dāng)前看起來(lái)最有希望成功的邊（任務(wù)）。一旦做出決定，它就不會(huì)再重新考慮，也不會(huì)關(guān)心后面會(huì)引發(fā)什么情況。也就是說(shuō)，不從整體最優(yōu)上加以考慮，它所做出的是在某種意義上的局部最優(yōu)解。貪心算法是一種能夠得到某種度量意義下的最