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

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

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

1 貪心算法的定義

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

2 貪心算法的基本要素

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

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

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

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

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

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

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

4 貪心算法的特點及難點

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

但正是因為這種鮮明的特點，問題也隨之凸顯。比如，利用貪心算法的貪心策略，我們考慮的只是當(dāng)下，這可能是現(xiàn)階段最優(yōu)的一種解決問題的方式，但我們卻并不能保證其在最后的解題中是否是最優(yōu)的一種解題方式。因為這種方式只能從局部考慮，無法從整體上來做出判斷，也并不能保證這就是最正確的解題方式。所以對于最終的解題方式來說，這種貪心算法是否會是最優(yōu)的一種解題方法，我們無法保證。我們也只能用利用貪心算法來解決一些比如最大或者最小的問題。因為在一定程度上來說，貪心算法只能確定一些問題的可行范圍，并不能準(zhǔn)確解答。它是一種預(yù)估的范疇，當(dāng)面對詳細的問題，或者是非常絕對的問題，那么貪心算法就不是最佳的計算方式。所以我們在使用貪心算法的時候，要考慮到它的適用性，不能盲目使用[4]。

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

5 結(jié)語

貪心算法或許在一些信息競賽或者是NPC類的問題中具有絕對的優(yōu)勢，但平時可能只能確定一個范圍，并不一定是最佳的解題方式。所以在求最優(yōu)解時，一定要全面考慮，可以運用貪心算法時，一定要充分利用其優(yōu)勢，因為它是最接近我們思維的一種解題方式。同時，我們也一定要考慮到貪心算法的適用范圍，在可行的范圍最大化利用這一方法。