亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

基本算法思想：遞歸+分治+動(dòng)態(tài)規(guī)劃+貪心+回溯+分支限界

EscapedDog / 2023人閱讀

摘要：代碼實(shí)現(xiàn)見(jiàn)下面評(píng)論對(duì)應(yīng)代碼動(dòng)態(tài)規(guī)劃基本思想和分治法基本思想有共同的地方，不同的是子問(wèn)題往往不是獨(dú)立的，有事母問(wèn)題要借助子問(wèn)題的解來(lái)判斷，因此把已經(jīng)計(jì)算好的問(wèn)題記錄在表格中，后續(xù)如果需要查詢一下，可以避免重復(fù)計(jì)算，這是動(dòng)態(tài)規(guī)劃的基本思想。

作者：心葉
時(shí)間：2018-05-01 19:28

本文對(duì)應(yīng)github地址：https://github.com/yelloxing/...

以上實(shí)現(xiàn)了常見(jiàn)算法的java、c語(yǔ)言、javascrpt（或node.js）、python3和go語(yǔ)言實(shí)現(xiàn)，持續(xù)更新中。

下面針對(duì)一些基本的算法思想，給出大致的說(shuō)明和用例。

遞歸與分治策略 分治法的基本思想

把一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題相同，遞歸的解這些子問(wèn)題，然后把各個(gè)子問(wèn)題的解合并得到原問(wèn)題的解。

算法使用例子

【題目】

使用快速排序方法排列一個(gè)一維數(shù)組。

【思路】

對(duì)于輸入的子數(shù)組a[p:r]，按照一下3個(gè)步驟進(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：通過(guò)遞歸調(diào)用排序，分別對(duì)a[p:q-1]和a[q+1:r]進(jìn)行排序。
3）合并merge：合并a[p:q-1]，a[q]和a[q+1:r]返回為最終結(jié)果。

【代碼實(shí)現(xiàn)】

見(jiàn)下面評(píng)論對(duì)應(yīng)代碼

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

和分治法基本思想有共同的地方，不同的是子問(wèn)題往往不是獨(dú)立的，有事母問(wèn)題要借助子問(wèn)題的解來(lái)判斷，因此把已經(jīng)計(jì)算好的問(wèn)題記錄在表格中，后續(xù)如果需要查詢一下，可以避免重復(fù)計(jì)算，這是動(dòng)態(tài)規(guī)劃的基本思想。

不過(guò)動(dòng)態(tài)規(guī)劃具體實(shí)現(xiàn)起來(lái)多種多樣，不過(guò)都具有相同的填表格式，通常按照下面步驟設(shè)計(jì)算法：
1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；
2）遞歸的定義最優(yōu)值；
3）以自底向上的方式計(jì)算出最優(yōu)值；
4）通過(guò)計(jì)算最優(yōu)值時(shí)刻意記錄的判斷結(jié)果來(lái)構(gòu)造最優(yōu)解。

可以使用該算法思想設(shè)計(jì)算法的問(wèn)題一般會(huì)具有二個(gè)決定性的性質(zhì)：
1）最優(yōu)子結(jié)構(gòu)性質(zhì)；
2）子問(wèn)題重疊性質(zhì)。

備忘錄算法

和上面的算法思想差不多，不同的是備忘錄為每個(gè)解過(guò)的子問(wèn)題建立備忘錄以備需要的時(shí)候查看，避免了相同的問(wèn)題計(jì)算多次。

一般來(lái)說(shuō)，當(dāng)一個(gè)問(wèn)題的所有子問(wèn)題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃比備忘錄要好，因?yàn)椴粫?huì)有任務(wù)暫存且沒(méi)有多余的計(jì)算；當(dāng)子問(wèn)題空間中部分問(wèn)題不必解時(shí)，用備忘錄比較好。

不過(guò)上面不是絕對(duì)的，這樣說(shuō)只是想?yún)^(qū)別一下二個(gè)思想的不同，具體的時(shí)候還是要根據(jù)業(yè)務(wù)場(chǎng)景來(lái)在保證可行的前提下選擇更好的方法。

算法使用例子

【題目】

給定n個(gè)矩形{A1,A2,...,An},其中Ai與Ai+1是可乘的，由于矩陣滿足結(jié)合律，不同的加括號(hào)方法計(jì)算次數(shù)不一樣，求最優(yōu)的加括號(hào)方法。

【思路】

分別計(jì)算有1，2，3，...，n個(gè)矩陣的最優(yōu)解，計(jì)算i個(gè)時(shí)候，全部的i-1的最優(yōu)解已經(jīng)記錄下來(lái)了，保證計(jì)算不重復(fù)。

【代碼實(shí)現(xiàn)】

見(jiàn)下面評(píng)論對(duì)應(yīng)代碼

貪心算法 基本思想

算法思想很簡(jiǎn)單，和字面意思一樣，每次都選擇對(duì)自己最有利的，不過(guò)這是有條件的，只有在滿足條件下每次選擇最有利自己的才可以獲取最優(yōu)解。

貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)是該思想最重要的性質(zhì)：
1）貪心選擇性質(zhì)：所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇達(dá)到。
2）最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有此性質(zhì)。

算法使用例子

【題目】

有一批集裝箱要裝上一艘載重為c的輪船，其中集裝箱i的重量為wi，要求在裝貨體積不受限制的條件下盡力多裝集裝箱的解。

【思路】

先排序，然后選擇從最輕的開(kāi)始裝貨物。

【代碼實(shí)現(xiàn)】

這里就不提供具體代碼了，因?yàn)楦杏X(jué)沒(méi)有什么意義，最重要的是要先確定問(wèn)題滿足貪心選擇性質(zhì)，這樣在很多時(shí)候，可以更容易的解決問(wèn)題，這點(diǎn)很重要。

回溯法 基本思想

說(shuō)的直白點(diǎn)就是深度優(yōu)先方式系統(tǒng)搜索問(wèn)題的算法。

算法使用例子

【題目】

有一批共n個(gè)集裝箱要裝上兩艘載重方別為c1和c2的輪船上，其中集裝箱i的重量為wi，且全部集裝箱重量不大于兩艘載重之和，問(wèn)是否有一個(gè)裝載方案完成裝載。

【思路】

對(duì)第一艘船，構(gòu)造一個(gè)0/1樹(shù)，0代表不選擇，1代表選擇，然后分別去從根節(jié)點(diǎn)試圖爬到葉節(jié)點(diǎn)，去一一記錄下來(lái)可行的，選擇最小的為解，余下的判斷第二艘船是否裝的下即可。

【代碼實(shí)現(xiàn)】

見(jiàn)下面評(píng)論對(duì)應(yīng)代碼

分支限界 基本思想

對(duì)比回溯法就很容易思考，用廣度優(yōu)先的辦法，不斷擴(kuò)大當(dāng)前節(jié)點(diǎn)的孩子為當(dāng)前節(jié)點(diǎn)，主要是求解一個(gè)最優(yōu)解，算法相比回溯法要簡(jiǎn)單些。

算法使用例子

【題目】

有一批共n個(gè)集裝箱要裝上兩艘載重方別為c1和c2的輪船上，其中集裝箱i的重量為wi，且全部集裝箱重量不大于兩艘載重之和，問(wèn)是否有一個(gè)裝載方案完成裝載。

【思路】

借助隊(duì)列，一層層來(lái)檢查，找到最優(yōu)解。

【代碼實(shí)現(xiàn)】

見(jiàn)下面評(píng)論對(duì)應(yīng)代碼

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/107711.html

相關(guān)文章

  • 校招社招必備核心前端面試問(wèn)題與詳細(xì)解答

    摘要：本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識(shí)點(diǎn)。此外還有網(wǎng)絡(luò)線程，定時(shí)器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機(jī)制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)...

    DevTalking 評(píng)論0 收藏0

  • 校招社招必備核心前端面試問(wèn)題與詳細(xì)解答

    摘要：本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識(shí)點(diǎn)。此外還有網(wǎng)絡(luò)線程，定時(shí)器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機(jī)制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)...

    jonh_felix 評(píng)論0 收藏0

  • 校招社招必備核心前端面試問(wèn)題與詳細(xì)解答

    摘要：本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識(shí)點(diǎn)。此外還有網(wǎng)絡(luò)線程，定時(shí)器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機(jī)制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)...

    Rango 評(píng)論0 收藏0

  • 看動(dòng)畫(huà)輕松理解「遞歸」與「動(dòng)態(tài)規(guī)劃」

    摘要：程序員小吳打算使用動(dòng)畫(huà)的形式來(lái)幫助理解遞歸，然后通過(guò)遞歸的概念延伸至理解動(dòng)態(tài)規(guī)劃算法思想。因此，分治策略一般用來(lái)解決子問(wèn)題相互對(duì)立的問(wèn)題，稱為標(biāo)準(zhǔn)分治，而動(dòng)態(tài)規(guī)劃用來(lái)解決子問(wèn)題重疊的問(wèn)題。難點(diǎn)就在于找出動(dòng)態(tài)規(guī)劃中的這三個(gè)概念。 在學(xué)習(xí)「數(shù)據(jù)結(jié)構(gòu)和算法」的過(guò)程中，因?yàn)槿肆?xí)慣了平鋪直敘的思維方式，所以「遞歸」與「動(dòng)態(tài)規(guī)劃」這種帶循環(huán)概念（繞來(lái)繞去）的往往是相對(duì)比較難以理解的兩個(gè)抽象知識(shí)點(diǎn)。...

    cnio 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<