莆田制作公司網(wǎng)站b站推廣入口2023破解版
上文講到算法的概念、復(fù)雜度,本文給大家介紹具體的算法思想,讓大家對(duì)算法設(shè)計(jì)理念有個(gè)認(rèn)識(shí),后續(xù)再分別介紹各種算法。
算法思想
算法是解決問(wèn)題的一種思想和方法,其基本思想是將一個(gè)復(fù)雜問(wèn)題分解為多個(gè)簡(jiǎn)單的子問(wèn)題,然后通過(guò)一定的邏輯和操作方法將這些子問(wèn)題的解組合成原問(wèn)題的解。
分而治之
把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題,再把子問(wèn)題分成更小的子問(wèn)題,直到最后子問(wèn)題小到可以簡(jiǎn)單的直接求解,原問(wèn)題的解即子問(wèn)題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ),如排序算法(快速排序,歸并排序),傅立葉變換(快速傅立葉變換),大數(shù)據(jù)中的MR,現(xiàn)實(shí)中如漢諾塔游戲。
分治法對(duì)問(wèn)題有一定的要求:
- 該問(wèn)題縮小到一定程度后,就可以輕松解決
- 問(wèn)題具有可拆解性,不是一團(tuán)無(wú)法拆分的亂麻
- 拆解后的答案具有可合并性。能組裝成最終結(jié)果
- 拆解的子問(wèn)題要相互獨(dú)立,互相之間不存在或者很少有依賴關(guān)系
動(dòng)態(tài)規(guī)劃
基本思想與分治法類似,也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題(階段),按順序求解子階段,前一子問(wèn)題的解,為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí),列出各種可能的局部解,通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解,丟棄其他。依次解決各子問(wèn)題,最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。
與分治法最大的不同在于,分治法的思想是并發(fā),動(dòng)態(tài)規(guī)劃的思想是分步。該方法經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的,其下一個(gè)子階段的求解往往是建立在上一個(gè)子階段的解的基礎(chǔ)上。動(dòng)態(tài)規(guī)劃算法同樣有一定的適用性場(chǎng)景要求:
- 最優(yōu)化解:拆解后的子階段具備最優(yōu)化解,且該最優(yōu)化解與追蹤答案方向一致
- 流程向前,無(wú)后效性:上一階段的解決方案一旦確定,狀態(tài)就確定,只會(huì)影響下一步,而不會(huì)反向影響
- 階段關(guān)聯(lián):上下階段不是獨(dú)立的,上一階段會(huì)對(duì)下一階段的行動(dòng)提供決策性指導(dǎo)。這不是必須的,但是如果具備該特征,動(dòng)態(tài)規(guī)劃算法的意義才能更大的得到體現(xiàn)
貪心算法
同樣對(duì)問(wèn)題要求作出拆解,但是每一步,以當(dāng)前局部為目標(biāo),求得該局部的最優(yōu)解。那么最終問(wèn)題解決時(shí),得到完整的最優(yōu)解。也就是說(shuō),在對(duì)問(wèn)題求解時(shí),總是做出在當(dāng)前看來(lái)是最好的選擇,而不去從整體最優(yōu)上加以考慮。從這一角度來(lái)講,該算法具有一定的場(chǎng)景局限性。
- 要求問(wèn)題可拆解,并且拆解后每一步的狀態(tài)無(wú)后效性(與動(dòng)態(tài)規(guī)劃算法類似)
- 要求問(wèn)題每一步的局部最優(yōu),與整體最優(yōu)解方向一致。至少會(huì)導(dǎo)向正確的主方向。
回溯算法
回溯算法實(shí)際上是一個(gè)類似枚舉的搜索嘗試過(guò)程,在每一步的問(wèn)題下,列舉可能的解決方式。選擇某個(gè)方案往深度探究,尋找問(wèn)題的解,當(dāng)發(fā)現(xiàn)已不滿足求解條件,或深度達(dá)到一定數(shù)量時(shí),就返回,嘗試別的路徑?;厮莘ㄒ话氵m用于比較復(fù)雜的,規(guī)模較大的問(wèn)題。有“通用解題法”之稱。
- 問(wèn)題的解決方案具備可列舉性,數(shù)量有限
- 界定回溯點(diǎn)的深度。達(dá)到一定程度后,折返
分支限界
與回溯法類似,也是一種在空間上枚舉尋找最優(yōu)解的方式。但是回溯法策略為深度優(yōu)先。分支法為廣度優(yōu)先。分支法一般找到所有相鄰結(jié)點(diǎn),先采取淘汰策略,拋棄不滿足約束條件的結(jié)點(diǎn),其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從存活表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)操作對(duì)象