一，概述
算法策略和算法是有區(qū)別的,它們是算法設(shè)計(jì)中的兩個(gè)方面，算法策略是面向問題的,算法是面向?qū)崿F(xiàn)的；
但二者又是不可分的,首先是通過算法策略才找出解決問題的算法，其次對(duì)于用不同算法求解的問題算法策略是自然不同的。
二，算法策略
1）遞推策略：“遞推法”和貪心算法一樣也是由當(dāng)前問題的逐步解決從而得到整個(gè)問題的解，只是依賴的是信息間本身的遞推關(guān)系，每一步不需要策略參與到算法中，它們更多地用于計(jì)算。
2）遞歸策略：遞歸法是利用大問題與其子問題間的遞歸關(guān)系來解決問題的。每次找出大問題與小的子問題之間的關(guān)系,直到小的子問題很容易解決，再由小的子問題的解導(dǎo)出大問題的解。。例如：漢諾塔問題
3）窮舉策略：對(duì)所有可能的解逐一嘗試。4）遞歸回溯策略：類似于窮舉法的思想,遞歸回朔法通過遞歸嘗試遍問題各個(gè)可能解的通路，發(fā)現(xiàn)此路不通時(shí)回朔到上一步繼續(xù)嘗試別的通路。
5）分治策略：求解的則是較復(fù)雜的問題，這類問題是可以被分解成獨(dú)立的子問題來解決的，將兩個(gè)或兩個(gè)以上的獨(dú)立子問題的解“合成”，就得到較大的子問題的解，最后合成為總問題的解。（注意一定是可以分解成獨(dú)立子問題，否則會(huì)重復(fù)計(jì)算公共子問題）
6）動(dòng)態(tài)規(guī)劃策略：動(dòng)態(tài)規(guī)劃法與貪心法類似，要求問題具有最優(yōu)子結(jié)構(gòu)（即最優(yōu)解包含子問題的最優(yōu)解），是一種自底向上的求解思路，與遞歸正好相反，每次求解到一個(gè)階段時(shí)，該階段求解所依賴的子問題已經(jīng)完全求解完畢，因此每一步的求解都是在直到全部所需信息的情況下進(jìn)行的，因此可以得到全局最優(yōu)解。
7）貪心策略：如果想要得到最優(yōu)解，需要對(duì)問題性質(zhì)有更嚴(yán)格的要求，除了要有最優(yōu)子結(jié)構(gòu)外，還要求問題具有貪婪選擇性質(zhì)。具體來說就是：貪心是一種策略，即每一步都要選擇當(dāng)前看來最好的，做完此選擇后便將問題化為一個(gè)（僅僅一個(gè)）子問題，這是一個(gè)順序的求解過程，每一步都是單獨(dú)考慮，只考慮局部最優(yōu)，因?yàn)椴]有完成對(duì)之后子問題的求解，所以貪心算法不能完成對(duì)整個(gè)解空間的搜索，因此通常不能得到最優(yōu)解。除非問題具有貪婪選擇性質(zhì)。所謂貪婪選擇性質(zhì)就是問題經(jīng)過一次貪婪選擇后只能形成一個(gè)子問題，這樣求解空間實(shí)際上就是一個(gè)線性的空間，貪心算法可以得到最優(yōu)解。是一種自頂向下求解思路。
三，算法策略之間關(guān)系
1）分治法”與“動(dòng)態(tài)規(guī)劃法”
· 都是遞歸思想的應(yīng)用，找出大問題與小的子問題之間的關(guān)系,直到小的子問題很容易解決，再由小的子問題的解導(dǎo)出大問題的解。
·分治法的特征之一是所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。
· 動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余。
2）全面逐一嘗試、比較“窮舉法”、“枚舉法”、“遞歸回溯法”
· 若問題中不易找到信息間的相互關(guān)系，也不能分解為獨(dú)立的子問題,似乎只有把各種可能情況都考慮到,并把全部解都列出來之后,才能判定和得到最優(yōu)解。
·枚舉法算法的實(shí)現(xiàn)依賴于循環(huán),通過循環(huán)嵌套枚舉問題中各種可能的情況。
· 對(duì)于規(guī)模不固定的問題就無(wú)法用固定重?cái)?shù)的循環(huán)嵌套來枚舉了,有的問題可能通過變換枚舉對(duì)象也能用循環(huán)嵌套枚舉實(shí)現(xiàn),但更多的任意指定規(guī)模的問題是靠遞歸回朔法來“枚舉”或“遍歷”各種可能的情況。
3）回溯與分支限界策略
·回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。
·一般情況下，回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解的方案，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。
4）深度優(yōu)先與廣度優(yōu)先
· 深度優(yōu)先：通常深度優(yōu)先搜索法不全部保留結(jié)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)棧中彈出刪去，一般在數(shù)據(jù)棧中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是解空間樹的深度，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索是一種有效的求解方法。
· 廣度優(yōu)先：一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計(jì)中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無(wú)回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快。
5）動(dòng)態(tài)規(guī)劃與搜索算法
·搜索算法：在解決最優(yōu)化問題的算法中，搜索可以說是“萬(wàn)能”的。所以動(dòng)態(tài)規(guī)劃可以解決的問題，搜索也一定可以解決。動(dòng)態(tài)規(guī)劃要求階段決策具有無(wú)后向性，而搜索算法沒有此限止。
·動(dòng)態(tài)規(guī)劃算法在時(shí)間效率上的優(yōu)勢(shì)是搜索無(wú)法比擬的，但動(dòng)態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無(wú)效狀態(tài)。可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動(dòng)態(tài)規(guī)劃要低很多。
·動(dòng)態(tài)規(guī)劃是自底向上的遞推求解，而無(wú)論深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解。
聯(lián)系客服
