基本算法策略的應(yīng)用和比較

1、最新資料推薦基本算法策略的應(yīng)用和比較基本算法策略的應(yīng)用和比較摘要：基本的算法策略主要有貪婪策略、遞推策略、遞歸策略、枚 舉策略、遞歸回溯策略、分治策略和動(dòng)態(tài)規(guī)劃策略等。各算法策略特點(diǎn)不同，適合的問題類型不同，但各算法策略間 也有著緊密的聯(lián)系。關(guān)鍵詞：算法策略、特點(diǎn)、應(yīng)用、比較1.概述 算法是指在解決問 題時(shí)，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程?，F(xiàn)在計(jì)算機(jī)能解決的實(shí)際問題種類繁多，解決問題的算法更是 不勝枚舉。但是還是有一些基本方法、策略是可以遵循的。算法策略和算法是有區(qū)別的，他們是算法設(shè)計(jì)中的兩個(gè)方面。算法策略是面向問題的，算法是面向?qū)崿F(xiàn)的，但是二者又是不 可分的，只有通過一定的算

2、法策略才能找出解決問題的具體算法?；镜乃惴ú呗灾饕胸澙凡呗浴⑦f推策略、遞歸策略、枚 舉策略、遞歸回溯策略、分治策略和動(dòng)態(tài)規(guī)劃策略等。不同算法策略的特點(diǎn)2. 1貪婪策略貪婪策略是對(duì)問題 要求比較嚴(yán)格的算法策略。貪婪策略解決問題是按一定順序，在只需考慮當(dāng)前局部信息的 情況下，就做出一定的決策，最終得出問題的解，即貪婪策略針對(duì) 的是通過局部最優(yōu)決策就能得到全局最優(yōu)決策的問題。2. 2遞推策略遞推策略和貪婪策略一樣也是由當(dāng)前問題的逐 步解決從而得到整個(gè)問題的解，它依賴的是信息間本身的遞推關(guān)系， 每一步不需要決策參與到算法中，遞推策略更多地用于計(jì)算。2. 3遞歸策略和遞推策略類似，遞歸策略是利用大問

3、題與其 子問題的遞推關(guān)系來解決問題。能采用遞歸描述的算法，通常有如下特征：為求解規(guī)模為n的問題，設(shè)法將它分解成規(guī)模較小的問題，然 后從這些小問題的解方便地構(gòu)造出大問題的解，并且這些規(guī)模較小 的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題， 并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別地，當(dāng)規(guī)模n=1時(shí)， 能直接得解。2. 4枚舉策略枚舉既是一個(gè)策略，也是一個(gè)算法，還是一 種分析問題的手段。枚舉策略的求解思路很簡單，就是對(duì)問題的所有可能的解逐一 嘗試，從而找出問題的真正解。當(dāng)然，這就要求所解問題的可能解是有限的、固定的、容易枚 舉的。枚舉策略多用于決策類問題，這類問題往往不易找出大

4、、小規(guī) 模間問題的關(guān)系，也不易對(duì)問題進(jìn)行分解，因此用嘗試的方法對(duì)整 體求解。2. 5遞歸回溯策略 類似于枚舉策略的思想，遞歸回溯策略通，最新資料推薦過遞歸嘗試遍歷問題各個(gè)可能解的通路，當(dāng)發(fā)現(xiàn)此路不通時(shí)，回溯 到上一步繼續(xù)嘗試別的通路。2. 6分治策略分治求解的一般是較復(fù)雜的問題，這類問題是 可以逐步被分解成容易解決的獨(dú)立的子問題，這些子問題解決后， 進(jìn)而將它們的解合成，就得到較大子問題的解，最終合成為總問題 的解。7動(dòng)態(tài)規(guī)劃策略動(dòng)態(tài)規(guī)劃策略與貪心策略類似，是通過多 階段決策過程來解決問題的。每個(gè)階段決策的結(jié)果是一個(gè)決策結(jié)果序列，最終哪一個(gè)是最優(yōu) 結(jié)果，取決于以后每個(gè)階段決策。因此，可以說動(dòng)態(tài)規(guī)

5、劃策略是高效率、高消費(fèi)的算法策略。算法策略的實(shí)際應(yīng)用 在算法設(shè)計(jì)的實(shí)際應(yīng)用中，遇到的 問題主要分為四類，它們主要適用的算法策略如下：（1）判定性問題：可用遞推法、遞歸法（2）計(jì)算問題：可用遞推法、遞歸法（3）最優(yōu)化問題：貪心算法、分治法、動(dòng)態(tài)規(guī)劃法、枚舉法（4）構(gòu)造性問題:貪心算法、分治法、廣度優(yōu)先搜索、深度優(yōu)先搜索4.算法 策略的比較 算法策略的中心思想是：將解決問題的過程歸納為可以用基本工具循環(huán)機(jī)制和遞歸機(jī)制 表示的規(guī)范操作。當(dāng)我們面臨實(shí)際的各種問題時(shí)，應(yīng)該首先分析它屬于上述常見問題中的哪一種。對(duì)于查找問題，它在實(shí)際運(yùn)用中主要用于搜索，而且要求時(shí)間 效率很高。若搜索的內(nèi)容是已經(jīng)排好序的線性表，這時(shí)應(yīng)該采用分治策略。若搜索的內(nèi)容是需要進(jìn)行增、刪、改的動(dòng)態(tài)查找表，則采用 動(dòng)態(tài)規(guī)劃策略。對(duì)于排序問題，在實(shí)際運(yùn)用中主要是內(nèi)排序，排序的目的主要是為了進(jìn)行快速查找，一般采用分治策略提高時(shí)間效率。對(duì)于圖問題，總是會(huì)涉及到最優(yōu)化問題，所以可針對(duì)不同問題 的特點(diǎn)，在動(dòng)態(tài)規(guī)劃策略、貪婪策略、回溯策略中選擇。對(duì)于組合問題，這幾種策略都可以用，但是分治策略和貪婪策 略的實(shí)際運(yùn)用范圍更廣。對(duì)于幾何問題，若涉及到數(shù)值計(jì)算，選用迭代策略。若涉及