分支限界法的基本思想：
求解目標(biāo)：分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出在某種意義下的最優(yōu)解。
搜索方式：以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)统捶。
在分支限界法中呈昔，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)」掖拢活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)服赎。在這些兒子結(jié)點(diǎn)中葵蒂，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中重虑。
此后践付，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程缺厉。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止永高。
分支限界法示例：
單源最短路徑：
問(wèn)題：給定一個(gè)帶權(quán)有向圖G=（V,E）隧土，其中每條邊的權(quán)是一個(gè)實(shí)數(shù)。另外乏梁，還給定V中的一個(gè)頂點(diǎn)次洼，稱(chēng)為源。現(xiàn)在要計(jì)算從源到其他所有各頂點(diǎn)的最短路徑長(zhǎng)度遇骑。這里的長(zhǎng)度就是指路上各邊權(quán)之和卖毁。
分析：
分支限界法的步驟如下：
1)按寬度優(yōu)先策略遍歷解空間樹(shù)
2)在遍歷過(guò)程中，對(duì)處理的每個(gè)結(jié)點(diǎn)i落萎，根據(jù)界限函數(shù)亥啦，估計(jì)沿該結(jié)點(diǎn)向下搜索所可能達(dá)到的完全解的目標(biāo)函數(shù)的可能取值范圍—界限bound(i)=[dow(i), up(i)]
3)?從中選擇使目標(biāo)函數(shù)取的極小值的結(jié)點(diǎn)優(yōu)先進(jìn)行寬度優(yōu)先搜索，從而不斷調(diào)整搜索方向练链，盡快找到問(wèn)題解翔脱。
在每次分支后，對(duì)凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支媒鼓。這樣届吁，解的許多子集（即搜索樹(shù)上的許多結(jié)點(diǎn)）就可以不予考慮了，從而縮小了搜索范圍绿鸣。
將這個(gè)圖轉(zhuǎn)化成樹(shù)的形式疚沐，如下所示：
創(chuàng)建隊(duì)列。 １．節(jié)點(diǎn)１入隊(duì)列潮模，Ｑ＝｛１｝亮蛔。
我們?nèi)〕鲫?duì)頭節(jié)點(diǎn)，作為擴(kuò)散節(jié)點(diǎn)擎厢，更新他的后代的值究流。此題中更新節(jié)點(diǎn)２，３动遭，４ 的距離芬探，并將他們加入隊(duì)列，Ｑ＝｛１厘惦，２灯节，３，４｝绵估。 完成后節(jié)點(diǎn)１出隊(duì)。Ｑ＝｛２卡骂，３国裳，４｝。
２.同樣全跨，重復(fù)１的步驟缝左，Ｑ＝｛３，４，５渺杉，６｝蛇数；
３.當(dāng)我們?nèi)〉焦?jié)點(diǎn)３時(shí)，我們發(fā)現(xiàn)源點(diǎn)－＞節(jié)點(diǎn)３－＞節(jié)點(diǎn)６的距離為11是越，大于１－２－６這條路徑的權(quán)重耳舅，所以１－３－６這條路徑之后我們不再考慮。 這就是“限界”（稱(chēng)為”剪枝“）的思想倚评。
４. 重復(fù)步驟浦徊，直到Ｑ為空。優(yōu)先隊(duì)列法方法和FIFO方法類(lèi)似天梧，區(qū)別在于優(yōu)先隊(duì)列每次取隊(duì)列元素中到源點(diǎn)距離最短的點(diǎn)盔性。
# -*- coding: utf-8 -*-
"""
Created on Sun Mar? 7 19:03:09 2021
@author: iron
"""
# Author:Iron
# 初始化圖參數(shù) 用字典初始初始化這個(gè)圖
G = {1: { 2: 4, 3: 2,4:5},
? ? 2: { 5: 7, 6: 5},
? ? 3: {6: 9},
? ? 4: {5: 2, 7: 7},
? ? 5: {8: 4},
? ? 6: {10:6},
? ? 7: {9: 3},
? ? 8: {10:7},
? ? 9: {10:8},
? ? 10:{}
? ? }
inf=9999
#保存源點(diǎn)到各點(diǎn)的距離，為了讓頂點(diǎn)和下標(biāo)一致呢岗，前面多了一個(gè)inf不用在意冕香。
length=[inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf]
Q=[]
#FIFO隊(duì)列實(shí)現(xiàn)
def branch(G,v0):
? ? Q.append(v0)
? ? dict=G[1]
? ? while len(Q)!=0:
? ? ? ? ? #隊(duì)列頭元素出隊(duì)
? ? ? ? ? head=Q[0]
? ? ? ? ? #松弛操作，并且滿(mǎn)足條件的后代入隊(duì)
? ? ? ? ? for key in dict:
? ? ? ? ? ? ? if length[head]+G[head][key]<=length[key]:
? ? ? ? ? ? ? ? ? ? length[key]=length[head]+G[head][key]
? ? ? ? ? ? ? ? ? ? Q.append(key)
? ? ? ? #松弛完畢后豫，隊(duì)頭出列
? ? ? ? ? del Q[0]
? ? ? ? ? if len(Q)!=0:
? ? ? ? ? ? ? dict=G[Q[0]]
'''
#優(yōu)先隊(duì)列法實(shí)現(xiàn)
def branch(G, v0):
? ? Q.append(v0)
? ? while len(Q) != 0:
? ? ? ? ? min=99999
? ? ? ? ? flag=0
? ? ? ? ? #找到隊(duì)列中距離源點(diǎn)最近的點(diǎn)
? ? ? ? ? for v in Q:
? ? ? ? ? ? ? if min > length[v]:
? ? ? ? ? ? ? ? ? ? min=length[v]
? ? ? ? ? ? ? ? ? ? flag = v
? ? ? ? ? head = flag
? ? ? ? ? dict=G[head]
? ? ? ? ? #找到擴(kuò)散點(diǎn)后進(jìn)行松弛操作
? ? ? ? ? for key in dict:
? ? ? ? ? ? ? if length[head] + G[head][key] <= length[key]:
? ? ? ? ? ? ? ? ? ? length[key] = length[head] + G[head][key]
? ? ? ? ? ? ? ? ? ? Q.append(key)
? ? ? ? ? #松弛完畢后悉尾，該擴(kuò)散點(diǎn)出隊(duì)
? ? ? ? ? Q.remove(head)
'''
branch(G,1)
print(length)
運(yùn)行結(jié)果：[9999, 0, 4, 2, 5, 7, 9, 12, 11, 15, 15]。
