現(xiàn)實(shí)生活中有很多問題，人為不好解決，但利用計(jì)算機(jī)速度快,，不出錯(cuò)的特性，可以很方便的解決這些問題,，下面簡單說說我在程序設(shè)計(jì)中解決實(shí)際問題的一些常見思想,，高手可以忽略掉，我也是無聊了隨便寫寫而已,。

1.枚舉最優(yōu)解時(shí)的情況

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

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

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

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

假設(shè)最優(yōu)解的圓上沒有2個(gè)點(diǎn),，如上圖，那么通過微量的平移操作,，可以使圓接觸平面上的2個(gè)點(diǎn),，并且園內(nèi)的點(diǎn)數(shù)不會減少，它的結(jié)果不會比圓上沒有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)解,，逆向思維解決問題。

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

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

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

3.排序思想

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

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

4.二分,，三分。

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

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

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

比如求函數(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è)問題可以轉(zhuǎn)換為二分,，將函數(shù)求導(dǎo)，二分其在0的位置即可,，這個(gè)涉及到高等數(shù)學(xué),，不贅述了。

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

5.隨機(jī)算法

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

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

簡單說說模擬退火（后面我打算專門寫一篇模擬退火的隨筆）

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

第一次接觸這個(gè)問題的時(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)中垂線上,，這里是對的。 然后假設(shè)這個(gè)圓心在在中垂線上移動(dòng),，如果滿足要求,，包圍了所有點(diǎn)。

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

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

這里說一下模擬退火的思想,。 大概依照一個(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è)問題轉(zhuǎn)化

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

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