回溯演算法

“不進則退，不喜則憂，不得則亡，此世人之常，”----《鄧析子·無后篇》

前言

回溯法被稱為萬能解法，更內涵退一步海闊天空的人生哲理，

一、回溯和回溯演算法

（1）何為"回溯"？

遺失的美好，你想在重復中找回當時的心動，沿著軌跡回溯，路過的風景卻全都已經不是當年的意味，世界上只剩下兩種人：像她的和不像她的，

(2) 何為"回溯演算法"？

回溯法是一種選優搜索法，按照選優條件深度優先搜索，直至達成目標，當搜索到某一步時，發現原先選擇并不是最優或無法達到目標，就退回一步重新選擇，這種走不通就退回再走的技術稱為回溯法，而滿足回溯條件的某個狀態稱為“回溯點”，

二、實體展現----0-1背包問題

（1）問題簡述

0-1背包問題：提供一個容量（也可以看作是載重量）是W的購物車和n件物品，每個物品 i 對應的價值為Vi，重量為Wi，每個物品只有一件，要么裝入要么不裝入，不可拆分，如何選擇物品，使裝入購物車的價值最高，

(2) 問題分析

從n件物品中選擇一些物品，相當于從n個物品組成的集合S中找到一個子集，該子集的所有物品的總重量不得超過購物車的容量，并且這些物品在滿足條件的情況下總價值最大，

(3) 演算法設計

1. 定義問題的解空間

對于每個物品，都只有兩種結果，裝入和不裝入，但是該物品是否裝入為未知，所以為方便期間，可以定義變數 Xi 來表示第 i 個物品是否裝入，如果裝入則使 Xi 的值為1，否則為0，該問題解的形式是一個n元組，且每個分量的取值為 0 或 1.由此可知，問題的解空間為{ X1 ，X2 ，X3，······ ，Xn },其中Xi為0 或 1，i 為1，2，3，4，······ ，n，

2. 確定解空間的組織結構

不難看出該問題的解是 n 個元素組成的集合所有子集個數，
例如 n 的值為3（即物品共有3個），那么解空間是{ 0， 0，0 } ， { 0 ，0 ，1 }， { 0 ， 1， 1 }， { 1 ，1，1 }， { 0 ，1 ，0 }， { 1 ，0 ，0 }， {1 ，0 ，1 }，{ 1 ，1 ，0 }，
可見問題的解空間樹的深度為問題的規模 n （也就是物品的總數量），

3. 搜索解空間

約束條件：

可容易看出 ∑Wi Xi<=W (下界是i=1，上界是n）

限界條件

根據解空間的組織結構，對于任意一個中間結點z，從根節點到z結點的分支所代表的狀態（是否裝入購物車）已經確定，從z到其子孫結點的分支狀態不確定，也就是說，如果z在解空間樹中處于第t層，說明第一種物品到第t-1 種物品的狀態已經確定，我們只需要沿著z的分支擴展確定第t種物品的狀態即可，為方便起見，我們用 CP 表示已經裝入購物車的物品的總價值，切記，已裝入的價值高并不一定是最優的，因為還有其他情況未確定，
由于我們未確定第t+1種物品到第 n 種物品的實際情況，所以只能估計他們的情況，假設第t+1種物品到第n種物品都裝入購物車，第t+1種物品到第n種物品的總價值用 rp 表示，因此 CP+rp是所有從根出發經過中間結點z的可行解的價值上界，

如果價值上界小于或等于當前搜索到的最優值（最優值用bestp表示，初始值為0），則無繼續搜索的必要，反之，則繼續搜索，
限界條件為： CP+rp>bestp

搜索程序

從根節點開始，深度優先式的搜索，根節點首先成為活結點，也是當前拓展結點，定義左分支為1，即左子樹表示該物品放入購物車，右分支為0，表示不放入購物車，起始沿著左分支進行拓展，往后需要判斷是否滿足限定條件，如果滿足則繼續沿著左分支拓展，否則沿著右分支拓展，如果不滿足則回溯到最近的父親結點繼續拓展其他情況，直到所有情況都被考慮到，

(4) 模擬程序

假設現在有4個物品和一個購物車，每個物品的重量w為（2，5，4，2），價值為（6，3，5，4），購物車重量W是10.
1.初始化

sumw和sumv分別用來統計所有物品的總重量和總價值，sumw=13，sumv=18，sumw>W，因此不能全部裝完，需要擇優選取，當前放入購物車的重量是cw=0，當前放入購物車的價值為cp=0，當前最優值bestp=0.

2.搜索第一層

擴展 1 號結點，首先判斷cw+w[1]=2<W,滿足約束條件，擴展左分支，令X[1]=1,cw=cw+w[1]=2,cp=cp+v[1]=6,生成二號節點，

3.擴展2號結點

首先判斷cw+w[2]=7<W,滿足約束條件，擴展左分支，令x[2]=1,cw=cw+w[2]=7,cp=cp+v[2]=9,生成三號節點，

4. 擴展3號結點

首先判斷cw+w[3]=11>W,超過了購物車容量，第三個物品不能放入，那么判斷bound(t+1)是否大于bestp，bound（4）中剩余物品只有第四個，rp=4,cp+rp=13,bestp=0,因此滿足限界條件，擴展右子樹，令x[3]=0,生成四號結點，

5. 擴展4號結點

首先判斷cw+w[4]=9<W,滿足約束條件，擴展左分支，令x[4]=1,cw=cw+w[4]=9,cp=cp+v[4]=13,生成5號結點，

6. 擴展5號結點

t>n,找到當前一個最優解，用bestx[ ]保存當前最優解{ 1 ，1 ，0， 1 }，保存當前最優值bestp=13，5號結點成為死點，

7. 回溯到4號結點，一直向上回溯到2號結點，

向上回溯到4號結點，回溯時cw=cw-w[4]=7,cp=cp-v[4]=9.如何加上的，如何減去，4號結點右子樹還未生成，考察bound（t+1）是否大于bestp，判斷可知不滿足條件，故不在擴展4號結點的右分支，4號結點為死點，向上繼續回溯至3號結點，3號結點左右孩子都已經考察過，為死點，繼續回溯至2號結點，回溯時cw=cw-w[2]=2,cp=cp-v[2]=6.

8. 擴展2號結點

2號結點右子樹還未生成，考察bound(t+1)是否大于bestp，bound（3）中剩余物品為第3、4個物品，rp=9,cp+rp=15>bestp=13,滿足條件，擴展右子樹，令x[2]=0,生成6號結點，

9. 擴展6號結點

首先判斷cw+w[3]=6<W,滿足約束條件，擴展左分支，令x[3]=1,cw=cw+w[3]=6,cp=cp+v[3]=11,生成7號結點，

10. 擴展7號結點

首先判斷cw+w[4]=8<W,滿足約束條件，擴展左分支，令x[4]=1,cw=cw+w[4]=8,cp=cp+v[4]=15,生成8號結點，

11. 擴展8號結點

t>n,找到一個最優解，用bestx[ ]保存最優解{ 1 ， 0 ，1 ，1 }，保存最優值bestp=10,8號為死點，回溯至7號結點，cw=cw-w[4]=6,cp=cp-v[4]=11.

12. 擴展7號結點

7號右子樹還未生成，考察發現不滿足限界條件，不再擴展，向上回溯至6號結點，cw=cw-w[3]=2,cp=cp-v[3]=6.

13. 擴展6號結點

6號結點右子樹未生成，判斷發現不滿足限界條件，向上回溯至2號結點，cw=cw-w[1]=0,cp=cp-v[1]=0.

14. 擴展1號結點

1號結點右分支未生成，判斷發現不滿足限界條件，演算法結束，

（5） 代碼實作

C++代碼

double Bound(int i) //計算上界
{
    int rp=0; //剩余物品為第i到n種物品，
    while(i<=n) //依次計算剩余物品的價值
    {
    rp+=v[i];
    i++;
    }
    return cp+rp; //回傳上界
}

void Backtrack(int t) //t表示當前擴展結點在第t層
{
    if(t>n)
    {
        for(j=1;j<=n;j++)
        {
            bestx[j]=x[j];
        }
        bestrp=cp;
        return ;
    }
    if(cw+w[t]<=W)
    {
        x[t]=1;
        cw+=w[t];
        cp+=v[t];
        Backtrack(t+1);
        cw-=w[t];
        cp-=v[t];
    }
    if(Bound(t+1)>bestp)
    {
        x[t]=0;
        Backtrack(t+1);
    }
}

Python代碼

def backtrack(i):#global是可以讓函式處理函式外的變數
    global bestV, curW, curV, x, bestx
    if i >= n:
        if bestV < curV:
            bestV = curV
            bestx = x[:]
    else:
        if curW + w[i] <= c:
            x[i] = True
            curW += w[i]
            curV += v[i]
            backtrack(i + 1)
            curW -= w[i]
            curV -= v[i]
        x[i] = False
        backtrack(i + 1)


if __name__ == '__main__':
    n = 5
    c = 10
    w = [2, 2, 6, 5, 4]
    v = [6, 3, 5, 4, 6]
    x = [False for i in range(n)]
    backtrack(0)
    print(bestV)
    print(bestx)

Java代碼：參考自CSDN博主：落雪侵越，文章鏈接：落雪侵越

/**
 * 回溯
 * @param t
 */
public static void BackTrack(int t) {
    if(t>count) {//到達葉結點
        if(cp>bestp) {
            for(int i = 1;i<=count;i++) {
                bestx[i] = cx[i];
            }

            bestp = cp;
        }
        return;
    }

    r -= p[t];
    if(cw + w[t] <= c) {//搜索左子樹
        cx[t] = 1;
        cp += p[t];
        cw += w[t];
        BackTrack(t+1);
        cp -= p[t];//恢復現場
        cw -= w[t];//恢復現場

    }

    if(cp + r >bestp) {//剪枝操作
        cx[t] = 0;//搜索右子樹
        BackTrack(t+1);
    }
    r += p[t];//恢復現場
}

C語言：轉自CSDN博主：永遠的9，文章地址：永遠的9

#include<stdio.h>
#define max 100
 
int weight[max];
int value[max];
int n,max_weight,max_value;
 
int best_answer[max],answer[max];
 
void print()
{
	int i,j,k,l;
	printf("+++++++++++++%d++++++++++++\n",max_value);
	
	for(i=1;i<=n;i++)
		printf("%d ",best_answer[i]);
	printf("\n");
}
 
void DFS(int level,int current_weight,int current_value)
{
	if(level>=n+1)
	{
		if(current_value>max_value)
		{
			int i;
			max_value = current_value;
			for(i=1;i<=n;i++)
				best_answer[i] = answer[i];
		}
	}
	else
	{
		if(current_weight>=weight[level+1])
		{
			current_weight = current_weight - weight[level+1];
			current_value = current_value + value[level+1];
			answer[level+1] = 1;
			DFS(level+1,current_weight,current_value);
			answer[level+1] = 0;
			current_weight = current_weight + weight[level+1];
			current_value = current_value - value[level+1];
		}
		DFS(level+1,current_weight,current_value);
	}
}
 
void init()
{
	int i,j,k,l;
	max_value = 0;
	for(i=1;i<=n;i++)
		answer[i] = 0;
}
 
int main()
{
	int i,j,k,l;
	while(scanf("%d%d",&n,&max_weight)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&weight[i]);
		for(j=1;j<=n;j++)
			scanf("%d",&value[j]);
		
		init();
		
		DFS(0,max_weight,0);
		
		print();
			
		
	}
	return 0;
	
}

總結

回溯演算法本質是一種暴力演算法，畢竟在絕對實力的面前，一切花里胡哨都如螻蟻，本人才疏學淺，出錯在所難免，還望各位不吝賜教，多加指正，鄙人先行謝過，最后，送大家一句話：風可以吹滅蠟燭，卻能使火越燒越旺！

致謝

感謝CSDN博客專家、2020年博客之星TOP5、藍橋杯簽約作者1_bit對本 人Python和演算法學習的建議；
感謝南陽理工學院陳小玉教授的網路遠程指導；
感謝滴滴出行的劉景亮學長對本人C++的指導以及資料結構與演算法的寶貴建議和資源的分享；
感謝致易王俊學長對本人Python演算法實作的除錯、建議與幫助；
感謝知某、某Code、某Time上各網友的建議和資源分享，