第1章
回溯法

1.1 一般原理

可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组(x₁，x₂，…，x_n)组成的一个状态空间E={(x₁，x₂，…，x_n)∣x_i∈S_i ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中S_i是分量x_i的定义域，且 |S_i| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组(x₁，x₂，…，x_i)满足D中仅涉及到x₁，x₂，…，x_i的所有约束意味着j(j<=i)元组(x₁，x₂，…，x_j)一定也满足D中仅涉及到x₁，x₂，…，x_j的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x₁，x₂，…，x_j）违反D中仅涉及到x₁，x₂，…，x_j的约束之一，则以（x₁，x₂，…，x_j）为前缀的任何n元组（x₁，x₂，…，x_j，x_j+1，…，x_n）一定也违反D中仅涉及到x₁，x₂，…，x_i的一个约束，n≥i≥j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x₁，x₂，…，x_j）违反D中仅涉及x₁，x₂，…，x_j的一个约束，就可以肯定，以（x₁，x₂，…，x_j）为前缀的任何n元组（x₁，x₂，…，x_j，x_j+1，…，x_n）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：

设S_i中的元素可排成x_i(1) ，x_i(2) ，…，x_i(m_i-1) ，|S_i|
=m_i，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有m_i个儿子。这m_i个儿子到它们的双亲的边，按从左到右的次序，分别带权x_i+1(1) ，x_i+1(2) ，…，x_i+1(m_i) ，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x₁，x₂，…，x_n）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x₁，x₂，…，x_n，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组（x₁，x₂，…，x_n）的一个前缀I元组（x₁，x₂，…，x_i）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x₁，x₂，…，x_i，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。

因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x₁，x₂，…，x_n满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x_1i）、前缀2元组（x₁，x₂）、…，前缀I元组（x₁，x₂，…，x_i），…，直到i=n为止。

在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。

用回溯法解题的一般步骤：

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

1.2 n元全排列

1.2.1 问题
 

如果p₁，p₂，…，p_n中的元素取自1，2，…，n，且互不相同，则称之为1，2，…，n的一个全排列。全排列问题就是要求输出所有的全排列。其搜索树为

 

图1-1全排列搜索树

1.2.2 算法设计

setp1 k=1，p₁=p₂=…p_n=1；

setp2 求p_k，从p_k当前的值往前寻求p_k的值，要求p_k与p₁，…，p_k-1不相同，且不超过n；如果找不到，到step4；

step3 如果k=n，打印全排列，p_k=p_k+1，回到step2；

step4 回溯，重新设置当前分量p_k=1，然后回到上一分量k=k-1；

step5 如果k<1，终止算法；

step6 回到step2。

图1-2 全排列回溯法流程图

1.2.3
C++代码

由于C++代码中的数组索引是从0开始的，所以，下面代码中k的值就是从0开始，求出的是0，1，…，n-1的全排列，在打印部分每个分量加1就得到了1，2，…，n的全排列。

void Backtracking(int n){

int *p=new int[n];

memset(p,0,n*sizeof(int));

    int k = 0;

    while (k >= 0) {

        //找一个合适的值给当前状态

        while (p[k] < n){

            int i;

            for (i = 0; i < k; i++)

                if (p[i] == p[k])

                    break;

            if (i < k)   p[k]++;

            else       break;

        }

        //找到了

        if (p[k]<n) {

            if (k < n-1) k++;//如果没有找到全部解就前进

            else//找到了一个解

            {

                int i;

                for(i=0;i<=k;i++)

                    cout<<p[i]+1<<" ";

                cout<<endl;

                p[k]++;//探索下一个解

            }

        }

        else//没找到需要回溯

        {

            p[k] = 0;//清除当前处理的信息

            k--;//回溯

            if(k>=0)

                p[k]++;//探索下一个解

        }

    }

}

注：这个算法很容易就修改成输出n个元素中选出m（m<n）个元素进行排列，只需要将判断k<n-1变成k<m-1，余皆不变。

1.3 正整数的拆分

1.3.1 问题

对于给定的正整数n，将其表述成若干个正整数的和，不计先后次序。例如

5=1+1+1+1+1

 =1+1+1+2

 =1+1+3

     =1+2+2

 =1+4

 =2+3

 =5

1.3.2 算法设计

假定我们将n拆分成n=p₁+p₂+…+p_n，并要求p₁≤p₂≤…≤p_l，p_l+1=…=p_n=0，如5=1+2+2+0+0。基本思想：开始时k=1，p_k=1，从p_k往前，因为要求p_k+1≥p_k，所以把余额部分分成等于p_k的若干份，赋给后面的p_j，不够p_k的余额就直接给最后一个分量。一旦得到一个解，就进行回溯，也就是令最后一个分量为0，次后的分量增加1个，然后继续。算法步骤如下：

step1 置p₁=p₂=…=p_n=1，k=n;

step2 打印p₁，p₂，…，p_k，num=p_k，p_k=0；

step3 如果 k<=1 终止；

step4  p_k-1=p_k-1+1，num=num-1，k=k-1；

step5  t=num/p_k取整，p_k+1=p_k+2=…=p_k+t-1=p_k，p_k+t=p_k+num
mod p_k， k=k+t，回到step2。

                      

图1-3 整数拆算法分流程图

1.3.3
C++代码

void SplitInteger(int n){

int*p=new int[n];//分量

int rem,k=n-1,i;//剩余、回溯变量、循环变量

for(i=0;i<n;i++)p[i]=1;

while(1){

cout<<n<<"="<<p[0];

for(i=1;i<=k;i++)

cout<<"+"<<p[i];

cout<<endl;

rem=p[k],p[k]=0;

if(k==0)

break;

k--,p[k]++,rem--;

int
t=rem/p[k];

for(i=0;i<t;i++)

p[k+i+1]=p[k];

k+=t;

p[k]+=rem
% p[k-t];

}

delete []p;

}

1.4 八皇后问题

1.4.1 问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8´8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

1.4.2 算法设计

我们考虑一般的N皇后问题，也就是在N´N格的国际象棋上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。要求输出所有摆设方案。首先我们可以用p_k记录第k列的皇后放在了第p_k行，这样，每一种方案就对应1，2，…，n的一个全排列p₁p₂…p_n。参考图1-4，是8皇后的一个摆设方案，其对应的全排列是15863724。不难看出，两个棋子摆放在同捺('\')斜线（我们称其为右斜线）上的充要条件是p_k-k=p_l-l，而两个旗子摆放在同撇（'/'）斜线（我们称其为左斜线）上的充要条件是p_k+k=p_l+l。从而，N皇后的摆放算法与全排列的回溯算法基本相同，只是需要添加两个判断，从而保证两颗棋子处于不同的斜线：

 

图1-4八皇后的一种摆放

    setp1 k=1，p₁=p₂=…p_n=1；

setp2 求p_k，从p_k当前的值往前寻求p_k的值，要求

1、p_k与p₁，…，p_k-1不相同；

2、p_k-k与p₁-1，…，p_k-1-(k-1)不同；

3、p_k+k与p₁+1，…，p_k-1+(k-1)不同；

4、且不超过n；

如果找不到，到step4；

step3 如果k=n，打印全排列，p_k=p_k+1，回到step2；

step4 回溯，重新设置当前分量p_k=1，然后回到上一分量k=k-1；

step5 如果k<1，终止算法；

step6 回到step2。

图1-5 N皇后算法流程

1.4.3 代码

由于多次判断同行或者同斜线问题，势必要对前面的摆放进行遍历，这样会增加运行成本，为了在O(1)的时间内进行判断，我们需要三个bool类型的数组rows、racross以及lacross，分别记下已经摆放了棋子的行、左斜线以及右斜线。显然，行数是N，而两个斜线的数目则是2*N-1。注意C++中数组索引从0开始，所以我们求的全排列也是0，1，…，N-1的全排列。这样p_k的值对应于p_k行放置了棋子，放置之后就可以置rows[p_k]=true，以后的各列在放置棋子时就可以利用此数组的值确定能否摆放。对于左斜线（/），对应地就是lacross[p_k+k]=true，对于右斜线（\）则要使当调整p_k-k的值，以适应数组下标非负的要求，我们采取的方法是置racross[n+p_k-k-1]=true。代码如下：

#include <iostream>

using namespace std;

#define N 50

int n,p[N];

bool rows[N],lacross[2*N-1],racross[2*N-1];

bool Place(int k){

bool b=rows[p[k]];

b=b || racross[n+p[k]-k-1];

b=b || lacross[p[k]+k];

return b;

}

void Set(int k){

rows[p[k]]=true;

racross[n+p[k]-k-1]=true;

lacross[p[k]+k]=true;

}

void DeSet(int k){

rows[p[k]]=false;

racross[n+p[k]-k-1]=false;

lacross[p[k]+k]=false;

}

void BackTrackQueen(int n){

int k=0;

while(k>=0){

while(p[k]<n
&& Place(k))

p[k]++;

if(p[k]<n){

Set(k);

if(k<n-1)k++;

else{

for(int
i=0;i<n;i++)

cout<<p[i]+1<<"
";

cout<<endl;

DeSet(k);

p[k]++;

}

}else{

p[k]=0;

k--;

DeSet(k);

if(k>=0)p[k]++;

}

}

}

int main(){

BackTrackQueen(8);

return 0;

}

1.5 数独

1.5.1 问题

数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

  

(a)原题
             (b)解答

图1-6 数独

1.5.2 算法设计

有了计算机之后，数独问题的解完全可以利用计算机程序完成。回溯算法的基本步骤是：

step1 将数独问题的原始数据存放到一个二维数组a中，没有数据的地方置0；

step2 根据a中的数据构造三个集合：行集合rows，列集合cols以及块集合square分别存储每行、每列以及每块已经存放的数字；

step3 置i，j为0;

step4 如果i，j处原有数字，到step8；

step5 如果a[i][j]不在rows[i]中，且不在cols[j]中，且不在对应的块中，则到step7；

step6  a[i][j]= a[i][j]+1，到step5；

step7 如果a[i][j]>9 ，a[i][j]=0，到step12；

step8 如果j<8，j=j+1到step4；

step9 如果i<8，i=i+1，j=0，到step4；

step10 打印解；

step11 i，j处原无数字，到step15；

step12 如果j>0，j=j-1，到step11；

step13 如果i>=0，i=i-1，j=8，到step11；

step14 终止；

step15 清除rows[i]和cols[j]以及对应的块中的a[i][j]，a[i][j]=
a[i][j]+1，到step5。

 

图1-7 数独算法流程图

1.5.3代码

在代码实现中，我们用了STL提供集合（set）定义了三组数组，分别收集行、列与块中已经填充了的数据，另一方面为了标记哪些位置已经放置有数字，我们提供了一个bool二维数组。在计算每个位置属于哪一块时使用的是公式k=[i/3]*3+[j/3]。

#include <iostream>

#include <set>

using namespace std;

void print(int a[][9]){

int i,j;

for(i=0;i<9;i++){

for(j=0;j<9;j++)

cout<<a[i][j]<<"
";

cout<<endl;

}

}

void Sudoku(int a[][9]){

int i,j,k=0;

//记录每行、每列、每个方块中已有的数字

set<int> rows[9],cols[9],square[9];

//记录那些元素是固定的

bool fixed[9][9]={false};

//初始化几个集合

for(i=0;i<9;i++){

for(j=0;j<9;j++){

rows[i].insert(a[i][j]);

cols[j].insert(a[i][j]);

square[i/3*3+j/3].insert(a[i][j]);

fixed[i][j]=
a[i][j]>0;

}

}

//开始回溯算法

i=0,j=0;

while(i>=0 && j>=0){

k=i/3*3+j/3;//计算当前是哪一块

if(fixed[i][j]==false)//寻找当前位置的可放数字

{

while(rows[i].find(a[i][j])!=rows[i].end()
|| cols[j].find(a[i][j])!=cols[j].end() || square[k].find(a[i][j])!=square[k].end())

a[i][j]++;

}

if(a[i][j]<=9)//当前位置的可放数字找到了之后

{

rows[i].insert(a[i][j]);//放入对应行

cols[j].insert(a[i][j]);//放入对应列

square[k].insert(a[i][j]);//放入对应快

if(i==8
&& j==8)//全部位置处理完后

{

print(a);//打印

//清除最后一个元素，以便回溯查找下一个解

while(i>=0
&& j>=0 && fixed[i][j]){

if(j>0)j--;

else
i--,j=8;

}

rows[i].erase(a[i][j]);

cols[j].erase(a[i][j]);

square[i/3*3+j/3].erase(a[i][j]);

//查找下一个解

a[i][j]++;

}

else//还有位置没处理，需要前进

{

if(j<8)j++;//行没处理完

else

i++,j=0;//当前行处|理完后，处理下一行

}

}else//当前位置的可放数字找不到，需要回溯

{

if(fixed[i][j]==false)

a[i][j]=0;//如果不是固定元素，就清除

//回溯

if(j>0)j--;

else
i--,j=8;

//略过固定元素

while(i>=0
&& j>=0 && fixed[i][j]){

if(j>0)j--;

else
i--,j=8;

}

if(i>=0
&& j>=0){

//清除当前元素

rows[i].erase(a[i][j]);

cols[j].erase(a[i][j]);

square[i/3*3+j/3].erase(a[i][j]);

//找下一个解

a[i][j]++;

}

}

}

}

int main(){

int a[9][9]={

0,6,0,5,9,3,0,0,0,

9,0,1,0,0,0,5,0,0,

0,3,0,4,0,0,0,9,0,

1,0,8,0,2,0,0,0,4,

4,0,0,3,0,9,0,0,1,

2,0,0,0,1,0,6,0,9,

0,8,0,0,0,6,0,2,0,

0,0,4,0,0,0,8,0,7,

0,0,0,7,8,5,0,1,0

};

Sudoku(a);

return 0;

}

1.5.4 数独问题的变形。

2012年第三节蓝桥杯决赛第5题

【编程题】(满分33分)

    “数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”，是大数学家欧拉于1783年发明的。

    如图1-8所示：6x6的小格被分为6个部分（图中用不同的颜色区分）,每个部分含有6个小格（以下也称为分组）。

 

图1-8 蓝桥杯决赛第5题图

    开始的时候，某些小格中已经填写了字母（ABCDEF之一）。需要在所有剩下的小格中补填字母。

    全部填好后，必须满足如下约束：

    1. 所填字母只允许是A,B,C,D,E,F 中的某一个。

    2. 每行的6个小格中，所填写的字母不能重复。

    3. 每列的6个小格中，所填写的字母不能重复。

    4. 每个分组（参见图中不同颜色表示）包含的6个小格中，所填写的字母不能重复。

    为了表示上的方便，我们用下面的6阶方阵来表示图[1.jpg]对应的分组情况（组号为0~5）：

000011

022013

221113

243333

244455

445555

     用下面的数据表示其已有字母的填写情况：

02C

03B

05A

20D

35E

53F

    很明显，第一列表示行号，第二列表示列号，第三列表示填写的字母。行号、列号都从0开始计算。

    一种可行的填写方案（此题刚好答案唯一）为：

E F C B D A

A C E D F B

D A B E C F

F B D C A E

B D F A E C

C E A F B D

    你的任务是：编写程序，对一般的拉丁方块问题求解，如果多解，要求找到所有解。

【输入、输出格式要求】

用户首先输入6行数据，表示拉丁方块的分组情况；接着用户输入一个整数n
(n<36), 表示接下来的数据行数；接着输入n行数据，每行表示一个预先填写的字母。

程序则输出所有可能的解（各个解间的顺序不重要）。每个解占用7行。即，先输出一个整数，表示该解的序号（从1开始），接着输出一个6x6的字母方阵，表示该解。解的字母之间用空格分开。

    如果找不到任何满足条件的解，则输出“无解”

    例如：用户输入：

000011

022013

221113

243333

244455

445555

6

02C

03B

05A

20D

35E

53F

 

    则程序输出：

1

E F C B D A

A C E D F B

D A B E C F

F B D C A E

B D F A E C

C E A F B D

 

   再如，用户输入：

001111

002113

022243

022443

544433

555553

7

04B

05A

13D

14C

24E

50C

51A

    则程序输出：

1

D C E F B A

E F A D C B

A B F C E D

B E D A F C

F D C B A E

C A B E D F

2

D C E F B A

E F A D C B

A D F B E C

B E C A F D

F B D C A E

C A B E D F

3

D C F E B A

A E B D C F

F D A C E B

B F E A D C

E B C F A D

C A D B F E

4

D C F E B A

B E A D C F

A D C F E B

F B E A D C

E F B C A D

C A D B F E

5

D C F E B A

E F A D C B

A B C F E D

B E D A F C

F D B C A E

C A E B D F

6

D C F E B A

E F A D C B

A B D F E C

B E C A F D

F D B C A E

C A E B D F

7

D C F E B A

E F A D C B

A D B F E C

B E C A F D

F B D C A E

C A E B D F

8

D C F E B A

F E A D C B

A D B C E F

B F E A D C

E B C F A D

C A D B F E

9

D C F E B A

F E A D C B

A F C B E D

B D E A F C

E B D C A F

C A B F D E

此题的解答与数独问题几乎一样，不同的秩序将数独代码中的9变成6，8变成5，然后变更的关键代码是对square的处理，只需用"square[sq[i][j]] "替换"square[i/3*3+j/3]" ，这里二维数组sq中存放分块数据。参考代码如下

 

#include <iostream>

#include <set>

using namespace std;

set<char> rows[6],cols[6],square[6];

char a[6][6]={0};

char sq[6][7]={"000011","022013","221113","243333","244455","445555"};

void print(){

int i,j;

for(i=0;i<6;i++){

for(j=0;j<6;j++)

cout<<char(a[i][j]+'A'-1)<<"
";

cout<<endl;

}

}

bool canNotPlace(int i,int j)

{

bool b=rows[i].find(a[i][j])!=rows[i].end();

b=b || cols[j].find(a[i][j])!=cols[j].end() ;

b=b || square[sq[i][j]-'0'].find(a[i][j])!=square[sq[i][j]-'0'].end();

return b;

}

void FillLating(){

int i,j,k=0;

//记录每行、每列、每个方块中已有的数字

//记录那些元素是固定的

bool fixed[6][6]={false};

//初始化几个集合

for(i=0;i<6;i++){

for(j=0;j<6;j++){

rows[i].insert(a[i][j]);

cols[j].insert(a[i][j]);

square[sq[i][j]-'0'].insert(a[i][j]);

fixed[i][j]=
a[i][j]>0;

}

}

//开始回溯算法

i=0,j=0;

while(i>=0 && j>=0){

if(fixed[i][j]==false)//寻找当前位置的可放数字

{

while(canNotPlace(i,j))

a[i][j]++;

}

if(a[i][j]<=6)//当前位置的可放数字找到了之后

{

rows[i].insert(a[i][j]);//放入对应行

cols[j].insert(a[i][j]);//放入对应列

square[sq[i][j]-'0'].insert(a[i][j]);//放入对应块

if(i==5
&& j==5)//全部位置处理完后

{

print();//打印

//清除最后一个元素，以便回溯查找下一个解

while(i>=0
&& j>=0 && fixed[i][j]){

if(j>0)j--;

else
i--,j=5;

}

rows[i].erase(a[i][j]);

cols[j].erase(a[i][j]);

square[sq[i][j]-'0'].erase(a[i][j]);

//查找下一个解

a[i][j]++;

}

else//还有位置没处理，需要前进

{

if(j<5)j++;//行没处理完

else

i++,j=0;//当前行处|理完后，处理下一行

}

}else//当前位置的可放数字找不到，需要回溯

{

if(fixed[i][j]==false)

a[i][j]=0;//如果不是固定元素，就清除

//回溯

if(j>0)j--;

else
i--,j=5;

//略过固定元素

while(i>=0
&& j>=0 && fixed[i][j]){

if(j>0)j--;

else
i--,j=5;

}

if(i>=0
&& j>=0){

//清除当前元素

rows[i].erase(a[i][j]);

cols[j].erase(a[i][j]);

square[sq[i][j]-'0'].erase(a[i][j]);

//找下一个解

a[i][j]++;

}

}

}

}

int main(){

int i,j;

a[0][2]=3;a[0][3]=2;a[0][5]=1;a[2][0]=4;a[3][5]=5;a[5][3]=6;

FillLating();

return 0;

}

1.6 0-1背包

1.6.1 问题

背包问题(Knapsack
problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

我们有n种物品，物品j的重量为w_j，价格为p_j。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为

1.6.2 算法设计

很多0-1背包问题的回溯算法都是先对物品依据其价值从达到小进行排序，我们则依据物品的重量从小到的进行排序，由此设计的算法在一定程度上提高了效率。其算法步骤如下：

step1 根据物体重量由小到大进行排序，设为

step2 置x'₁=x'₂=…=x'_n=0，tmpv=0，value=0，rem=M，i=1；

step3 如果i≤n且rem≥w_i到step4，否则到step5；

step4 x'_i=1，tmpv=tmpv+v_i，rem=rem-w_i，i=i+1回到step3；

step5 如果tmpv>value，则value=tmpv，x₁=x'₁，…，x_n=x'_n；

step6 如果i=n+1，置i=n；

step7 如果i>0 且 x'_i=0 到step8，否则，到step9；

step8 i=i-1，到step7；

step9 如果i=0终止，否则，x'_i=0，tmpv=tmpv-v_i ，rem=rem+w_i，i=i+1，回到step3。

这个算法可以求得问题的精确解。下面我们给出此算法的分析。

引理1 在算法的迭代中必定会出现状态x'₁=1，x'₂=…=x'_n=0之后进入step7。

证明。根据算法迭代规律，第一次进入step5的状态一定是x'₁=…= x'_k=1，x'_k+1=…=x'_n=0，其中k是某个0（w₁>W时）到n（所有物体之和≤W时）之间的整数。我们对k用数学归纳法：k=1是结论成立，假定在k时结论成立。对于k+1，记

则在此算法的迭代过程中状态的变化过程一定是

x'₁=…= x'_k+1=1，x'_k+2=…=x'_n=0

à x'₁=…= x'_k=1，x'_k+1=0，x'_k+2=1，x'_k+3=…=x'_n=0

à…à x'₁=…= x'_k=1，x'_k+1=…x'_l-1=0，x'_l=1，x'_l+1=…=x'_n=0

à x'₁=…= x'_k=1，x'_k+1=…=x'_n=0

 

图1-9 0-1背包问题算法流程图

并会在这个状态下进入step5，由归纳假定，引理1结论正确。

结论1 时间复杂度分析：，k=，则迭代次数大约为

如果假定每个物品的重量就是w，则不难看出，算法是在元素个数不超过k的子集上再遍历，从而可知迭代次数就是。

结论2 算法可以得到问题的精确解。

对n用数学归纳法。

对于n=1时显然是正确的；

假定对于n时算法正确；

对于n+1，分析算法迭代不难发现，开始时x'₁=1，以后在进入状态x'₁=1，x'₂=…=x'_n+1=0之前的迭代就相当于对后面的x'₂，…，x'_n+1以及背包容量为W-w₁进行求解，而进入状态x'₁=1，x'₂=…=x'_n+1=0之后，经由step7，step8，step9回到step3相当于对后面的x'₂，…，x'_n+1以及背包容量为M进行求解，由归纳假定知算法正确。

1.6.3 代码

#include <iostream>

#include <ctime>

#include <iomanip>

using namespace std;

 

double backpack_0_1( double w[],double v[],double pack_w,int n,int*x)

{

int i,j;

//用于记录原始索引

int *index=new int[n];

//临时解

int *x1=new int[n];

//复制数据

double *w1=new double[n];

double *v1=new double[n];

for(i=0;i<n;i++)

x1[i]=0,w1[i]=w[i],v1[i]=v[i],index[i]=i;

double value=0,tmpv;//value为最大价值，tmpv为当前解得价值

//依据重量的大小从小到大排序，v1与index随之变动

for(i=0;i<n;i++){

for(j=i+1;j<n;j++)

if(w1[i]>w1[j])

swap(w1[i],w1[j]),swap(v1[i],v1[j]),swap(index[i],index[j]);

}

double rem=pack_w;

i=0;tmpv=0;

while(i>=0)//回溯法开始

{

while(i<n
&& rem>=w1[i])//前进

{

x1[i]=1;rem-=w1[i];

tmpv+=v1[i];

i++;

}

if(tmpv>value)

{

value=tmpv;

for(j=0;j<n;j++)

x[index[j]]=x1[j];

}

while(i>=n
|| (i>=0 && x1[i]==0))//回溯

i--;

if(i<0)break;

x1[i]=0,tmpv-=v1[i],rem+=w1[i];

i++;

}

delete[]x1;delete[]index;delete[]w1;delete[]v1;

return value;

}

int main(){

int n=10;

double M=100;

double *w=new double[n],*v=new double[n];

int i;

srand((unsigned int)time(0));

for(i=0;i<n;i++){

w[i]=rand()%100;

v[i]=rand()%100+10;

}

int *x=new int[n];

cout<<backpack_0_1(w,v,M,n,x)<<endl;

for(i=0;i<n;i++)

cout<<setw(4)<<w[i];

cout<<endl;

for(i=0;i<n;i++)

cout<<setw(4)<<v[i];

cout<<endl;

for(i=0;i<n;i++)

cout<<setw(4)<<x[i];

cout<<endl;

double value=0;

for(i=0;i<n;i++)

value+=x[i]*w[i];

cout<<"装入物体重量上界:"<<M<<endl;

cout<<"装入物体总重量:"<<value<<endl;

value=0;

for(i=0;i<n;i++)

value+=x[i]*v[i];

cout<<"装入物体总价值:"<<value<<endl;

value=0;

for(i=0;i<n;i++)

value+=w[i];

cout<<M/value*100<<"%"<<endl;

delete[]x;

delete[]w;

delete[]v;

return 0;

}

 

1.7 迷宫

1.7.1 问题

求迷宫（参见图1-9）中从入口到出口的所有路径非常适合利用回溯法。从入口出发，顺某一方向向前探索，若能通过，则继续往前走，否则沿原路返回，换一个方向继续探索，直到所有可能的通路都探索到为止。

         

             图1-10 迷宫图
           1-11 查找方向示意图
 

1.7.2 算法设计

把路径当成是由点构成的序列，path=(p₁，p₂，…，p_n)，这样就可以为此问题设计回溯法。假定找到了部分路径(p₁，p₂，…，p_j)，则从p_j往前找就是探寻p_j的下方点，如果成功就将其加入路径，否则依次探寻p_j的右方点、上方点、左方点等，参见图1-10。同时记下当前点已查询的方向。如果四个方向都不能通过，则将p_j丢弃，并从p_j-1的下一个方向开始探寻。一个点不能作为路径的原因只有两个：不是通路，或者已经在路经中（因为我们规定只查找简单路径，不需要回路）。其算法步骤如下：

step1 start点进路径path；

step2 如果path的最后一个点等于end，打印路径，到step5；

step3 如果path端点的方向大于3，到step5，否则根据path的端点的方向寻求下一个点next；

step4 如果next是通路且不在path中，将next加到path的尾端，回到step2；否则，把path的端点的方向加1回到step3；

step5 删除path的最后一个点，如果path为空，终止算法步骤；否则，把path的端点的方向加1，回到step3。

次算法可以找到所有简单路径。其算法流程图见图1-11。

1.7.3 代码

因为迷宫的路径是由点构成的，所以我们首先定义了一个Point结构体，其中包含有点的位置，以及为了回溯而记下的寻求过了的方向（参见图1-10）。

 

图1-12 迷宫回溯算法流程图

#include <iostream>

#include <vector>

using namespace std;

struct Point{

int x,y;

int direction;

};

Point start={1, 1};

Point end ={8, 8};

bool walls[10][10] ={

{false,false,false,false,false,false,false,false,false,false},

    {false,true,true,false,true,true,true,false,true,false},

    {false,true,true,false,true,true,true,false,true,false},

    {false,true,true,true,true,false,false,true,true,false},

    {false,true,false,false,false,true,true,true,true,false},

    {false,true,true,true,false,true,true,true,true,false},

    {false,true,false,true,true,true,false,true,true,false},

    {false,true,false,false,false,true,false,false,true,false},

    {false,false,true,true,true,true,true,true,true,false},

    {false,false,false,false,false,false,false,false,false,false}

};

void Findpath();

Point NextPoint(Point curr);

bool Pace(vector<Point> path, Point p);

 

int main(){

Findpath();

return 0;

}

void Findpath()

{

    Point next;

    vector<Point> path;

    path.push_back(start);

    int num = 1;

    while (path.size()>0)

    {

        num = path.size();

        next = NextPoint(path[num-1]);

        while (path[num-1].direction < 4 && Pace(path,next))

        {

            path[num-1].direction++;

            next = NextPoint(path[num-1]);

        }

        if (path[num-1].direction< 4)

        {

            path. push_back(next);

num++;

            if (path[num-1].x==end.x && path[num-1].y==end.y)

            {

                for(int i=0;i<path.size();i++)

cout<<"("<<path[i].x<<","<<path[i].y<<")";

system("pause");

                path.erase(path.end()-1);

                if (path.size() > 0)

path[path.size()
- 1].direction++;

            }

        }

        else

        {

            path.erase(path.end() - 1);

num--;

            if (path.size() > 0)

path[path.size()
- 1].direction++;

        }

    }

}

Point NextPoint(Point curr)

{

Point p={-1,-1};

switch (curr.direction)

    {

        case 0:

            p.x=curr.x + 1;p.y=curr.y;

break;

        case 1:

            p.x=curr.x;p.y=curr.y + 1;

break;

        case 2:

            p.x=curr.x - 1;p.y=curr.y;

break;

        case 3:

            p.x=curr.x; p.y=curr.y - 1;

break;

    }

    return  p;

}

bool Pace(vector<Point> path, Point p)

{

    if (!walls[p.x][p.y])

        return true;

    for(int i=path.size()-1;i>=0;i--)

if((path[i].x==p.x)
&& (path[i].y==p.y))

            return true;

    return false;

}

1.8 旅行商（TSP）

1.8.1 问题

设有n个城市，v₁，v₂，…，v_n，第i个城市v_i到第j个城市v_j的旅行费用为c_ij。现有一人，从v₁出发，把所有城市旅游一次然后回到v₁，要设计一条路径，使得总旅行费用最小。

1.8.2 算法设计

假定路径为v₁àv_j2à…àv_jnàv₁，则显然有，v_j2，…，v_jn是v₂，…，v_n的一个全排列，所以旅行商问题也是一个全排列，全排列的算法可以照搬。但是，由于我们的最终目的是要找一条费用最小的路径，因此当要扩展结点时，可以利用当前费用对搜索树进行剪枝，从而达到提高计算速度的目的。

setp1 p₁=p₂=…=p_n=1，k=2，tmpc=0，cost=INF；

setp2 求p_k，从p_k当前的值往前寻求p_k的值，要求p_k与p₁，…，p_k-1不相同；如果找不到，到step6；

step3 tmpc=tmpc+，如果tmpc>cost，tmpc=tmpc-，到step2；

step4如果k=n，tmpc=tmpc+，如果tmpc<cost，则cost=tmpc，记下当前的路径。tmpc=tmpc--回到step2；

step5 k=k+1，到step2；

step6 p_k=2，k=k-1；

step7 如果k<1，终止算法；

step8 回到step2。

 

图1-13 TSP问题回溯法流程图

1.8.3 代码

以n=5为例，下面给出了算法代码。当

c=

时，此算法只需要处理7条完整的路径，由此可见有很多（约17条）路径被剪除了。

double Backtracking(double c[][5],int n){

int *p=new int[n];

memset(p,0,n*sizeof(int));

double tmpc=0,cost=9999;

    int k = 1;

    while (k >= 1) {

        //找一个合适的值给当前状态

        while (p[k] < n){

            int i;

            for (i = 0; i < k; i++)

                if (p[i] == p[k])

                    break;

            if (i < k)   p[k]++;

            else       break;

        }

        //找到了

        if (p[k]<n) {

tmpc+=c[p[k-1]][p[k]];

if(tmpc<cost)//当前费用小于总费用时才需要继续往前寻找

{

if
(k < n-1) k++;//如果没有找到全部解就前进

else//找到了一个解

{

int
i;

tmpc+=c[p[k]][0];

cout<<tmpc<<":";

 if(tmpc<cost)

cost=tmpc;

   for(i=0;i<n;i++)

cout<<p[i]+1<<"
";

cout<<endl;

tmpc-=c[p[k-1]][p[k]]+c[p[k]][0];

p[k]++;//探索下一个解

}

}else//否则状态不前进，继续找下一个

{

tmpc-=c[p[k-1]][p[k]];

p[k]++;

}

        }

        else//没找到需要回溯

        {

            p[k] = 0;//清除当前处理的信息

            k--;//回溯

            if(k>=1){

tmpc-=c[p[k-1]][p[k]];

                p[k]++;//探索下一个解

}

        }

    }

return cost;

}

1.9 图的n着色问题

1.9.1 问题

图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。

如果一个图的所有顶点和边都能采用某种方法华在平面上且没有任何两条边相交，则称这个图是可平面图。著名的平面图的4色猜想是图的m可着色性判定问题的一个特例。

四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯•格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”。他和在大学读书的弟弟格里斯都没能证明这一结论。1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德•摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密顿爵士请教。哈密顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密顿逝世为止，问题也没有能够解决。

1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普(Alfred
Kempe)和泰勒(Peter Guthrie Tait)两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。但是后来人们发现他们错了，但是他们的思考方式却得到了肯定。

电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。美国伊利诺大学哈肯在1970年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。就在1976年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。

这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。

“四色问题”的被证明仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。

不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍有不少数学家和数学爱好者在寻找更简洁的证明方法。

不难看出，一个地图，一定可以转化为一个平面图，参考图1-13

      

（a）地图              （b）平面图

图1-14地图及其相应的平面图

1.9.2 算法设计

我们把m种不同的颜色编号为1，2，…，m，则对于有n个顶点的图，一个合理的着色方案就是一个n元序列c₁，c₂，…，c_n，其中，1≤c_i≤m，i=1，2，…，n。依此，可以利用回溯法进行求解：从第1个顶点开始着色，假定已经对前面j个顶点着了色，c₁，c₂，…，c_j。考虑j+1个顶点时，依次考虑c_j+1=1，2，…，m，将第一个不发生冲突的颜色编号赋给c_j+1，并准备考虑下一个顶点的着色。如果所有的颜色编号都会引起冲突，则回到c_j，依次考虑c_j=c_j+1，c_j+2，…，m，将第一个不发生冲突的颜色编号赋给c_j，并准备考虑下一个顶点的着色，如果所有的颜色编号都会引起冲突，则回到c_j-1，…。算法步骤如下：

step1 c₁=c₂=…=c_n=0，i=1，c_i=1；

step2 如果第i个顶点的颜色与其邻接点无冲突到step6；

step3 如果c_i<m，c_i=c_i+1，到step2；

step4如果i>1，i=i-1，c_i=c_i+1，到step2；

step5 终止；

step6 如果i=n，输出方案，终止算法。

step7 i=i+1，c_i=1，到step2。

这里，我们只输出一种着色方案。次算法的流程图见图1-14。

 

图1-15 m着色算法流程图

1.9.3 代码

#include<iostream>

using namespace std;

bool mGraph(bool * adjMatrix,int color[],int n,int m);

bool CanPlace(bool *adjMatrix,int color[],int k,int n);

int main(){

#define N 5

bool adjMatrix[N][N]={{0,1,1,1,0},{1,0,1,1,1},{1,1,0,1,0},{1,1,1,0,1},{0,1,0,1,0}};

int color[N]={0},i;

if(mGraph(adjMatrix[0],color,N,4))

{

for(i=0;i<N;i++)

cout<<color[i]<<"
";

cout<<endl;

}else

cout<<"no
solve\n";

return 0;

}

bool CanPlace(bool *adjMatrix,int color[],int k,int n){

int i;

for(i=0;i<n;i++)

if(adjMatrix[i*n+k]
&& color[i]==color[k])

return
false;

return true;

}

bool mGraph(bool * adjMatrix,int color[],int n,int m){

int k=0;

color[k]=1;

while(k>=0){

while(!CanPlace(adjMatrix,color,k,n))color[k]++;

if(color[k]>m){

k--;

if(k>=0)color[k]++;

else
return false;

}

else
if(k<n-1){

k++;

color[k]=1;

}

else

return
true;

}

}

1.10 最大团问题

1.10.1问题

给定无向图G=(V,E)，如果有V的子集U，使得任意u，vÎU，均有(u,v) ÎE，则称U是G的完全子图。G的极大完全子图U称为G的团，所谓极大，就是指G没有包含U的完全子图。G的最大团是指G中所含定点数最多的团。

                           

(a) 无向图                     
(b)  (a)的团               
(c)  (a)的团                  (d)  (a)的团

图1-16无向图与团

显然，图1-16(b)、(c)、(d)都是(a)的最大团，因为它们包含的顶点数都是3。

如果有V的子集U，使得任意u，vÎU，均有(u,v) ÏE，则称U是G的空子图。G的极大空子图称为G的独立集，所谓极大，就是指G没有包含U的空子图。G的最大独立集是指G中所含定点数最多的独立集。

对于无向图G=(V,E)，其补图G₁=(V₁,E₁)定义为：V₁=V，且(u,v) ÎE₁当且仅当(u,v) ÏE。显然有，U是G的完全子图，当且仅当U是其补图G₁的空子图。因此G的团与其补图G₁的独立集之间存在一一对应关系，特别地，U是G的最大图，当且仅当U是其补图G₁的最大独立集。

1.10.2 算法设计

 

1.10.3 代码

 

1.11 电路排序问题

1.11.1问题

 

1.11.2 算法设计

 

1.11.3 代码

 

STL简介

一、vector

vector是一个序列，支持随机访问元素，在尾端插入、移除元素是常量时间的，在开始或中间则是线性时间的。vector的元素个数是动态的，内存管理是自动的。vector是最简单的STL容器类，在许多情况下，是最有效的。下面的代码段都需要添加头文件

#include <iostream>

#include <vector>

using namespace std;

 

1、定义向量

int main()

{

   vector<int> v1;//定义一个空向量

   vector<int> v2(4);//定义一个长度为4，元素全为0的向量

   vector<int> v3(5,7);//定义一个长度为5，元素全为7的向量

   int a[]={1,6,8,2,5,9,3,4,7,0};

   vector<int> v4(a,a+5);//定义一个向量，并放入a的前5个元素

   return 0;

}

2、插入元素

int main()

{

   vector<int> v;//定义一个空向量

   v.push_back(9);//将9插入到向量的尾端

   v.insert(v.begin(),8);//将8插入到v的前面

   v.insert(v.begin()+1,7);//7变成v的第二个元素

   v.insert(v.begin(),5,-4);//在v的前面放5个-4

   int a[]={1,6,8,2,5,9,3,4,7,0};

   v.insert(v.begin()+1,a,a+6);//a的前6个元素插入到v的第一个元素之后

   return 0;

}

3、删除元素

int main()

{

   int a[]={1,6,8,2,5,9,3,4,7,0};

   vector<int> v(a,a+10);

   v.erase(v.begin());//删除第一个元素

   v.erase(v.begin()+3,v.end());//保留前三个元素，删除其余。

   v.clear();//清空

   return 0;

}

4、遍历

int main()

{

   int a[]={1,6,8,2,5,9,3,4,7,0};

   vector<int> v(a,a+10);

   int i;

   //用下标遍历

   for(i=0;i<v.size();i++)

cout<<v[i]<<" ";

   cout<<endl;

   //用迭代子遍历

   vector<int>::iterator it=v.begin();

   while(it!=v.end())

cout<<*it++<<" ";

   cout<<endl;

   return 0;

}

5、其他操作

1）交换两个向量的内容

int main()

{

   int a[]={1,6,8,2,5,9,3,4,7,0};

   vector<int> v1(a,a+10);

   vector<int> v2(5,1);

   v2.swap(v1);

   return 0;

}

2）排序

int main()

{

   int a[]={1,6,8,2,5,9,3,4,7,0};

   vector<int> v(a,a+10);

   sort(v.begin(),v.end());

   return 0;

}

这里需要加上头文件，下面也是

#include<algorithm>

3）逆置

int main()

{

   int a[]={1,6,8,2,5,9,3,4,7,0};

   vector<int> v(a,a+10);

   reverse(v.begin(),v.end());

   return 0;

}

4）随机排列

int main()

{

   int a[]={0,1,2,3,4,5,6,7,8,9};

   vector<int> v(a,a+10);

   vector<int>::iterator it=v.begin();

   while(it!=v.end())

cout<<*it++<<" ";

   cout<<endl;

   random_shuffle(v.begin(),v.end());

   it=v.begin();

   while(it!=v.end())

cout<<*it++<<" ";

   cout<<endl;

   return 0;

}

5）复制

int main()

{

   int a[]={0,1,2,3,4,5,6,7,8,9};

   vector<int> v1(a,a+10);

   vector<int> v2(10);

   //正常复制，将v1的前三个数复制到v2的前面

   copy(v1.begin(),v1.begin()+3,v2.begin());

   //逆序复制，将v1的后面的元素逆序复制到v2的后面

   reverse_copy(v1.begin()+3,v1.end(),v2.begin()+3);

   return 0;

}

注意：如果v2的容量不够，会出问题！

 

P1=1,p2=1,p3,…pn;

K=1

While(k>=1)

{

For(;pk<=n && pk 有冲突;pk++);

If(pk<=n)

{

If(k==n)

{

  打印P1,p2,p3,…pn;

  Pk++；

}else

  K++;

}else

{

  Pk=1;

  k--;

  pk++;

}

}