運籌學筆記---分支定界 (branch and bound)求解TSP問題
1、方法簡介
分支定界我理解就是一種有規律的列舉，所以它是可以求出精確的解。分支定界幾個關鍵點就是設定界限函式，隨著搜尋的過程中逐漸更新界限，直至上界和下界重合；構建節點表，在每個分支的過程中需要將資訊記錄下來，按照某一個標準在節點表裡儲存，後續取點刪點。
2、方法應用
下邊以b&b在求解tsp中的應用來說明，不同問題思路相近，大同小異。求解步驟如下：
（1）規約費用矩陣
。即使費用矩陣中每一行每一列都包含0元素，此時規約係數就是該問題的一個下界。
（2）選擇分支邊
。在（a，b）處分支可以有兩個選擇：一個是選擇從a點到b點；另外就是選擇從a點不到b點。如果選擇了a到b那就就應該從費用矩陣裡將第a行和第b列對應的費用值剔除，因為tsp問題裡每一個點只能經過一次。然後還有防止路徑成環修改其他的費用值，這個後邊專門說。如果選擇a點不到b點，表明a，b點都沒有被選，只需要將費用矩陣裡（a，b）對應的費用值改為正無窮即可，表明後續不再選擇a點到b點。
（3）將每個分支的矩陣加入優先佇列中，按照下界從小到大排序。
每次分支後，從優先佇列裡選擇下界最小的那張表進行後續分支。
（4）防止成環處理。防止成環，也就是說所有點還沒有訪問完就回到起點，即第一次分支選擇點a到點b，第二次分支選擇點b到點c，那麼後續分支中如果選擇點c到點a，那麼就會形成a，b，c的環路。導致解是不可行的，因此需要做出修改。
3、演算法實現
Point類
public
class
point
{
public
double
c
［］［］；
//費用矩陣
public
int
rowNumber
［］；
// 費用矩陣的行號
public
int
colNumber
［］；
//費用矩陣對應的列號
public
int
ad
［］；
//路徑
public
int
k
；
// 階數
public
double
lowbound
；
// 下界
public
point
（
int
count
）{
c
=
new
double
［
count
］［
count
］；
rowNumber
=
new
int
［
count
］；
colNumber
=
new
int
［
count
］；
ad
=
new
int
［
Main
。
city
］；
k
=
count
；
}
}
public
class
BBTSP
{
public
static
int
n
=
Main
。
city
；
/**
* 計算某一行最小值和次小值
* @param p 點
* @param row p的第row行
* @return 返回 第row行的最小值和次小值
*/
double
［］
row_min
（
point
p
，
int
row
）{
double
result
［］=
new
double
［
2
］；
if
（
p
。
c
［
row
］［
0
］<
p
。
c
［
row
］［
1
］）{
result
［
0
］=
p
。
c
［
row
］［
0
］；
result
［
1
］=
p
。
c
［
row
］［
1
］；
}
else
{
result
［
0
］=
p
。
c
［
row
］［
1
］；
result
［
1
］=
p
。
c
［
row
］［
0
］；
}
for
（
int
i
=
2
；
i
<
p
。
k
；
i
++）{
if
（
p
。
c
［
row
］［
i
］<
result
［
0
］）{
result
［
1
］=
result
［
0
］；
result
［
0
］=
p
。
c
［
row
］［
i
］；
}
else
if
（
p
。
c
［
row
］［
i
］<
result
［
1
］）{
result
［
1
］=
p
。
c
［
row
］［
i
］；
}
}
return
result
；
}
double
［］
col_min
（
point
p
，
int
col
）{
double
result
［］=
new
double
［
2
］；
if
（
p
。
c
［
0
］［
col
］<
p
。
c
［
1
］［
col
］）{
result
［
0
］=
p
。
c
［
0
］［
col
］；
result
［
1
］=
p
。
c
［
1
］［
col
］；
}
else
{
result
［
0
］=
p
。
c
［
1
］［
col
］；
result
［
1
］=
p
。
c
［
0
］［
col
］；
}
for
（
int
i
=
2
；
i
<
p
。
k
；
i
++）{
if
（
p
。
c
［
i
］［
col
］<
result
［
0
］）{
result
［
1
］=
result
［
0
］；
result
［
0
］=
p
。
c
［
i
］［
col
］；
}
else
if
（
p
。
c
［
i
］［
col
］<
result
［
1
］）{
result
［
1
］=
p
。
c
［
i
］［
col
］；
}
}
return
result
；
}
/**
* 規約矩陣
* @param p 點
* @return p對應的費用矩陣的規約值
*/
double
changeMaxtrix
（
point
p
）{
double
sum
=
0
，
temp
；
for
（
int
i
=
0
；
i
<
p
。
k
；
i
++）{
temp
=
row_min
（
p
，
i
）［
0
］；
for
（
int
j
=
0
；
j
<
p
。
k
；
j
++）{
p
。
c
［
i
］［
j
］-=
temp
；
}
sum
+=
temp
；
}
for
（
int
i
=
0
；
i
<
p
。
k
；
i
++）{
temp
=
col_min
（
p
，
i
）［
0
］；
for
（
int
j
=
0
；
j
<
p
。
k
；
j
++）{
p
。
c
［
j
］［
i
］-=
temp
；
}
sum
+=
temp
；
}
return
sum
；
}
/**
* 選擇分支邊
* @param p 點
* @return 返回分支邊
*/
double
［］
edge_sel
（
point
p
）{
int
i
，
j
；
double
temp
，
d
=-
1
；
double
result
［］=
new
double
［
3
］；
double
row_value
［］=
new
double
［
p
。
k
］；
double
col_value
［］=
new
double
［
p
。
k
］；
for
（
i
=
0
；
i
<
p
。
k
；
i
++）{
row_value
［
i
］=
row_min
（
p
，
i
）［
1
］；
}
for
（
i
=
0
；
i
<
p
。
k
；
i
++）{
col_value
［
i
］=
col_min
（
p
，
i
）［
1
］；
}
for
（
i
=
0
；
i
<
p
。
k
；
i
++）{
for
（
j
=
0
；
j
<
p
。
k
；
j
++）{
if
（
p
。
c
［
i
］［
j
］==
0
）
{
temp
=
row_value
［
i
］
+
col_value
［
j
］；
if
（
temp
>
d
）
{
d
=
temp
；
result
［
0
］
=
d
；
result
［
1
］
=
i
；
result
［
2
］
=
j
；
}
}
}
}
return
result
；
}
/**
* 修改費用矩陣，刪除對應行和列
* @param p 點
* @param vk 第vk行
* @param vl 第vl列
* @return 返回修改後的點
*/
point
del_rowcolnew
（
point
p
，
int
vk
，
int
vl
）{
point
result
=
new
point
（
p
。
k
-
1
）；
result
。
k
=
p
。
k
-
1
；
int
i
=
0
；
int
j
=
0
；
int
r
，
c
；
for
（
r
=
0
；
r
<
p
。
k
；
r
++）{
j
=
0
；
if
（
r
==
vk
）{
continue
；}
for
（
c
=
0
；
c
<
p
。
k
；
c
++）{
if
（
c
==
vl
）{
continue
；}
result
。
c
［
i
］［
j
］=
p
。
c
［
r
］［
c
］；
j
++；
}
i
++；
}
i
=
0
；
for
（
r
=
0
；
r
<
p
。
k
；
r
++）{
if
（
r
==
vk
）{
continue
；}
result
。
rowNumber
［
i
］=
p
。
rowNumber
［
r
］；
i
++；
}
i
=
0
；
for
（
r
=
0
；
r
<
p
。
k
；
r
++）{
if
（
r
==
vl
）{
continue
；}
result
。
colNumber
［
i
］=
p
。
colNumber
［
r
］；
i
++；
}
for
（
r
=
0
；
r
<
n
；
r
++）{
result
。
ad
［
r
］=
p
。
ad
［
r
］；
}
return
result
；
}
/**
* 防止成環操作
* @param p
* @param vk
* @param vl
* @return
*/
point
edge_bypnew
（
point
p
，
int
vk
，
int
vl
）{
int
vk1
=
p
。
rowNumber
［
vk
］；
int
vl1
=
p
。
colNumber
［
vl
］；
p
。
ad
［
vk1
］=
vl1
；
if
（
vk
>=
0
&&
vl
>=
0
）{
p
。
c
［
vl
］［
vk
］=
Double
。
MAX_VALUE
；
}
int
e
=
vk1
；
int
s
=
vl1
；
int
c
=
0
；
while
（
c
<
n
）{
for
（
int
i
=
0
；
i
<
n
；
i
++）{
if
（
p
。
ad
［
i
］==
e
）{
e
=
i
；
break
；
}
}
break
；
}
c
=
0
；
while
（
c
<
n
）{
for
（
int
i
=
0
；
i
<
n
；
i
++）{
if
（
i
==
s
&&
p
。
ad
［
i
］>-
1
）{
s
=
p
。
ad
［
i
］；
break
；
}
}
break
；
}
int
d
；
for
（
c
=
0
；
c
<
p
。
rowNumber
。
length
；
c
++）{
for
（
d
=
0
；
d
<
p
。
colNumber
。
length
；
d
++）{
if
（
p
。
rowNumber
［
c
］==
s
&&
p
。
colNumber
［
d
］==
e
）{
p
。
c
［
c
］［
d
］=
Double
。
MAX_VALUE
；
}
}
}
return
p
；
}
/**
* 初始化
* @param c
* @param m
* @return
*/
point
initalnew
（
double
c
［］［］，
int
m
）{
int
i
，
j
；
point
node
=
new
point
（
m
）；
for
（
i
=
0
；
i
<
m
；
i
++）{
for
（
j
=
0
；
j
<
m
；
j
++）{
node
。
c
［
i
］［
j
］=
c
［
i
］［
j
］；
}
}
for
（
i
=
0
；
i
<
m
；
i
++）{
node
。
rowNumber
［
i
］=
i
；
node
。
colNumber
［
i
］=
i
；
}
for
（
i
=
0
；
i
<
m
；
i
++）{
node
。
ad
［
i
］=-
1
；
}
node
。
k
=
m
；
return
node
；
}
}
以28個點的tsp為例，測試結果如下：
