回溯法
回溯法的算法框架
1. 綜述
- 從問(wèn)題的 解空間樹(shù) 中，按照 深度優(yōu)先 的策略医增，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。
- 回溯法求所有解時(shí)老虫，最終需要回溯到根叶骨，并且所有節(jié)點(diǎn)的字?jǐn)?shù)都已被搜索遍才結(jié)束。求一個(gè)解時(shí)祈匙，遇到一個(gè)解便可以結(jié)束忽刽。
- 回溯法適用于組合數(shù)較大的問(wèn)題。
2. 解空間
- 解空間應(yīng)該至少包含問(wèn)題的一個(gè)解
- 解空間應(yīng)該很好地組織起來(lái)夺欲，通常組織成樹(shù)或者圖
3. 基本思想
- 活結(jié)點(diǎn)跪帝、擴(kuò)展結(jié)點(diǎn)、死結(jié)點(diǎn)
- 約束函數(shù)剪去不滿足約束條件的子樹(shù)
- 限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)
- 基本步驟
- 針對(duì)所給的問(wèn)題些阅，定義問(wèn)題的解空間伞剑；
- 確定易于搜索的解空間；
- 以深度優(yōu)先方式搜索解空間市埋，并在搜索的過(guò)程中用剪枝函數(shù)避免無(wú)效搜索黎泣。
4. 遞歸回溯
/*
t:遞歸深度
n:最大深度
f(n,t):當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過(guò)的子樹(shù)的起始編碼
g(n,t):當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過(guò)的子樹(shù)的終止編碼
Constraint(t):約束函數(shù)
Bound(t):限界函數(shù)
自頂向下，
對(duì)每個(gè)結(jié)點(diǎn)的分支進(jìn)行遞歸調(diào)用 for(int i=f(n,t);i<=g(n,t);i++)
*/
void Backtrack(int t)
{
if(t > n) Output(x); //是否遞歸結(jié)束
else
{
for(int i=f(n,t);i<=g(n,t);i++) //保證所有子樹(shù)要不被遍歷缤谎，要么被剪枝
{
t=i;
if(Constraint(t)&&Bound(t)) Backtrack(i+1);
}
}
}
5. 迭代回溯
/*
自頂向下抒倚，
對(duì)每個(gè)結(jié)點(diǎn)的分支進(jìn)行迭代 for(int i=f(n,t);i<=g(n,t);i++)
*/
void IterativeBacktrack(void)
{
int t=1;
while(t > 0)
{
if(f(n,t) <= g(n,t))
{
for(int i=f(n,t);i<=g(n,t);i++)
{
t=i;
if(Constraint(t)&&Bound(t))
{
if（Solution(t)) Output(x); //Solution(t)用于判斷問(wèn)題是都得以解決
else t++;
}
else t--;
}
}
}
}
6. 子集樹(shù)
從結(jié)合S中尋找滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹(shù)稱為子集樹(shù)坷澡，如0-1背包問(wèn)題托呕。
子集樹(shù)一般為完全二叉樹(shù)，也就是由“要、不要项郊、要馅扣、不要等”形成。
void Backtrack(int t)
{
if(t > n) Output(x); //是否遞歸結(jié)束
else
{
for(int i=0;i<=1;i++) //保證所有子樹(shù)要不被遍歷呆抑，要么被剪枝
{
t=i;
if(Constraint(t)&&Bound(t)) Backtrack(i+1);
}
}
}
7. 排列樹(shù)
確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)岂嗓，相應(yīng)的解空間樹(shù)稱為排列樹(shù)。排列樹(shù)通常有n!個(gè)葉結(jié)點(diǎn)鹊碍。例如旅行售貨員問(wèn)題厌殉。
void Backtrack(int t)
{
if(t > n) Output(x);
else
{
for(int i=t;i<=n;i++)
{
Swap(x[t],x[i]);
if(Constraint(t)&&Bound(t)) Backtrack(i+1);
Swap(x[i],x[t]);
}
}
}
貨箱裝載
1. 問(wèn)題描述
兩艘船，n個(gè)貨箱侈咕。第一艘載重量c1公罕，第二艘載重量c2。wi是貨箱i的重量耀销，∑wi<=c1+c2楼眷。確定一種方法把n個(gè)貨箱全部裝上船。
∑wi<=c1=c2熊尉，原問(wèn)題等價(jià)于子集之和問(wèn)題罐柳；c1=c2，原問(wèn)題等價(jià)于分割問(wèn)題狰住。這兩個(gè)問(wèn)題都是NP-復(fù)雜問(wèn)題张吉。
解決辦法 ：盡可能將第一艘船轉(zhuǎn)載到它的轉(zhuǎn)載極限，在將剩余的裝載到第二艘催植。
為了將第一艘船盡可能裝滿肮蛹，需要一個(gè)貨箱的子集，使得他們的總重量接近于c1创南。這個(gè)問(wèn)題可以通過(guò)0/1背包問(wèn)題來(lái)解決伦忠。
2. 遞歸回溯算法
屬于上述的子集樹(shù)解決辦法。
/*
貨箱重量weight[1:numberOfContainers]
rLoad(1):返回<=capacity的最大子集之和
*/
void rLoad(int currentLevel)
{
//從currentLevel處的節(jié)點(diǎn)開(kāi)始搜索
if(currentLevel > numberOfContainers)
{
//到達(dá)一個(gè)葉節(jié)點(diǎn)處
if(weightOfCurrentLoading > maxWeightSoFar)
maxWeightSoFar = weightOfCurrentLoading;
return;
}
//還未到達(dá)葉節(jié)點(diǎn)稿辙，檢查子樹(shù)
if(weightOfCurrentLoading + weight[currentLevel] <= capacity)
{
//搜索左子樹(shù)昆码，即x[currentLevel]=1
weightOfCurrentLoading += weight[currentLevel];
rLoad(currentLevel + 1);
weightOfCurrentLoading -= weight[currentLevel];
}
//搜索左子樹(shù)，即x[currentLevel]=0邻储，既然為0那么可以無(wú)需檢查而得以繼續(xù)
rLoad(currentLevel + 1);
}
3. 尋找最優(yōu)子集
增加代碼來(lái)尋找到當(dāng)前的最優(yōu)子集未桥，為此使用一組數(shù)組bestLoadingSoFar,當(dāng)且僅當(dāng)bestLoadingSoFar[i]=1時(shí)，貨箱i屬于最優(yōu)子集芥备。
/*
報(bào)告最有裝載的預(yù)處理程序
*/
int maxLoading(int *theWeight, int theNumberOfContainers, int theCapacity, int *bestLoading)
{
/*
數(shù)組theWeight[1:theNumberOfContainers]是貨箱重量
theCapacity是船的載貨量
數(shù)組bestLoading[1:theNumberOfContainers]是解
返回最大載重量
*/
//初始化全局變量
numberOfContainers = theNumberOfContainers;
weight =theWeight;
capacity = theCapacity;
weightOfCurrentLoading = 0;
maxWeightSoFar = 0;
currentLoading = new int [numberOfContainers+1];
bestLoadingSoFar = bestLoading;
//remainingWeight的初始值是所有貨箱重量之和
for(int i=1;i<=numberOfContainers;i++)
{
remainingWeight += weight[i];
}
//計(jì)算最優(yōu)裝載的重量
rLoad(1);
return maxWeightSoFar;
}
/*
報(bào)告最優(yōu)裝載的回溯算法
*/
void rLoad(int currentLevel)
{
//從currentLevel處開(kāi)始搜索
if(currentLevel > numberOfContainers)
{
//到達(dá)了一個(gè)葉節(jié)點(diǎn)冬耿，存儲(chǔ)一個(gè)更優(yōu)解
for(int j=1; j <= numberOfContainers; j++)
bestLoadingSoFar[j] = currentLoading[j];
maxWeightSoFar = weightOfCurrentLoading;
return;
}
//沒(méi)有到達(dá)一個(gè)葉節(jié)點(diǎn)，檢查子樹(shù)
remainingWeight -= weight[currentLevel];
if(weightOfCurrentLoading + weight[currentLevel] <= capacity)
{
//搜索左子樹(shù)
currentLoading[currentLevel] = 1;
weightOfCurrentLoading += weight[currentLevel];
rLoad(currentLevel + 1);
weightOfCurrentLoading -= weight[currentLevel];
}
if(weightOfCurrentLoading + remainingWeight > maxWeightSoFar)
{
//搜索右子樹(shù)
rLoad(currentLevel + 1);
}
remainingWeight += weight[currentLevel];
}
