|
五大常用算法之五：分支限界法
摘要: 分支限界法 一、基本描述 類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出T中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。 （1）分支搜索算法 所謂“分支”就是采用廣度優(yōu)先的策略，依次搜索E-...閱讀全文
五大常用算法之四：回溯法
摘要: 1、概念 回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。 回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。 許多復(fù)雜的，規(guī)模較大的問題都可以使用回...閱讀全文
五大常用算法之三：貪心算法
摘要: 貪心算法 一、基本概念： 所謂貪心算法是指，在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 貪心算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。 所以對所采用的貪心...閱讀全文
五大常用算法之二：動(dòng)態(tài)規(guī)劃算法
摘要: 一、基本概念 動(dòng)態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動(dòng)態(tài)規(guī)劃。二、基本思想與策略 基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時(shí)，列出各種可能的局部解，通過決策保留那些有可能達(dá)到...閱讀全文
五大常用算法之一：分治算法
摘要: 分治算法一、基本概念 在計(jì)算機(jī)科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)&hellip...閱讀全文
|
|
|
