有很多問(wèn)題初看很棘手，但經(jīng)過(guò)仔細(xì)的分析，可以得出一些顯然的結(jié)論。

比如下面這個(gè)問(wèn)題： 平面內(nèi)有上千個(gè)點(diǎn)，用一個(gè)半徑為R的圓去覆蓋，最多能覆蓋多少點(diǎn)？

很多程序員最暴力的思想就是枚舉，當(dāng)然，利用計(jì)算機(jī)枚舉確實(shí)是一種很有效的方法，特別是在數(shù)據(jù)很小的情況下，不過(guò)對(duì)于上述問(wèn)題，如何枚舉？枚舉圓的位置嗎？

確實(shí)可以枚舉圓的位置，如果不經(jīng)過(guò)思考的話可以再二維正交系內(nèi)枚舉每個(gè)點(diǎn)為圓心，然后判斷這個(gè)圓能覆蓋多少圓，最后結(jié)果取最大。這個(gè)確實(shí)是一種方法，不過(guò)枚舉圓心如何操作？圓心的位置是連續(xù)的，不一定是整點(diǎn)這種離散位置。 在數(shù)據(jù)量小并且精度要求不高的情況下，直接枚舉圓心位置不失為一種好方法。 不過(guò)稍微分析一下，可以得出這樣一個(gè)結(jié)論，最優(yōu)解的圓，也就是覆蓋點(diǎn)最短的R半徑圓，圓上一定有2個(gè)點(diǎn)。

假設(shè)最優(yōu)解的圓上沒(méi)有2個(gè)點(diǎn)，如上圖，那么通過(guò)微量的平移操作，可以使圓接觸平面上的2個(gè)點(diǎn)，并且園內(nèi)的點(diǎn)數(shù)不會(huì)減少，它的結(jié)果不會(huì)比圓上沒(méi)有2個(gè)點(diǎn)的情況差，因?yàn)橹灰笞疃喔采w多少點(diǎn)，我們可以枚舉任意2個(gè)點(diǎn)，這樣這個(gè)半徑為R的圓的位置就確定了（在這2點(diǎn)中垂線上，2中情況），再判斷下這個(gè)圓能覆蓋多少點(diǎn)，兩兩點(diǎn)枚舉后取最大，這是一個(gè)O(n^3)的算法，1秒內(nèi)出結(jié)果，已經(jīng)比較高效了。

所以很多時(shí)候我們可以分析出最優(yōu)解是滿足哪種情況的，然后利用計(jì)算機(jī)特性枚舉最優(yōu)解，逆向思維解決問(wèn)題。

2.動(dòng)態(tài)規(guī)劃思想

  動(dòng)態(tài)規(guī)劃是一種非常高效的方法，這個(gè)編程里面非常非常常見(jiàn)的，不會(huì)搜索和動(dòng)態(tài)規(guī)劃，基本就不會(huì)編程。如果能夠把一個(gè)大的問(wèn)題劃分成若干同類型的小問(wèn)題，小問(wèn)題又可以劃分為更小的問(wèn)題，直到問(wèn)題程度小到一眼就能看出來(lái)。 這樣的例子相當(dāng)多，著名的快速排序就是這種思想，而且利用遞歸的寫法，很容易實(shí)現(xiàn)這種思想。 經(jīng)典的動(dòng)態(tài)規(guī)劃還有很多，最長(zhǎng)上升子序列，背包問(wèn)題等等。

如果還有同學(xué)不明白動(dòng)態(tài)規(guī)劃，看下面這一段C語(yǔ)言代碼，相信能體會(huì)到一些。

/****************** 
Author: lxgsbqylbk 
Function : Get the factorial of integer n (n>=0) 
n!= 
1   n==0 
n*(n-1)!  n>0 
****/ 
int F(int n) 
{ 
    return n?n*F(n-1):1; 
} 

3.排序思想

  排序是一個(gè)很重要的步驟，有很多問(wèn)題通過(guò)排序預(yù)處理后可以更加方便的解決，比如有很多張鈔票，面值不同，從中選出m張使它們價(jià)值最大，一個(gè)做法當(dāng)然是對(duì)著些鈔票按照面值從大到小排序，然后取錢m張就行了。 很多時(shí)候，上述的動(dòng)態(tài)規(guī)劃需要對(duì)變量按照一定規(guī)則排序后才能操作，有一定順序了之后，問(wèn)題一般更容易解決。

  說(shuō)到排序，不得不說(shuō)到貪心算法。 貪心算法就是如果整個(gè)大問(wèn)題要到達(dá)一個(gè)最優(yōu)解，在構(gòu)成大問(wèn)題的小問(wèn)題中每次取最優(yōu)的，大問(wèn)題就能到達(dá)最優(yōu)情況，當(dāng)然，這種策略需要經(jīng)過(guò)證明正確性后才能實(shí)現(xiàn)。 很多貪心過(guò)程前也要有排序的工作，比如著名的Kruscal最小生成樹(shù)算法，要先對(duì)邊進(jìn)行排序，所以排序是個(gè)很重要的過(guò)程，以至于它被收錄到各種語(yǔ)言的庫(kù)函數(shù)中，可以方便的被用戶調(diào)用。

4.二分，三分。

前幾天聽(tīng)同學(xué)說(shuō)，現(xiàn)在8K已經(jīng)招不到會(huì)寫二分的程序員了，當(dāng)然這句話有夸張的成分啦，^-^ 可見(jiàn)二分在程序設(shè)計(jì)中的常用性。

其實(shí)這個(gè)可以并列到枚舉算法那中，只是這種枚舉效率很高，很多地方比如SQL數(shù)據(jù)庫(kù)里面的查找方式就是二分，二分枚舉，三分枚舉，時(shí)間復(fù)雜度都是對(duì)數(shù)級(jí)的，在程序設(shè)計(jì)中是相當(dāng)高效的算法。

二分的條件：數(shù)據(jù)的單調(diào)性。 比如在一組從小到大排序的數(shù)中尋找數(shù)x 這樣就可以二分枚舉 每次可以把范圍縮小一半，無(wú)論數(shù)據(jù)多大，就算超出int類型，都能很快找出來(lái)。

比如求函數(shù)8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == K 在區(qū)間[0,100]的解 由于這個(gè)函數(shù)在[0,100]是單調(diào)遞增的，所以二分是個(gè)不錯(cuò)的選擇。

三分的條件: 數(shù)據(jù)的有凸性。

比如求函數(shù)6*x^7 + 8*x^6 + 7*x^3 + 5*x^2 - K*x 在區(qū)間[0,100]的最小值

這個(gè)函數(shù)在[0,100]是一個(gè)先減后增(或者完全單調(diào)，主要看K)的函數(shù)，所以三分求解。

當(dāng)然這個(gè)問(wèn)題可以轉(zhuǎn)換為二分，將函數(shù)求導(dǎo)，二分其在0的位置即可，這個(gè)涉及到高等數(shù)學(xué)，不贅述了。

具體過(guò)程可以去查資料 二分前一般也需要排序操作的。

5.隨機(jī)算法

很多時(shí)候在要解決的問(wèn)題沒(méi)有任何思路，枚舉數(shù)據(jù)量又太大的情況下，可以使用一些隨機(jī)算法。

  常見(jiàn)的隨機(jī)算法，蟻群算法，模擬退火等等。

  簡(jiǎn)單說(shuō)說(shuō)模擬退火（后面我打算專門寫一篇模擬退火的隨筆）

  比如平面內(nèi)有成千上萬(wàn)個(gè)點(diǎn)，要在平面選一個(gè)圓，覆蓋所有點(diǎn)，問(wèn)最小的半徑是多少？

第一次接觸這個(gè)問(wèn)題的時(shí)候我有想到一種做法（不敢保證正確）：

  根據(jù)1 還是可以得出結(jié)論，最優(yōu)情況圓上面一定有2個(gè)點(diǎn)，否則的話可以把圓繼續(xù)縮小平移，使它上面有2個(gè)點(diǎn)，結(jié)果更優(yōu)。

所以枚舉任意2個(gè)點(diǎn)，圓心一定在這2點(diǎn)中垂線上，這里是對(duì)的。 然后假設(shè)這個(gè)圓心在在中垂線上移動(dòng)，如果滿足要求，包圍了所有點(diǎn)。

那么我猜測(cè)這個(gè)圓在移動(dòng)過(guò)程中半徑先減小后增大。(感覺(jué)而已，未證明，也未測(cè)試，太麻煩了。) 這里可以使用上述的三分枚舉，因?yàn)榘霃胶瘮?shù)是下凸性的。

我上面這個(gè)方法正確性先不說(shuō)，復(fù)雜度是有一點(diǎn)的，枚舉2點(diǎn)，再三分。O(n^2*logV) 當(dāng)然，數(shù)據(jù)很小的情況下，比如只有幾千個(gè)點(diǎn)的話，結(jié)果秒出，數(shù)據(jù)大了，效率降低了。

這里說(shuō)一下模擬退火的思想。 大概依照一個(gè)這樣的理論，假設(shè)現(xiàn)在有1個(gè)位置pos,如果最優(yōu)解圓心位置在pos上面，那么如果往pos下面搜，搜到的圓心一定比在pos的位置時(shí)候大。

依照這個(gè)理論，我們就可以現(xiàn)在平面內(nèi)隨機(jī)生成一些點(diǎn)，然后貪心的隨機(jī)移動(dòng)它們，直到達(dá)到一定程度停止。這個(gè)算法在時(shí)間復(fù)雜度上是O(n)的 正確性很高，運(yùn)行也相當(dāng)?shù)目臁?/p>

6.最后一個(gè)問(wèn)題轉(zhuǎn)化

  有的時(shí)候遇到問(wèn)題，不能立即想出策略，這個(gè)時(shí)候嘗試下將這個(gè)問(wèn)題轉(zhuǎn)化為常見(jiàn)的模型，利用常見(jiàn)模型和經(jīng)典的算法解決它。

  最常見(jiàn)的還是一些圖論上的問(wèn)題，將實(shí)際問(wèn)題轉(zhuǎn)化為流網(wǎng)絡(luò)或者二分圖。

原文鏈接：http://www.cnblogs.com/lxglbk/archive/2012/08/22/2650125.html

【編輯推薦】