阜陽(yáng)市第三中學(xué) 安徽阜陽(yáng) 236000

貪心算法是一種非常常見(jiàn)的算法，最常應(yīng)用的有歸納法和反證法，當(dāng)然還有其它的應(yīng)用方式。此外，貪心算法是信息競(jìng)賽中最為常用的一種解題思路。

1 貪心算法的定義

貪心算法只是當(dāng)下最優(yōu)的一種解題方式，與后續(xù)無(wú)關(guān)，有些自私因素在其中，所以被稱為貪心算法[1]。因?yàn)槠渚植啃?，可能從整體來(lái)看這種解題方式不夠完美、不夠準(zhǔn)確，但它是目前最快最完美的解答方式。這種方式在信息競(jìng)賽中很常見(jiàn)，也是信息競(jìng)賽中的一種常見(jiàn)解題思想。

2 貪心算法的基本要素

貪心算法的第一個(gè)要素是貪心選擇，通常來(lái)說(shuō)就是所求問(wèn)題的一種最優(yōu)的解答方式。一般是我們常采用從頂向下，或者是以迭代的方式做出選擇，但都是為了同一目的，之后再通過(guò)一次次貪心選擇，將求解的問(wèn)題不斷做減法，通過(guò)簡(jiǎn)化，縮小規(guī)模以找尋最優(yōu)的一種解題方法。

一般來(lái)說(shuō)，一個(gè)問(wèn)題能否用貪心算法，首選要看它能否做出貪心選擇，如果可以通過(guò)一步步的貪心選擇，最終找到最優(yōu)方式，那么就可以使用貪心算法。通過(guò)數(shù)學(xué)歸納法來(lái)證明，就是每一步的貪心選擇最后都是為了達(dá)到最優(yōu)的目的。而使用貪心算法一般都有一定的貪心策略，而證明這個(gè)貪心策略的方法有很多，一般最常用的有歸納法、反證法。

3 貪心算法生活中的應(yīng)用

在日常生活中，比如汽車去加油站加油，如果加滿后這輛車可以行駛N千米，但是在途中有很多個(gè)加油站，此時(shí)我們可以利用貪心算法算出在整個(gè)旅途中怎么加油使得加油的次數(shù)最少。首先我們要先通過(guò)貪心算法設(shè)計(jì)一個(gè)最有效的算法，并要說(shuō)明應(yīng)該在哪些個(gè)加油站?？考佑蚚2]。如果加油次數(shù)為m，那每一個(gè)加油站之間的距離就是a[i]；i=0，1，2，3……n。利用貪心算法，最優(yōu)的選擇應(yīng)該是若每次加油時(shí)油箱里的油不能支撐到下一個(gè)加油站，我們才會(huì)選擇就近的加油站加油。

假設(shè)A不是最優(yōu)的一種方式，那么一定還存在其它解題方式，假設(shè)是B，那么B就是和A最接近的一個(gè)優(yōu)解。B和A的前K-1個(gè)元素是相同的，也就是說(shuō)K個(gè)元素是不同的，即A的第K個(gè)選擇是一定滿足一個(gè)條件，那就是不能不加油就開(kāi)到另一個(gè)加油站。而B的第K個(gè)選擇的站一定是A的K-1，如果說(shuō)到K的選擇之間的某一個(gè)加油站是Y的話，對(duì)A來(lái)說(shuō)，X到下一個(gè)加油的距離一定小于Y。

如果此時(shí)再構(gòu)造一個(gè)C，也就是說(shuō)C=B-y+x。那么C其實(shí)就是這個(gè)問(wèn)題的最優(yōu)解，同時(shí)C也能使得汽車安全到達(dá)最終的目的地。在C中，在X站之前的加油站點(diǎn)其實(shí)和A站的加油站點(diǎn)是一樣的，而在X后的加油站點(diǎn)也和B站的加油站點(diǎn)是一樣的，所以就是說(shuō)C可以順利通過(guò)。而當(dāng)?shù)酱騒站的時(shí)候，X站的下站又小于Y到下一個(gè)加油站的距離，所以在這個(gè)過(guò)程中不需要加油，所以按照這樣的理論來(lái)說(shuō)，那么C就是最優(yōu)解。

但如果C是最優(yōu)解，這又與之前的假設(shè)K-1矛盾，所以如果之前的所有的假設(shè)都是錯(cuò)誤，就意味著A是最優(yōu)解。

4 貪心算法的特點(diǎn)及難點(diǎn)

貪心算法的特點(diǎn)非常鮮明，就是在運(yùn)用整個(gè)貪心算法，通過(guò)貪心策略解決問(wèn)題的過(guò)程中不需要考慮前因后果，也不需要不斷回溯，而只需要考慮在當(dāng)前狀態(tài)下是否是最優(yōu)的解題方式，因此目的性更強(qiáng)，在解題的時(shí)候也更有目標(biāo)，更準(zhǔn)確，更快捷[3]。

但正是因?yàn)檫@種鮮明的特點(diǎn)，問(wèn)題也隨之凸顯。比如，利用貪心算法的貪心策略，我們考慮的只是當(dāng)下，這可能是現(xiàn)階段最優(yōu)的一種解決問(wèn)題的方式，但我們卻并不能保證其在最后的解題中是否是最優(yōu)的一種解題方式。因?yàn)檫@種方式只能從局部考慮，無(wú)法從整體上來(lái)做出判斷，也并不能保證這就是最正確的解題方式。所以對(duì)于最終的解題方式來(lái)說(shuō)，這種貪心算法是否會(huì)是最優(yōu)的一種解題方法，我們無(wú)法保證。我們也只能用利用貪心算法來(lái)解決一些比如最大或者最小的問(wèn)題。因?yàn)樵谝欢ǔ潭壬蟻?lái)說(shuō)，貪心算法只能確定一些問(wèn)題的可行范圍，并不能準(zhǔn)確解答。它是一種預(yù)估的范疇，當(dāng)面對(duì)詳細(xì)的問(wèn)題，或者是非常絕對(duì)的問(wèn)題，那么貪心算法就不是最佳的計(jì)算方式。所以我們?cè)谑褂秘澬乃惴ǖ臅r(shí)候，要考慮到它的適用性，不能盲目使用[4]。

貪心算法的難點(diǎn)也很明顯，即如何確定能否使用貪心算法。使用貪心算法并不困難，但其是卻是在局部中應(yīng)用的，并不能確定是不是整體的最優(yōu)解。所以針對(duì)一些問(wèn)題，如果只能在局部使用，我們就應(yīng)該考慮其它解題方式。

5 結(jié)語(yǔ)

貪心算法或許在一些信息競(jìng)賽或者是NPC類的問(wèn)題中具有絕對(duì)的優(yōu)勢(shì)，但平時(shí)可能只能確定一個(gè)范圍，并不一定是最佳的解題方式。所以在求最優(yōu)解時(shí)，一定要全面考慮，可以運(yùn)用貪心算法時(shí)，一定要充分利用其優(yōu)勢(shì)，因?yàn)樗亲罱咏覀兯季S的一種解題方式。同時(shí)，我們也一定要考慮到貪心算法的適用范圍，在可行的范圍最大化利用這一方法。