日韩av在线影音先锋,超碰操网,久久久久久亚洲AV无码蜜芽老妇,欧美搞逼,精品伊人大香蕉,天天干,天天日,天天插,人人人透午夜久久精品嫖妓av一区二区三区 ,国产视频swag,美女性高潮视频

分枝限界

關(guān)注那些不斷已被他人成功應(yīng)用的新思路。你的原創(chuàng)思想只應(yīng)該應(yīng)用在那些你正在研究的問題上。

——托馬斯·愛迪生(1847-1931)

這周到來的太快，

沒想到這么快就迎來了考試。

干了這碗烤柿粥！

（然而我至今還沒開始復(fù)習(xí)）

沒辦法，試可以亂考，文不能不更

那么就來看看這次認(rèn)（隨）真（意）完成的內(nèi)容吧！

1.方法概述

2.FIFO實(shí)現(xiàn)

3.priority queue實(shí)現(xiàn)

方法概述

對(duì)老板寫過的內(nèi)容，肯定是要先放鏈接的：

干貨 | 10分鐘帶你全面掌握branch and bound（分支定界）算法-概念篇

干貨 | 10分鐘搞懂branch and bound算法的代碼實(shí)現(xiàn)附帶java代碼

干貨 | 10分鐘教你用branch and bound（分支定界）算法求解TSP旅行商問題

老板寫的是java，學(xué)過的童鞋可以康康，不過可能比較難。

那么，拋玉引磚，接下來就開始正文啦。

在談到分枝限界法時(shí)，我們一般都會(huì)提到回溯法。因?yàn)檫@兩種方法有很多的類似點(diǎn)。關(guān)于回溯法，不了解的同學(xué)可以康康往期的內(nèi)容，一些提到過的定義就不再講解了：

?【算法學(xué)習(xí)】再談回溯法

回溯法和分支限界都是以構(gòu)造一顆解空間樹為基礎(chǔ)的?；厮莘ㄍㄟ^深度優(yōu)先搜索的思想，選擇一條可行的路徑，一路走下去；而分支限界法可以根據(jù)多種規(guī)則生成節(jié)點(diǎn)，如廣度優(yōu)先搜索，再結(jié)合剪枝函數(shù)（我們?cè)诨厮莘ɡ镆部梢允褂茫┻M(jìn)行剪枝，得出最優(yōu)解。

限界函數(shù)的使用我們?cè)诨厮莘ɡ镆蔡岬竭^，是在尋找最優(yōu)解時(shí)使用的一種優(yōu)化方法，如果我們使用回溯法解決最優(yōu)解問題也可以使用（其實(shí)回溯法尋找最優(yōu)解的過程本身就可以看作是分枝限界通過深度優(yōu)先LIFO的棧實(shí)現(xiàn)）。而在分枝限界中，這是必不可少的一部分。這也就意味著，回溯法可以找到所有解（這里糾正一下那篇文章的錯(cuò)誤），而分枝限界一般解決最優(yōu)解問題。

限界函數(shù)的作用是判斷后續(xù)結(jié)點(diǎn)對(duì)應(yīng)的選擇是否有機(jī)會(huì)得出問題的最優(yōu)解。如果不可能，直接剪枝掉解空間樹的這一條分支，停止遍歷。

在大致了解分支限界的流程后，我們發(fā)現(xiàn)，主要的難點(diǎn)在于：

（1）解空間樹的構(gòu)造，即節(jié)點(diǎn)的生成順序

（2）剪枝函數(shù)的確定，即如何判斷是否可能得到最優(yōu)解

下一個(gè)擴(kuò)展節(jié)點(diǎn)的選擇（或者說對(duì)樹的搜索方法）一般有如下方式：

隊(duì)列式（FIFO）分支界限法（廣度優(yōu)先）：按照隊(duì)列先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。這種搜索可以用FIFO queue實(shí)現(xiàn)，即通過隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。

優(yōu)先隊(duì)列式分支限界法（最小損耗優(yōu)先）：按照優(yōu)先隊(duì)列規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。這種搜索可以用優(yōu)先隊(duì)列priority queue來實(shí)現(xiàn)。

為了判斷能否剪枝，我們一般需要兩個(gè)額外的條件：

1.對(duì)于一顆狀態(tài)空間樹的每一個(gè)節(jié)點(diǎn)所代表的部分解，我們要提供一種方法，計(jì)算出通過這個(gè)部分解繁衍出的任何解在目標(biāo)函數(shù)上的最佳值邊界。（即可能達(dá)到的最優(yōu)解）

2.目前求得的最佳解的值。（記錄即可）

如果可以得到這些信息，我們可以拿某個(gè)節(jié)點(diǎn)的邊界值和目前求得的最佳解進(jìn)行比較。只要符合下面三種中的一種原因，我們就會(huì)中止掉它的在當(dāng)前節(jié)點(diǎn)上的查找路徑：

1.該節(jié)點(diǎn)的邊界值不能超越目前最佳解的值。

2.該節(jié)點(diǎn)無法代表任何可行解，因?yàn)樗呀?jīng)違反了問題的約束。

3.該節(jié)點(diǎn)代表的可行解的子集只包含一個(gè)單獨(dú)的點(diǎn)（因此無法給出更多的選擇）。在這種情況下，我們拿這個(gè)可行解在目標(biāo)函數(shù)上的值和目前求得的最佳解進(jìn)行比較，如果新的解更好一些的話，就用前者替換后者。

我們結(jié)合圖片看一看解空間樹的建立，順便具象化一下隊(duì)列的概念（盜圖，請(qǐng)忽略邊上的數(shù)字）：

1.節(jié)點(diǎn)１入隊(duì)列queue＝｛１｝，創(chuàng)建隊(duì)列。

2.我們?nèi)〕鲫?duì)尾節(jié)點(diǎn)tail，作為父節(jié)點(diǎn)，更新他的后代的值。此題中更新節(jié)點(diǎn)２，３，４　的距離，并將他們加入隊(duì)列，queue＝｛１，２，３，４｝。完成后節(jié)點(diǎn)１出隊(duì)。queue＝｛２，３，４｝。

3.同樣，重復(fù)2的步驟，queue＝｛３，４，５，６｝；

4.當(dāng)我們?nèi)〉焦?jié)點(diǎn)３時(shí)，出于“限界”（稱為”剪枝“）的考慮，我們需要剪去某些邊；或者說本身就無法擴(kuò)展出新的邊。

5.重復(fù)步驟，直到queue為空（head=tail）。

優(yōu)先隊(duì)列法方法和FIFO方法類似，區(qū)別在于優(yōu)先隊(duì)列每次取隊(duì)列元素中最優(yōu)的解先進(jìn)行拓展，我們?cè)诮酉聛淼睦又芯唧w說明。

FIFO實(shí)現(xiàn)

我們先來介紹一下基于廣度優(yōu)先搜索實(shí)現(xiàn)的分枝限界法。例題依舊是我們熟悉的0-1背包問題。

這里我們采用之前回溯法里講到的限界函數(shù)。但是在我們的隊(duì)列中，每層只判斷一個(gè)物品是否被選中，所以bag_v不到最后一層都一直為0。所以，我們需要先找出一個(gè)bag_v來進(jìn)行對(duì)比。我們可以考慮用貪婪算法找出一個(gè)較優(yōu)解。

說實(shí)話，針對(duì)這題，個(gè)人認(rèn)為還是回溯法比較快捷，寫代碼的時(shí)候全程無語(yǔ)，感覺在做一件很沒意義的事。。。（尤其是debug的過程中）本想選別的例題，但找不到太好的，而01背包又比較熟悉，就當(dāng)是熟悉FIFO的分枝限界吧。（編的時(shí)候還真是改錯(cuò)了好久。。。）

具體講解參考代碼注釋，感覺有點(diǎn)傻，還是將就著看吧。。。

Code

//01背包問題  分枝限界法  隊(duì)列實(shí)現(xiàn)#include using namespace std;
int n,bag_v,bag_w;int bag[105],w[105],v[105],order[105]; //存儲(chǔ)初始編號(hào) double perp[105]; //單位重量?jī)r(jià)值 
class node   //隊(duì)列； {  public:    node(int w,int v,int isput,node front);    node(int num);    node();     double cur_w; //當(dāng)前重量     double cur_v; //當(dāng)前價(jià)值     int put[105]; //put表示當(dāng)前是否被選中，將選中的物品存入bag中     int cur;      //判斷到第cur個(gè)物品 }; node bagque[105]=node();
node::node(int w,int v,int isput,node front) {  cur_w=w+front.cur_w ;  cur_v=v+front.cur_v ;  cur=front.cur +1;  for (int i=1;i      put[i]=front.put[i];  put[cur]=isput; }
node::node(int num) {  cur_w=0;  cur_v=0;  cur=0;  for (int i=1;i<=num;i++)      put[i]=0;}
node::node() {  cur_w=0;  cur_v=0;  cur=0;  for (int i=1;i<=10;i++)      put[i]=0;}
//按照單位重量?jī)r(jià)值排序，這里用冒泡 void bubblesort(){    int i,j;    int temporder = 0;    double temp = 0.0;    for(i=1;i<=n;i++)        perp[i]=v[i]/w[i]; //計(jì)算單位價(jià)值（單位重量的物品價(jià)值）    for(i=1;i<=n-1;i++)    {        for(j=i+1;j<=n;j++)            if(perp[i]//冒泡排序perp[],order[],sortv[],sortw[]        {            temp = perp[i];  //冒泡對(duì)perp[]排序交換             perp[i]=perp[i];            perp[j]=temp;            temporder=order[i];//冒泡對(duì)order[]交換             order[i]=order[j];            order[j]=temporder;            temp = v[i];//冒泡對(duì)v[]交換             v[i]=v[j];            v[j]=temp;            temp=w[i];//冒泡對(duì)w[]交換             w[i]=w[j];            w[j]=temp;        }    }}
//基于平均價(jià)值優(yōu)先的貪婪算法，用于剪枝 int greedy ()   {  double greedyvalue=0;  double greedyweight=0;  for (int i=1;i<=n;i++)  {      if(greedyweight+w[i]<=bag_w)      {          greedyvalue+=v[i];          greedyweight+=w[i];      }  }  return greedyvalue;}
//計(jì)算上界函數(shù)，功能為剪枝double bound(int i,int cur_v,int cur_w){   //判斷當(dāng)前背包的總價(jià)值cur_v＋剩余容量可容納的最大價(jià)值<=當(dāng)前最優(yōu)價(jià)值    double leftw= bag_w-cur_w;//剩余背包容量    double b = cur_v;//記錄當(dāng)前背包的總價(jià)值cur_v,最后求上界    //以物品單位重量?jī)r(jià)值遞減次序裝入物品    while(i<=n && w[i]<=leftw)    {        leftw-=w[i];        b+=v[i];        i++;    }    //裝滿背包    if(i<=n)        b+=v[i]/w[i]*leftw;    return b;//返回計(jì)算出的上界}
void FIFO( ){  bagque[1]=node(n);  int head=2,tail=1;  while (head>tail)  {     int current=bagque[tail].cur+1;     if(bagque[tail].cur>=n)   //判斷邊界         {        if(bagque[tail].cur_v >=bag_v)        //是否超過最大價(jià)值        {            bag_v=bagque[tail].cur_v;         //更新最大價(jià)值            for(int i=1;i<=n;i++)                      bag[order[i]]=bagque[tail].put[i];             }        tail++;        continue;      }      //如若可以選擇當(dāng)前物品，則直接加入隊(duì)列;      //如果不選擇，先計(jì)算上界函數(shù)，以判斷是否將其減去      if(bagque[tail].cur_w+w[current]<=bag_w)//選擇加入當(dāng)前物品cur的情況入列       {        bagque[head]=node(w[current],v[current],1,bagque[tail]);    head++;      }      if(bound(current,bagque[tail].cur_v,bagque[tail].cur_w)>bag_v)  //不選cur的情況入列     {        bagque[head]=node(0,0,0,bagque[tail]);        head++;      }            tail++;  }}

int main(){    int i;    bag_v=0; //初始化背包最大價(jià)值    //輸入數(shù)據(jù)     cout<<"請(qǐng)輸入背包最大容量:"<<endl;;    cin>>bag_w;    cout<<"請(qǐng)輸入物品個(gè)數(shù):"<<endl;    cin>>n;    cout<<"請(qǐng)依次輸入物品的重量:"<<endl;    for(i=1;i<=n;i++)         cin>>w[i];    cout<<"請(qǐng)依次輸入物品的價(jià)值:"<<endl;    for(i=1;i<=n;i++)         cin>>v[i];    for (i=1;i<=n;i++)         order[i]=i;    bubblesort();    bag_v=greedy();    FIFO();    cout<<"最大價(jià)值為:"<<endl;    cout<endl;    cout<<"物品的編號(hào)依次為:"<<endl;
    for(i=1;i<=n;i++)        if(bag[i]==1)             cout<" ";    cout<<endl;    return 0;}

priority queue實(shí)現(xiàn)

接下來是優(yōu)先隊(duì)列式分枝限界法，我們以單源最短路徑問題為例。

最短路徑依舊是一個(gè)熟悉的問題，可以通過過去的推文了解，就不多解釋了：

?【算法學(xué)習(xí)】最短路徑問題

先簡(jiǎn)單介紹一下優(yōu)先隊(duì)列：

優(yōu)先隊(duì)列可以分為最大、最小優(yōu)先隊(duì)列。相比于先進(jìn)先出的普通隊(duì)列，優(yōu)先隊(duì)列每次都是最大（或最?。┑脑貎?yōu)先出隊(duì)。

在單源最短路徑問題中，我們采用的剪枝函數(shù)則類似于之前提到的Dijkstra算法（其實(shí)它本身也就是源于BFS），通過尋找當(dāng)前離原點(diǎn)最近的點(diǎn)進(jìn)行下一步操作；通過松弛操作得出下一層子節(jié)點(diǎn)。說是最優(yōu)優(yōu)先出隊(duì)，其實(shí)這里也只有最小點(diǎn)一個(gè)出隊(duì)拓展新子點(diǎn)了。之前推文里有提到具體算法，可以參考一下，就不難理解了。

這里暫時(shí)不深入講解如何實(shí)現(xiàn)優(yōu)先隊(duì)列，而是直接通過頭文件調(diào)用。由于我也不是很習(xí)慣用優(yōu)先隊(duì)列，這里參考了網(wǎng)上的代碼。具體講解參見注釋：

Code：

//優(yōu)先隊(duì)列式分支限界法 解單源最短路徑問題//來源互聯(lián)網(wǎng) ，作者csdn zzzsdust 原文鏈接見后文 
#include   //頭文件中附帶有優(yōu)先隊(duì)列 using namespace std;
class MinHeapNode  //最小堆 {public:    int id;    int length; //從起始點(diǎn) v 到點(diǎn) id 的距離public:    friend bool operator < (const MinHeapNode &a, const MinHeapNode &b)   //運(yùn)算符重載     {        return a.length < b.length;    }    friend bool operator > (const MinHeapNode &a, const MinHeapNode &b)    {        return a.length > b.length;    }};
const int max_ = 0x3f3f3f;int Graph[100][100];  //輸入兩點(diǎn)間距離 int dist[100];    //到原點(diǎn)距離 int pre[100];   //記錄最短路徑中的前一個(gè)點(diǎn) int n, m, v;void OutPutPath(int i)   //輸出到原點(diǎn)的最短路徑 {    if(i == pre[i])    {        printf("%d", i);        return;    }    else    {        OutPutPath(pre[i]);        printf(" %d", i);    }}
void OutPut(){    for(int i = 1; i <= n; ++i)    {        if(i != v)        {            printf("點(diǎn) %d 到 %d 的最短距離是 %d\n", v, i, dist[i]);            printf("路徑為：");            OutPutPath(i);            printf("\n");        }    }}
//劃重點(diǎn)??！ void ShortestPaths(){    priority_queuevector, greater > q;     /*調(diào)用優(yōu)先隊(duì)列 ，  第一個(gè)參數(shù)是數(shù)值類型;  第二個(gè)參數(shù)是存放數(shù)值的容器類型，一般用vector;  第三個(gè)參數(shù)為排序規(guī)則。   greater升序，即小的先出；less降序，即大的先出。    具體函數(shù)：      1.插入         .push()函數(shù)     2.取出頂端元素   .top()函數(shù)     3.刪除頂端元素   .pop()函數(shù)     4.大小         .size()函數(shù)     5.是否為空      .empty()函數(shù)    */    memset(dist, max_, sizeof(dist)); //初始化距離     dist[v] = 0;     pre[v] = v;    MinHeapNode cur_p;    cur_p.id = v;    cur_p.length = 0;    q.push(cur_p);    while(true)    {        if(q.empty() == 1) //全員松弛完畢             break;        cur_p = q.top(); //取出堆頂?shù)狞c(diǎn)（距離最短）         q.pop(); // 在優(yōu)先隊(duì)列中刪除剛?cè)〕龅狞c(diǎn)
        for(int i = 1; i <= n; ++i)        {            if(Graph[cur_p.id][i] != max_ && (cur_p.length + Graph[cur_p.id][i] < dist[i]))  //剪枝函數(shù)，也就是Dijkstra中的松弛             {                dist[i] = cur_p.length + Graph[cur_p.id][i];                pre[i] = cur_p.id;                MinHeapNode temp;                temp.id = i;                temp.length = dist[i];                q.push(temp);            }        }    }  }
void InPut()   //輸入數(shù)據(jù) {    int x, y, len;    scanf("%d %d %d", &v, &n, &m);  //以v為原點(diǎn)，n個(gè)點(diǎn)，m條邊。     memset(Graph, max_, sizeof(Graph));   //默認(rèn)設(shè)置為最大，表示無法到達(dá)     for(int i = 1; i <= m; ++i)    {        scanf("%d %d %d", &x, &y, &len);        Graph[x][y] = Graph[y][x] = len; //無向圖?。?    }}
int main(){    InPut();    ShortestPaths();    OutPut();}

Reference：

https://blog.csdn.net/qjt19950610/article/details/89476784?

https://blog.csdn.net/m0_38015368/article/details/80449014

《Introduction to The Design and Analysis of Algorithms》?

by Anany Levitin? ? ?潘彥譯?

后記：

分枝限界法最有名的作用還是求解整數(shù)規(guī)劃問題。

這部分問題我們暫且擱一會(huì)兒，等未來再講。

（關(guān)鍵看我什么時(shí)候編出正確的代碼）

其實(shí)到這里，一個(gè)部分的內(nèi)容也結(jié)束了。

這一部分主要是講算法設(shè)計(jì)思想。

然而rookie的我連數(shù)據(jù)結(jié)構(gòu)的不過關(guān)。。。

因此打算接下來一段時(shí)間惡補(bǔ)一波。

可能會(huì)寫相關(guān)的內(nèi)容。敬請(qǐng)期待~~

-The End-

文/真的真的要考試了的新手舟

版/馬上要開啟下一個(gè)篇章的小白舟

碼/這期繼續(xù)減少內(nèi)容的工人舟

審/帥氣師兄短短的路走走停停

【算法學(xué)習(xí)】分枝限界法