資訊專欄INFORMATION COLUMN
摘要：代碼實現(xiàn)見下面評論對應(yīng)代碼動態(tài)規(guī)劃基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經(jīng)計算好的問題記錄在表格中，后續(xù)如果需要查詢一下，可以避免重復(fù)計算，這是動態(tài)規(guī)劃的基本思想。
作者：心葉
時間：2018-05-01 19:28
本文對應(yīng)github地址：https://github.com/yelloxing/...
以上實現(xiàn)了常見算法的java、c語言、javascrpt（或node.js）、python3和go語言實現(xiàn)，持續(xù)更新中。
下面針對一些基本的算法思想，給出大致的說明和用例。
遞歸與分治策略 分治法的基本思想把一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題相互獨立且與原問題相同，遞歸的解這些子問題，然后把各個子問題的解合并得到原問題的解。
算法使用例子【題目】
使用快速排序方法排列一個一維數(shù)組。
【思路】
對于輸入的子數(shù)組a[p:r]，按照一下3個步驟進(jìn)行排序：
1）分解divide：以a[p]為基準(zhǔn)元素將a[p:r]劃分成3段a[p:q-1]，a[q]和a[q+1:r]，其中a[q]不小于a[p:q-1]中的任何元素且不大于a[q+1:r]中的任何元素，下標(biāo)q在劃分中確定。
2）遞歸求解conquer：通過遞歸調(diào)用排序，分別對a[p:q-1]和a[q+1:r]進(jìn)行排序。
3）合并merge：合并a[p:q-1]，a[q]和a[q+1:r]返回為最終結(jié)果。
【代碼實現(xiàn)】
見下面評論對應(yīng)代碼
動態(tài)規(guī)劃 基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經(jīng)計算好的問題記錄在表格中，后續(xù)如果需要查詢一下，可以避免重復(fù)計算，這是動態(tài)規(guī)劃的基本思想。
不過動態(tài)規(guī)劃具體實現(xiàn)起來多種多樣，不過都具有相同的填表格式，通常按照下面步驟設(shè)計算法：
1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；
2）遞歸的定義最優(yōu)值；
3）以自底向上的方式計算出最優(yōu)值；
4）通過計算最優(yōu)值時刻意記錄的判斷結(jié)果來構(gòu)造最優(yōu)解。
可以使用該算法思想設(shè)計算法的問題一般會具有二個決定性的性質(zhì)：
1）最優(yōu)子結(jié)構(gòu)性質(zhì)；
2）子問題重疊性質(zhì)。
和上面的算法思想差不多，不同的是備忘錄為每個解過的子問題建立備忘錄以備需要的時候查看，避免了相同的問題計算多次。
一般來說，當(dāng)一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃比備忘錄要好，因為不會有任務(wù)暫存且沒有多余的計算；當(dāng)子問題空間中部分問題不必解時，用備忘錄比較好。
不過上面不是絕對的，這樣說只是想?yún)^(qū)別一下二個思想的不同，具體的時候還是要根據(jù)業(yè)務(wù)場景來在保證可行的前提下選擇更好的方法。
算法使用例子【題目】
給定n個矩形{A1,A2,...,An},其中Ai與Ai+1是可乘的，由于矩陣滿足結(jié)合律，不同的加括號方法計算次數(shù)不一樣，求最優(yōu)的加括號方法。
【思路】
分別計算有1，2，3，...，n個矩陣的最優(yōu)解，計算i個時候，全部的i-1的最優(yōu)解已經(jīng)記錄下來了，保證計算不重復(fù)。
【代碼實現(xiàn)】
見下面評論對應(yīng)代碼
貪心算法 基本思想算法思想很簡單，和字面意思一樣，每次都選擇對自己最有利的，不過這是有條件的，只有在滿足條件下每次選擇最有利自己的才可以獲取最優(yōu)解。
貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)是該思想最重要的性質(zhì)：
1）貪心選擇性質(zhì)：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇達(dá)到。
2）最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有此性質(zhì)。
【題目】
有一批集裝箱要裝上一艘載重為c的輪船，其中集裝箱i的重量為wi，要求在裝貨體積不受限制的條件下盡力多裝集裝箱的解。
【思路】
先排序，然后選擇從最輕的開始裝貨物。
【代碼實現(xiàn)】
這里就不提供具體代碼了，因為感覺沒有什么意義，最重要的是要先確定問題滿足貪心選擇性質(zhì)，這樣在很多時候，可以更容易的解決問題，這點很重要。
回溯法 基本思想說的直白點就是深度優(yōu)先方式系統(tǒng)搜索問題的算法。
算法使用例子【題目】
有一批共n個集裝箱要裝上兩艘載重方別為c1和c2的輪船上，其中集裝箱i的重量為wi，且全部集裝箱重量不大于兩艘載重之和，問是否有一個裝載方案完成裝載。
【思路】
對第一艘船，構(gòu)造一個0/1樹，0代表不選擇，1代表選擇，然后分別去從根節(jié)點試圖爬到葉節(jié)點，去一一記錄下來可行的，選擇最小的為解，余下的判斷第二艘船是否裝的下即可。
【代碼實現(xiàn)】
見下面評論對應(yīng)代碼
分支限界 基本思想對比回溯法就很容易思考，用廣度優(yōu)先的辦法，不斷擴大當(dāng)前節(jié)點的孩子為當(dāng)前節(jié)點，主要是求解一個最優(yōu)解，算法相比回溯法要簡單些。
算法使用例子【題目】
有一批共n個集裝箱要裝上兩艘載重方別為c1和c2的輪船上，其中集裝箱i的重量為wi，且全部集裝箱重量不大于兩艘載重之和，問是否有一個裝載方案完成裝載。
【思路】
借助隊列，一層層來檢查，找到最優(yōu)解。
【代碼實現(xiàn)】
見下面評論對應(yīng)代碼
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/107711.html
摘要：本文總結(jié)了前端老司機經(jīng)常問題的一些問題并結(jié)合個人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識點。此外還有網(wǎng)絡(luò)線程，定時器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機經(jīng)常問題的一些問題并結(jié)合個...
摘要：本文總結(jié)了前端老司機經(jīng)常問題的一些問題并結(jié)合個人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識點。此外還有網(wǎng)絡(luò)線程，定時器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機經(jīng)常問題的一些問題并結(jié)合個...
摘要：本文總結(jié)了前端老司機經(jīng)常問題的一些問題并結(jié)合個人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識點。此外還有網(wǎng)絡(luò)線程，定時器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機經(jīng)常問題的一些問題并結(jié)合個...
摘要：程序員小吳打算使用動畫的形式來幫助理解遞歸，然后通過遞歸的概念延伸至理解動態(tài)規(guī)劃算法思想。因此，分治策略一般用來解決子問題相互對立的問題，稱為標(biāo)準(zhǔn)分治，而動態(tài)規(guī)劃用來解決子問題重疊的問題。難點就在于找出動態(tài)規(guī)劃中的這三個概念。 在學(xué)習(xí)「數(shù)據(jù)結(jié)構(gòu)和算法」的過程中，因為人習(xí)慣了平鋪直敘的思維方式，所以「遞歸」與「動態(tài)規(guī)劃」這種帶循環(huán)概念（繞來繞去）的往往是相對比較難以理解的兩個抽象知識點。...
閱讀 984·2021-11-23 09:51
閱讀 3470·2021-11-22 12:04
閱讀 2716·2021-11-11 16:55
閱讀 2921·2019-08-30 15:55
閱讀 3222·2019-08-29 14:22
閱讀 3351·2019-08-28 18:06
閱讀 1240·2019-08-26 18:36
閱讀 2126·2019-08-26 12:08
