分支限界法实现最优装载c++_分支限界法
曉強(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)題。
- 上一篇: python输入文件名读取文件_[Pyt
- 下一篇: 联发科天玑9300芯片正式发布 跑分超2