撒撒算法胡椒面兒調試程序做個伴兒

1、一、算法概述算法與過程過程與算法是解決問題的一種方法的逐步描述，(1)是由若干條指令組成的有窮序列；(2)每條指令的意義都是確定的；(3)具有零個或多個輸入；(4)產生若干個輸出；(5)算法要求其執(zhí)行時間是有限的 (終止性) 。過程的執(zhí)行時間可能是無限的。程序程序是某個算法或過程的在計算機上的一個具體的實現(xiàn)。程序是依賴于程序設計語言的，甚至依賴于計算機結構的。算法是脫離具體的計算機結構和程序設計語言的。算法的復雜性算法的復雜性是指算法運行時所需要的計算機資源的量多少，所需資源量越多則復雜性越高，反之所需資源量越少則復雜性越低。其中最為重要的是：時間復雜性：需要時間的資源量?？臻g復雜性：需要空間

2、的資源量。這里人們通常更為關注的是時間復雜性。決定算法復雜性的因素算法的復雜性取決于(1)求解問題的規(guī)模；(2)具體的輸入數(shù)據(jù)；(3)算法本身的設計。二、遞歸與分治遞歸的概念簡單地說，遞歸就是用自己來定義自己。一般地說，一個遞歸過程P可以表示為基語句S(不含P)和P自身的組合：P (S, P)這樣的表示包含了過程不終止的可能，因此遞歸算法應更準確地表述為P if B then Q else (S, P) 其中Q也不包含P，B為遞歸終止條件。遞歸元遞歸算法的思想是將對較大規(guī)模的對象的操作歸結為對較小規(guī)模的對象實施同樣的操作。這種規(guī)模的變化就體現(xiàn)在遞歸算法的變元中的一類(一個或幾個)變元上，這類變

3、元被稱之為遞歸元。遞歸元的變化是在遞歸定義中確定的，它的變化應能導致遞歸算法的終止。在遞歸算法的設計中遞歸元是非常重要的。分治法分治法的基本做法是：(1)將規(guī)模為n的問題分解為k個規(guī)模較小的子問題。這些子問題相互獨立且與原問題相同。(2)遞歸地解這些子問題。(3)然后將子問題合并得到原問題的解。分治法的時間復雜性：子問題的復雜性當然低于原問題。但是整體上能否降低復雜性還取決于合并。通過降低合并的復雜性可以降低原問題求解的復雜性。三、貪心算法貪心算法的特點貪心算法總是作出在當前來看是最好的選擇。就是說，貪心算法并不從整體最優(yōu)上來考慮，所作出的選擇只是某種意義上的局部最優(yōu)選擇。當然希望貪心算法得到

4、的最終結果是最優(yōu)的?？墒秦澬乃惴ú⒉荒鼙ＷC最終結果是最優(yōu)的。不過，在許多的情況下，應用貪心算法能夠得到整體最優(yōu)解；并且在一些情況下，即使得到的不是最優(yōu)解，也是一個很好的近似解。貪心算法的一般框架初始化；重復執(zhí)行以下的操作： 選擇當前可以選擇的(相容)最優(yōu)解；將所選擇的當前解加入到問題的解中；直至滿足問題求解的結束條件。貪心算法的基本要素貪心算法的基本要素是：貪心選擇性質。所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)解的選擇，即貪心選擇來達到。貪心選擇每次選取當前最優(yōu)解，因此它依賴以往的選擇，而不依賴于將來的選擇。貪心算法通常以自頂向下的方式進行，每次貪心選擇就將原問題轉化為規(guī)

5、模更小的子問題。四、動態(tài)規(guī)劃動態(tài)規(guī)劃的基本思想將原問題分解為若干個子問題，先求子問題的解，然后從這些子問題的解得到原問題的解。這些子問題的解往往不是相互獨立的。在求解的過程中，許多子問題的解被反復地使用。為了避免重復計算，動態(tài)規(guī)劃算法采用了填表來保存子問題解的方法。在算法中用表格來保存已經求解的子問題的解，無論它是否會被用到。當以后遇到該子問題時即可查表取出其解，避免了重復計算。動態(tài)規(guī)劃的基本要素最優(yōu)子結構：問題的最優(yōu)解是由其子問題的最優(yōu)解所構成的。重疊子問題：子問題之間并非相互獨立的，而是彼此有重疊的。最優(yōu)子結構性質使我們能夠以自底向上的方式遞歸地從子結構的最優(yōu)解構造出問題的最優(yōu)解。因為子問

6、題重疊，所以存在著重復計算。這樣就可以用填表保存子問題解的方法來提高效率。動態(tài)規(guī)劃的基本方法動態(tài)規(guī)劃通?？梢园匆韵聨讉€步驟進行：(1)找出最優(yōu)解的性質，并刻畫其結構特征；(2)遞歸地定義最優(yōu)值；(3)以自底向上的方式計算出各子結構的最優(yōu)值并添入表格中保存；(4)根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。步驟13是動態(tài)規(guī)劃算法的基本步驟。若需要最優(yōu)解，則必須執(zhí)行第4步，為此還需要在第3步中記錄構造最優(yōu)解所必需的信息。與分治法相比，相同之處是也將原問題分解為若干子問題，再遞歸求解；不同之處是所分解的子問題彼此并不獨立，而是互有重疊?；舅枷胧窃毂碛涗浺呀獾淖訂栴}，再次遇到時僅查表即可，避免了重復計算

7、，提高效率。通常用于求解具有最優(yōu)性質的問題，而且其子問題也具有最優(yōu)性質(最優(yōu)子結構性質)。實現(xiàn)方法通常為自底向上的遞歸形式，但也可以采用自上而下的形式(備忘錄方法)。五、回溯法回溯法是一種通用的算法，實為深度優(yōu)先的搜索方法。回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。八皇后問題就是回溯算法的典型，第一步按照順序放一個皇后，然后第二步符合要求放第2個皇后，如果沒有位置符合要求，那么就要改變第一個皇后的位置，重新放第2個皇后的位置，直到找到符合條件的位置就可以了。回溯在迷宮搜索中使用很常見，就是這條路走不通，然后返回前一個路口，繼續(xù)下一條路?；厮菟惴ㄕf白了就是窮舉

8、法。不過回溯算法使用剪枝函數(shù)，剪去一些不可能到達 最終狀態(tài)（即答案狀態(tài)）的節(jié)點，從而減少狀態(tài)空間樹節(jié)點的生成?；厮莘ㄊ且粋€既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統(tǒng)搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束?；厮莘梢赃f歸實現(xiàn)

9、，也可以迭代實現(xiàn)?；厮莘ㄍǔＧ蠼馊悊栴}：(1)求排列：時間復雜性為O(f(n)n!)；(2)求子集：時間復雜性為O(f(n)2n)；(3)求路徑：時間復雜性為O(f(n)kn)。這里f(n)為處理一個結點的時間復雜性。六、分支限界法分支限界法是最佳優(yōu)先搜索法分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先在內)的搜索法。分支限界法將要搜索的結點按評價函數(shù)的優(yōu)劣排序，讓好的結點優(yōu)先搜索，將壞的結點剪去。所以準確說，此方法應稱為界限剪支法。分支限界法中有兩個要點：(1)評價函數(shù)的構造；(2)搜索路徑的構造。七、概率算法概率計算概率計算就是在算法中可采用隨機選擇計算的步驟、元素或參數(shù)等。它的基本特征是計算具有

10、不確定性。它的解也不一定是最優(yōu)解。它在很大程度上能降低算法的復雜度。在非標準算法中普遍了應用概率方法，主要有：(1)直接用概率進行數(shù)值計算；(2)用概率/隨機進行選擇；(3)利用概率加速搜索或避免陷于局部最優(yōu)。進化算法達爾文的進化論：適者生存，優(yōu)勝劣汰。1975年霍蘭(Holland)提出了遺傳算法，通過模擬生物進化的過程概率搜索最優(yōu)解。遺傳算法首先產生所謂的個體種群，每個個體是編碼的二進制串(又稱為染色體)。然后對個體進行隨機的選擇，再經過復制、交叉和變異產生下一代的種群。就這樣經過一代一代的進化，最終獲得滿意的個體(即問題的解)。人工神經網絡1943年McCulloch和Pitts提出神經

11、元的數(shù)學模型，即MP模型。1957年Rosenblatt設計制作了“感知機”。這是第一個多層的人工神經網絡。第一個高潮期。1969年之后進入低潮。1980年以后重新進入高潮，并得到蓬勃的發(fā)展。目前人們普遍認為突破圖林機模型的將是人工神經網絡。這是下一代計算機的主體。人工神經網絡人工神經網絡就是人工神經元所構成的網絡。主要有前饋網絡和反饋網絡兩種形式。前饋網絡有若干層神經元組成，第i層的神經元只接受第i1層輸出的信息，而不接受同層或高層的輸出信息。反饋網絡中的神經元可以接受外加輸入和其它神經元包括自身的反饋輸入。人工神經網絡的學習神經元的計算主要依賴于權重wi，而權重wi是通過學習獲得的。所謂學

12、習(又稱訓練)是首先給權重賦予一個初值，然后將大量的訓練樣板(包括正例和反例)輸入計算機，人工神經網絡自己不斷地調整相應的權重。學習的方式主要分為：有監(jiān)督的學習和自適應的學習兩種形式，以及它們的改進。八、調試代碼的技巧 一、理解代碼 二、休息休息 三、漸增式測試 先從單個模塊開始測試，然后每次將測試后的一個模塊添加到系統(tǒng)中并測試，系統(tǒng)像“滾雪球”一樣越滾越大，直到把所有的模塊都組裝并測試完畢。四、務求簡單 在調試的過程中你會把錯誤想得越來越復雜，所以這時務求簡單。將代碼按照功能和邏輯拆分會變得“務求簡單”。 五、懂得放棄 不要舍不得代碼修改代碼原則尋找合適的代碼記錄每個修改通讀源代碼修改最少耦

13、合度最低尋找合適的代碼修改代碼不如自己重寫代碼，除非時間、人力方面不允許。 修改代碼之前必須先讀懂對方的源代碼，這花的時間可能會比自己寫花的時間更多。必須在這兩者之間取得平衡。改變自身需求，使需求適應下載的代碼，達到直接使用，無需修改。 比如你打算找一個實現(xiàn)某些功能的代碼，可是找了很多代碼，要不只能實現(xiàn)其中的某些功能，要不就是某些功能不完全符合你的要求，這時就必須改變自己最原始的想法，找一個最接近的代碼。因為有時候你原先的需求就是錯誤的。尋找合適的代碼代碼必須架構合理，編碼規(guī)范，這樣的代碼安全系數(shù)才比較高。源代碼作者經常更新。 源代碼公布后，如果有什么安全漏洞，整個系統(tǒng)就暴露在cracker面

14、前。只有源代碼作者根據(jù)用戶的建議不斷修復Bug和增加功能，才是可信賴的系統(tǒng)。尋找合適的代碼推薦網站 和 、 。 是網上最大的開放源代碼聚合地。有大量的源代碼，分類組織，便于查找。 內事不明問百度，外事不明問谷歌，這2個搜索引擎，基本上你可以找到任何東西，如果你使用了正確的關鍵字。記錄每個修改使用文本文件記錄下修改，以便快速恢復 因為開始我們只是試用一個系統(tǒng)，或者只是試著加入一些功能，如果加入功能失敗，你又不知道加入了那些東西，這時你可以全部刪除你剛才的修改，把原始文件重新解壓，根據(jù)文本文件的記錄恢復到某個版本。記錄下打算增加或者修改的事情，記為todo，完成后放入done區(qū)。記錄每個修改有了這

15、個記錄，就可以在下次推出新版本后繼續(xù)修改。每件事都有記錄是一個好的習慣。在源代碼里也可加上記錄。通讀源代碼通讀代碼包括通讀目錄下的所有文件，特別是Readme，Manual，help，guide，doc，faq這種開頭的文檔。很多簡單的安裝出錯其實在手冊里面都已經告訴你了。修改別人的程序時一定要通讀代碼，這樣才可以保證修改了不加入新的Bug，并且可以充分利用原先的代碼。有時為了增加一個新功能，你可以寫了一個下午的代碼，過幾天后發(fā)現(xiàn)源代碼里面其實有這個功能函數(shù)，只需調用某個函數(shù)即可。這就是沒有通讀源代碼的結果。通讀源代碼用文本文件記錄下代碼的函數(shù)功能，一些值得注意的地方。一定必須確保你知道這個軟

16、件在干什么，管理員有幾個入口，有幾個內置帳號需要關閉等等。修改最少定位修改位置，可以使用Editplus的目錄全文檢索功能。根據(jù)用戶界面的文字做關鍵字。Web的用戶界面文字可能不準確，可以查看web源代碼或者縮小文字單位。如果一個功能有多個修改方法，使用修改最少的那種。雖然這種可能破壞了代碼的架構。耦合度最低增加進去的代碼應該盡量跟原程序比較分離?？偟脑瓌t是：源代碼就像刺猬，能不碰就不碰。把增加的代碼包裝成一個過程或者函數(shù)，在正確的地方調用一下即可。這樣是為了代碼的美觀。代碼如果寫得很亂，程序便不易被閱讀與修改，所以，在編寫代碼時要注意以下幾點：(1)注釋：寫注釋雖然要占用一定的時間，但在閱讀和修改代碼時卻會節(jié)省很多的時間。所以，建議大家在定義一個函數(shù)時，在函數(shù)的第一行寫出函數(shù)的作用，再用一行解釋函數(shù)的參數(shù)，并在每個變量的定義語句后注釋出其作用。 (2)變量和函數(shù)的命名：每個程序都會使用很多的變量和函數(shù)，如果隨意命名變量與函數(shù)，每次使用時還得在變量或函數(shù)的定義語句處查出它的數(shù)據(jù)類型及名稱，而且隨意命名還會造成變量與函數(shù)重復定義。建議大家使用匈牙利命名法，方法是：每個變量或函數(shù)的開頭都以其數(shù)據(jù)類型的縮寫命名，然后再加上代表這個變量或函數(shù)的作用的英文單詞簡寫共同組成變量或函數(shù)的名稱。