曉強(qiáng)Deep Learning的讀書(shū)分享會(huì)，先從這里開(kāi)始，從大學(xué)開(kāi)始。大家好，我是曉強(qiáng)，計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)研究生在讀。我會(huì)不定時(shí)的更新我的文章，內(nèi)容可能包括深度學(xué)習(xí)入門(mén)知識(shí)，具體包括CV，NLP方向的基礎(chǔ)知識(shí)和學(xué)習(xí)的論文；網(wǎng)絡(luò)表征學(xué)習(xí)的相關(guān)論文解讀。當(dāng)然我每天的讀書(shū)心得也會(huì)分享給大家，可能涉及我們生活各個(gè)方面的書(shū)籍。我也會(huì)不定時(shí)回答大家的問(wèn)題與大家一同進(jìn)步，共同交流，互相監(jiān)督，結(jié)交更多的朋友。希望大家多留言，多交流，多多關(guān)照。我在這里等你一同學(xué)習(xí)，如果需要相關(guān)資料也可以私信我，進(jìn)入我們的群大家庭。

【曉白】今天正值高考，給大家加油。還是要堅(jiān)持下去的，努力終會(huì)有收獲，只為了追求那個(gè)曾經(jīng)的優(yōu)秀的自己。所以今天中午抽時(shí)間寫(xiě)了一篇分支限界法的文章。希望大家點(diǎn)贊，關(guān)注，支持一下。謝謝精神合伙人的支持和鼓勵(lì)。如果有準(zhǔn)備秋招的同學(xué)，也可以來(lái)看一下，對(duì)大家很有幫助。有任何疑問(wèn)可以私信，獲得我們大家庭的聯(lián)系方式，多多溝通，共同進(jìn)步。如果高考結(jié)束以后大家對(duì)計(jì)算機(jī)學(xué)習(xí)有一定興趣，或者家長(zhǎng)朋友和考生希望以后報(bào)考計(jì)算機(jī)，學(xué)習(xí)計(jì)算機(jī)的，也可以關(guān)注我，看更多文章；詳情私信，了解更多。可以咨詢，輔導(dǎo)入門(mén)。今天更新第六章的前面先補(bǔ)充一下回溯法的效率。

第五章回溯法的效率分析：

一個(gè)回溯算法的效率在很大程度上依賴于以下幾個(gè)因素：

(1)產(chǎn)生X[k]的時(shí)間

(2)滿足顯約束的x[k]值的個(gè)數(shù)

(3)計(jì)算約束函數(shù)Constraint的時(shí)間

(4)計(jì)算上界函數(shù)Bound的時(shí)間

(5)滿足約束函數(shù)和上界函數(shù)約束的所有x[k]的個(gè)數(shù)，在選擇約束函數(shù)時(shí)通常存在著生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷

重排原理：

解空間的結(jié)構(gòu)一經(jīng)選定，影響回溯法效率的前四個(gè)因素就可以確定，只剩下生成結(jié)點(diǎn)的數(shù)目是可變的，它將隨問(wèn)題的具體內(nèi)容以及結(jié)點(diǎn)的不同生成方式而變動(dòng)。

對(duì)于一個(gè)問(wèn)題的具體實(shí)例，我們很難預(yù)測(cè)回溯法的算法行為。特別是我們很難估計(jì)出回溯法在解這一具體實(shí)例時(shí)所產(chǎn)生的結(jié)點(diǎn)數(shù)。這是我們?cè)诜治龌厮莘ㄐ蕰r(shí)遇到的主要困難。

蒙特卡羅方法：

估計(jì)回溯法將要產(chǎn)生的結(jié)點(diǎn)數(shù)目。主要思想是在解空間樹(shù)上產(chǎn)生一條隨機(jī)的路徑，然后沿此路徑來(lái)估算解空間樹(shù)中滿足約束條件的結(jié)點(diǎn)總數(shù)。

算法Estimate從解空間樹(shù)的根結(jié)點(diǎn)開(kāi)始選取一條隨機(jī)路徑,計(jì)算回溯法生成的結(jié)點(diǎn)總數(shù)m。

Estimate (int n, Type *x)

{ int m=1,r=1,k=1;

while (k<=n)

{

SetType T=x[k]的滿足約束的可取值集合；

if （Size(T)==0）return m;

r*= Size(T); // Size(T)得到集合T大小

m+=r;

x[k]=Choose(T); //Choose(T) 從集合T隨機(jī)地選一個(gè)元素

k++;

}

return m;

}

當(dāng)用回溯法求解某一具體問(wèn)題時(shí)，可用算法Estimate估算回溯法生成的結(jié)點(diǎn)數(shù)。

若要估算得更精確些，可選取若干條不同的隨機(jī)路徑（通常不超過(guò)20條），分別對(duì)各隨機(jī)路徑估計(jì)結(jié)點(diǎn)總數(shù)，然后再取這些結(jié)點(diǎn)總數(shù)的平均值，得到m的估算值。

例：8后問(wèn)題

利用顯約束排除那些有2個(gè)皇后在同一行或同一列的方法，也有8！種不同的方法。8后問(wèn)題的解空間樹(shù)的結(jié)點(diǎn)總數(shù)是：

回溯法產(chǎn)生的結(jié)點(diǎn)數(shù)m是解空間樹(shù)的結(jié)點(diǎn)總數(shù)的1.55%左右。說(shuō)明回溯法的效率大大高于窮舉法。

第六章 分支限界法

分支限界法類似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上搜索解的算法。但是，分支限界法與回溯法有不同的求解目標(biāo):回溯法的求解目標(biāo)是找出T中滿足約束條件的所有解，或任意一個(gè)解;分支限界法的求解目標(biāo)則是找出T中使得某一目標(biāo)函數(shù)值達(dá)到極小或極大的解，即問(wèn)題在某種意義下的最優(yōu)解。

由于求解目標(biāo)不同， 導(dǎo)致分支限界法與回溯法在解空間樹(shù)T上搜索的算法有兩點(diǎn)不同：

（1）回溯法以深度優(yōu)先的方式搜索解空間樹(shù)T;分支限界法以廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)T。

（2）回溯法一般只通過(guò)約束條件，而分支限界法不僅通過(guò)約束條件，而且通過(guò)目標(biāo)函數(shù)的限界來(lái)減少無(wú)效搜索，提高求解效率。

分支限界法的搜索策略是：

在擴(kuò)展結(jié)點(diǎn)處，先生成其所有兒子結(jié)點(diǎn)（使其變?yōu)榛罱Y(jié)點(diǎn)），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。這種方法就稱為分支限界法。

一、分支限界法的基本思想

從活動(dòng)結(jié)點(diǎn)表選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的原則體現(xiàn)在對(duì)活結(jié)點(diǎn)表的組織方式（即，數(shù)據(jù)結(jié)構(gòu)）之中。常見(jiàn)的活結(jié)點(diǎn)表的組織方式有以下二種：

隊(duì)列式(FIFO)

優(yōu)先隊(duì)列式(PQ, Prioroty Queue)---優(yōu)先隊(duì)列可用堆實(shí)現(xiàn)

所以，常見(jiàn)的分支限界法分為：

（1）隊(duì)列式(FIFO)分支限界法

（2）優(yōu)先隊(duì)列式（PQ）分支限界法

用隊(duì)列式分支限界法求解單源最短路徑問(wèn)題

按隊(duì)列式分支限界法求解單源最短路徑的算法：

SSShortestPaths(v)

{ E.i=v;

E.length=0;

dist[v]=0; //源點(diǎn)V到源點(diǎn)V的最近距離

INSERT (Q, E); //Q是一個(gè)隊(duì)列

while(!Empty(Q))

{ E=DELETE(Q);

if(dist[E.i]<E.length) continue; //源點(diǎn)V到頂點(diǎn)i的當(dāng)前最近距離

for(j=1; j<=n; j++)

if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j]))

{ dist[j]=E.length+c[E.i][j];

prev[j]=E.i;

N.i=j;

N.length=dist[j];

INSERT(Q,N);

}

}

}

用優(yōu)先隊(duì)列式分支限界法求解單源最短路徑問(wèn)題

(1) 按隊(duì)列式分支限界法求解多段圖最短路徑的算法：

ShortestPath(v)

{E.i=v; E.length=0;

Bound=inf; //也可用貪心法先確定一個(gè)初始界限

INSERT (Q, E); //Q是隊(duì)列

while(!Empty(Q))

{ E=DELETE(Q);

if(Bound<E.length) continue;

for (j=1; j<=n; j++)

{ if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<Bound))

{ prev[j]=E.i;

if（j是終點(diǎn)）

{Bound=E.length+c[E.i][j]；continue; }

N.i=j;

N.length= E.length+c[E.i][j];

INSERT(Q,N);

}

}

}

}

按優(yōu)先隊(duì)列式分支限界法求解多段圖問(wèn)題的算法：

template <class Type>

void graph <Type> :: ShortestPath(int v)

{MinHeap <MinHeapNode <Type> > H(1000); //定義小根堆的容量為1000

MinHeapNode <Type> E;

E.i=v; E.length=0; //定義源為初始擴(kuò)展結(jié)點(diǎn)

Bound=inf; //開(kāi)始搜索問(wèn)題的解空間

while(true)

{ if(E.length<Bound)

for(j=1; j<=n; j++)

if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<Bound))

{ prev[j]=E.i;

if（j是終點(diǎn)）

{Bound=E.length+c[E.i][j]；continue; }

MinHeapNode <Type> N;

N.i=j; N.length= E.length+c[E.i][j];

H.Insert(N);

}

try { H.DeleteMin(E);} //從優(yōu)先隊(duì)列取下一個(gè)擴(kuò)展結(jié)點(diǎn)

catch (OutOfBound) {break;} // 優(yōu)先隊(duì)列空

}

}

今天算法設(shè)計(jì)分析的第六章更新完畢，明天我會(huì)繼續(xù)更新對(duì)于第五章，和第六章的補(bǔ)充知識(shí)，敬請(qǐng)期待。當(dāng)然，后續(xù)我也打算給小伙伴們更新一下計(jì)算理論的介紹以便大家全面的學(xué)習(xí)。7.7-7.10是高考的日子，我也會(huì)繼續(xù)更新，希望與大家一起堅(jiān)持下去。祝順利，金榜題名都圓大學(xué)夢(mèng)。莘莘學(xué)子們，如果對(duì)計(jì)算機(jī)學(xué)習(xí)感興趣也可以私信留言咨詢，學(xué)習(xí)，推薦資料，一對(duì)一輔導(dǎo)交流都可以。加入大家庭，一起學(xué)習(xí)。感興趣，關(guān)注我，文章。連接如下，

曉強(qiáng)DL：第五章 回溯法（Backtrack）?zhuanlan.zhihu.com曉強(qiáng)DL：圖像處理必讀論文之AlexNet?zhuanlan.zhihu.com曉強(qiáng)DL：圖像處理必讀論文之二：VGG網(wǎng)絡(luò)?zhuanlan.zhihu.com曉強(qiáng)DL：第四章 貪心算法(Greedy Algorithms)?zhuanlan.zhihu.com曉強(qiáng)DL：第三章 動(dòng)態(tài)規(guī)劃(Dynamic Programming )?zhuanlan.zhihu.com曉強(qiáng)DL：第二章 遞歸與分治?zhuanlan.zhihu.com曉強(qiáng)DL：計(jì)算機(jī)算法設(shè)計(jì)與分析第一章 算法概述?zhuanlan.zhihu.com曉強(qiáng)DL：Opencv圖像處理(一)?zhuanlan.zhihu.com曉強(qiáng)DL：OpenCV圖像處理（二）?zhuanlan.zhihu.com曉強(qiáng)DL：Opencv圖像處理(三)?zhuanlan.zhihu.com曉強(qiáng)DL：Opencv圖像處理 （四）?zhuanlan.zhihu.com

總結(jié)

以上是生活随笔為你收集整理的分支限界法实现最优装载c++_分支限界法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。