回溯算法的主要思想是每次只构造解的一个分量，
然后按照下面的方法来评估这个部分构造解。
如果一个部分构造解可以进一步构造而不会违反问题的约束，
我们就接受对解的下一个分量所做的第一个合法选择。
如果无法对下一分量进行合法的选择，就不必再剩下的任何分量再做任何选择了。
在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。
算法：
Backtrack( X[1...i] )
// 输入：X[1...i]确定了一个解的前面i个有希望的分量
// 输出：代表问题的解的所有元组
if X[1...i]是一个解
write X[1...i]
else
for 和X[1...i]以及约束相容的每一个元素x属于S
X[i+1] = x;
Backtrack(X[1...i+1])
回溯并非是高效的技术，在最坏情况下，对于某些问题，它可能必须
生成一个呈指数增长的状态空间中所有的可能解。提高效率的关键在于修
剪掉它的状态空间树中足够多的分支。
摘自《算法设计与分析基础》
/* ------------------------------------------------------------------------- */
/* ------------------------------------------------------------------------- */
下面用回溯法解答四个经典问题：
八皇后问题，马踏棋盘问题，迷宫问题，八数码问题
主要考虑回溯算法的实现，当N增大时效率方面并不是很理想。
八皇后问题可以利用对称性和加列攻击标记改进程序性能。
马踏棋盘问题可以利用对每个方向加上优先权值改进程序性能。
八数码问题性能瓶颈则是在路径重复的判断方面。
author: yihui.L
time: 2008.08.09
/* ------------------------------------------------------------------------- */
/*****************************************************************************/
/*
* 八皇后问题
*/
#include <stdio.h>
#define N 8 /* 皇后个数 */
int sum = 0; /* 总排列数 */
int q[N]; /* 皇后位置 */
/* 输出N皇后排列方式 */
void Print( int q[], int n )
{
int i, j;
for ( i = 0; i < n; i++ ) {
for ( j = 0; j < n; j++ ) {
if ( j == q[i] ) printf("Q ");
else printf("_ ");
}
printf("/n");
}
}
/* 判断是否存在攻击 */
int Attacked( int q[], int n )
{
int i;
for( i = 0; i < n; i++ ) {
if( ( 0 == q[n] - q[i] ) || /* 存在列攻击 */
( n - i == q[n] - q[i] ) || /* 正斜角攻击 */
( n - i == q[i] - q[n] ) ) /* 反斜角攻击 */
return 1;
}
return 0;
}
void Queen( int q[], int n )
{
int i;
if ( n >= N ) {
sum++;
/* Print( q, n );
getchar(); */
} else {
for ( i = 0; i < N; i++ ) {
q[n] = i;
if ( !Attacked( q, n ) )
Queen( q, n + 1 );
}
}
}
int main()
{
Queen( q, 0 );
printf( "sum = %d/n", sum );
return 0;
}
/*****************************************************************************/
/*
* 马踏棋盘问题
*/
#include <stdio.h>
#include <time.h>
#define CB_SIZE 5
#define STEP_NUM (CB_SIZE*CB_SIZE)
int chessboard[CB_SIZE][CB_SIZE];
/* 马在棋盘中的八个方向 */
#define DIR_NUM 8
int direction[DIR_NUM][2] = {
{ 2, 1 }, { 2, -1 },
{ 1, -2 }, { -1, -2 },
{ -2, -1 }, { -2, 1 },
{ -1, 2 }, { 1, 2 },
};
int sum;
/* 棋子的位置是否在棋盘中 */
int IsInBoard( int x, int y )
{
if ( x < 0 || CB_SIZE <= x ||
y < 0 || CB_SIZE <= y )
return 0;
else
return 1;
}
/* 输出马走的路径 */
void PrintBoard( int chessboard[CB_SIZE][CB_SIZE] )
{
int i, j;
for( i = 0; i < CB_SIZE; i++ ) {
for( j = 0; j < CB_SIZE; j++ ) {
printf( " %2d", chessboard[i][j] );
}
printf( "/n" );
}
}
void HorseJump( int nowX, int nowY, int n )
{
int i;
int nextX, nextY;
if ( n > STEP_NUM ) {
sum++;
/* PrintBoard( chessboard );
getchar(); */
} else {
for ( i = 0; i < DIR_NUM; i++ ) {
nextX = nowX + direction[i][0];
nextY = nowY + direction[i][1];
if ( IsInBoard( nextX, nextY ) &
0 == chessboard[nextX][nextY] ) {
chessboard[nextX][nextY] = n;
HorseJump( nextX, nextY, n + 1 );
chessboard[nextX][nextY] = 0;
}
}
}
}
int main()
{
int startX;
int startY;
startX = startY = 0;
chessboard[startX][startY] = 1;
HorseJump( startX, startY, 2 );
printf("sum = %d/n", sum);
return 0;
}
/*****************************************************************************/
/*
* 迷宫问题
*/
#include <stdio.h>
int maze[8][8] = {
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,1,
1,0,1,1,0,1,0,1,
1,0,1,1,0,0,0,1,
1,0,0,0,1,1,0,1,
1,0,1,0,0,0,0,1,
1,0,0,0,1,1,0,0,
1,1,1,1,1,1,1,1,
};
#define DIR_NUM 4
int direction[DIR_NUM][2] = {
{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }
};
void PrintPath()
{
int i, j;
for ( i = 0; i < 8; i++ ) {
for ( j = 0; j < 8; j++ ) {
switch( maze[i][j] ) {
case 0: printf("_ "); break;
case 1: printf("# "); break;
case 2: printf("* "); break;
}
}
printf("/n");
}
}
void FindThePath( int nowX, int nowY,
int endX, int endY )
{
int i;
int nextX, nextY;
if ( nowX == endX && nowY == endY ) {
PrintPath();
getchar();
} else {
for ( i = 0; i < DIR_NUM; i++ ) { /* 尝试四个方向的路径 */
nextX = nowX + direction[i][0];
nextY = nowY + direction[i][1];
if ( maze[nextX][nextY] ) continue; /* 如果有墙或者已经走过 */
maze[nextX][nextY] = 2; /* 标记该点 */
FindThePath(nextX, nextY, endX, endY);
maze[nextX][nextY] = 0; /* 回溯 */
}
}
}
int main()
{
int startX = 1;
int startY = 0;
int endX = 6;
int endY = 7;
maze[startX][startY] = 2;
FindThePath(startX, startY, endX, endY);
return 0;
}
/*****************************************************************************/
/*
* 八数码问题
*/
#include <stdio.h>
#include <stdlib.h>
#define DIR_NUM 4
int direction[DIR_NUM][2] = {
{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }
};
#define ST_MAX 16
int stNum = 0;
int stack[ST_MAX][3][3];
int dirSt[ST_MAX];
void Push( int st[3][3], int d )
{
int i, j;
for ( i = 0; i < 3; i++ ) {
for ( j = 0; j < 3; j++ )
stack[stNum][i][j] = st[i][j];
}
dirSt[stNum] = d;
stNum++;
}
void Pop()
{
if ( --stNum < 0 ) stNum = 0;
}
int Top()
{
return stNum;
}
int StackFull()
{
if ( stNum < ST_MAX ) return 0;
else return 1;
}
void PrintTrace()
{
int i;
for ( i = 0; i < stNum; i++ )
{
switch( dirSt[i] )
{
case 0: printf("down/n"); break;
case 1: printf("right/n"); break;
case 2: printf("up/n"); break;
case 3: printf("left/n"); break;
}
}
}
int IsEqual( int a[3][3], int b[3][3] )
{
int i, j;
for ( i = 0; i < 3; i++ ) {
for ( j = 0; j < 3; j++ )
if ( a[i][j] != b[i][j] )
return 0;
}
return 1;
}
void PrintNumber( int src[3][3] )
{
int i, j;
printf("/n------/n");
for ( i = 0; i < 3; i++ ) {
for ( j = 0; j < 3; j++ ) {
printf("%d ", src[i][j]);
}
printf( "/n" );
}
}
int IsOutside( int x, int y )
{
if ( x < 0 || 3 <= x ||
y < 0 || 3 <= y )
return 1;
else
return 0;
}
void FindNumber( int src[3][3], int num, int *x, int *y )
{
int i, j;
for ( i = 0; i < 3; i++ ) {
for ( j = 0; j < 3; j++ ) {
if ( src[i][j] == num ) {
*x = i;
*y = j;
return ;
}
}
}
}
int TraceExisted( int st[3][3], int d )
{
int i;
for ( i = 0; i < stNum; i++ ) {
if ( ( d == dirSt[i] ) && IsEqual( stack[i], st ) )
return 1;
}
return 0;
}
void SwapNumber( int *a, int *b )
{
int temp = *a;
*a = *b;
*b = temp;
}
void FindSolution( int start[3][3], int stop[3][3], int x, int y )
{
int i;
int nextX, nextY;
if ( IsEqual( start, stop ) ) {
printf("-- %d --/n", Top()); /* 所走的步数 */
PrintTrace();
PrintNumber( stop );
getchar();
} else {
for ( i = 0; i < DIR_NUM; i++ ) {
nextX = x + direction[i][0];
nextY = y + direction[i][1];
if ( IsOutside( nextX, nextY ) ) continue; /* 不在方格内 */
if ( StackFull() ) continue; /* 路径太深 */
SwapNumber( &start[x][y], &start[nextX][nextY] );
if ( TraceExisted( start, i ) ) { /* 路径重复 */
SwapNumber( &start[x][y], &start[nextX][nextY] ); /* 回溯 */
continue;
}
Push( start, i ); /* 保存路径 */
FindSolution( start, stop, nextX, nextY );
SwapNumber( &start[x][y], &start[nextX][nextY] ); /* 回溯 */
Pop();
}
}
}
void EightNumber( int start[3][3], int stop[3][3] )
{
int x, y;
FindNumber( start, 0, &x, &y ); /* 找出空格的位置 */
FindSolution( start, stop, x, y );
}
int startState[3][3] = {
0, 1, 2,
3, 4, 5,
6, 7, 8
};
int stopState[3][3] = {
1, 2, 0,
3, 4, 5,
6, 7, 8
};
int main()
{
EightNumber( startState, stopState );
return 0;
}
/*****************************************************************************/
回溯是按照某种条件在解空间中往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索。
符号声明：
解空间：[a1,a2,a3,...,an];
x[k]为解空间元素的索引， 0 <= x[k] < n;k为数组x的索引；
a[x[0~n-1]]表示一组解。
//判断解空间中的a[x[k]]是否满足条件
bool CanbeUsed(int k)
{
if(x[k] 不满足条件) return false;
else return true;
}
算法描述如下：
(1) k = 0; x[k] = -1;
(2)while( k >= 0 )
a. x[k] = x[k] + 1;
b. while(x[k] < n && ( ! CanbeUsed(k) ))//遍历解空间，直到找到可用的元素
x[k] = x[k] + 1;
c. if(x[k] > n -1)//x[k]超出了解空间a的索引范围
k = k - 1; //回溯
d. else if( k == n -1)//找到了n - 1个元素
输出一组解
e. else //当前元素可用，更新变量准备寻找下一个元素
k = k + 1;
x[k] = -1;
实例源码：
1.回溯之全排列(VC6.0/VS2005)==============================================
////////////////////////////////
//回溯搜索之全排列
#include<iostream>
#include<string>
using namespace std;
#define N 100
string str;
int x[N];
bool IsPlaced(int n)
{
for(int i = 0; i < n ; ++i)
{
if(x[i] == x[n])
return false;
}
return true;
}
void PrintResult()
{
for(int i = 0; i < str.length(); ++i)
cout<<str[x[i]];
cout<<endl;
}
void Arrange()
{
int k = 0; x[k] = -1;
while(k >= 0)
{
x[k] = x[k] + 1;
while(x[k] < str.length() && !IsPlaced(k))
{
x[k] = x[k] + 1;
}
if(x[k] > str.length() - 1)
{
k = k - 1;
}
else if( k == str.length() - 1)
{
PrintResult();
}
else
{
k = k + 1;
x[k] = -1;
}
}
}
int main()
{
cout<<"input:"<<endl;
while(cin>>str)
{
cout<<str<<" arrange......"<<endl;
Arrange();
cout<<"input:"<<endl;
}
return 0;
}
2.八皇后(N皇后)============================================================
////////////////////////////////////////
//回溯之N皇后问题[ 4<=N<=100]
#include <iostream>
using namespace std;
#define N 8
//用于防置皇后的棋盘
//0表示未放置，1表示已放置
int board[N][N]={
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0
};
int x[N];
//按列摆放
bool CanbePlaced(int k)
{
for(int i = 0; i < k ; ++i)
{
if(x[i] == x[k] || abs(x[i] - x[k]) == abs(i - k))
return false;
}
return true;
}
void PrintResult()
{
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
board[i][j] = 0;
for(int i = 0; i < N; ++i)
board[i][x[i]] = 1;
for(int i = 0; i < N; ++i)
{
for(int j = 0; j < N; ++j)
{
if(board[i][j] == 1)
cout<<"* ";
else
cout<<"- ";
}
cout<<endl;
}
cout<<endl;
}
int count = 0;
void NQ()
{
int k = 0;
x[k] = -1;
while( k >= 0 )
{
x[k] = x[k] + 1;
while(x[k] < N && !CanbePlaced(k))
x[k] = x[k] + 1;
if(x[k] > N - 1)
{
k = k - 1;
}
else if( k == N - 1)
{
PrintResult();
count ++;
}
else
{
k = k + 1;
x[k] = - 1;
}
}
}
int main()
{
NQ();
cout<<"一共:"<<count<<"组摆放方法"<<endl;
system("pause");
return 0;
}
3.回溯之整数划分==========================================================
/////////////////////////
//回溯之整数划分
#include<iostream>
using namespace std;
#define N 100
int x[N];
int result[N];//保存一组解
int count = 0;//解的组数
int sum(int k)
{
int sum = 0;
for(int i = 0; i <= k; ++i)
sum += result[x[i]];
return sum;
}
//a1>=a2>=...>=an
//a1+a2+...+an = n
bool IsSuit(int n,int k)
{
if(sum(k) > n)
return false;
if(k > 0 && result[x[k]] > result[x[k-1]] )
return false;
return true;
}
void PrintResult(int n,int k)
{
if(sum(k) == n)
{
for(int i = 0; i <= k; ++i)
cout<<result[x[i]]<<" ";
cout<<endl;
count++;
}
}
void SplitInt(int n)
{
//解空间[n,n-1,n-2,...,1]
for(int i = 0; i < n; ++i)
{
result[i] = n - i;
}
for(int m = 1; m <= n; ++m)
{
int k = 0;
x[k] = -1;
while( k >= 0 )
{
x[k] = x[k] + 1;
while(x[k] < n && !IsSuit(n,k) )
x[k] = x[k] + 1;
if(x[k] > n - 1)
k = k - 1;
else if( k == m - 1)
{
PrintResult(n,k);
}
else
{
k = k + 1;
x[k] = -1;
}
}
}
}
int main()
{
int num;
while(cin>>num)
{
count = 0;
SplitInt(num);
cout<<"共:"<<count<<"组"<<endl;
}
return 0;
}
4.回溯之组合===============================================================
/////////////////////////////////////////
//回溯之组合
//找出所有从m个元素中选取n(n<=m)元素的组合
#include<iostream>
using namespace std;
#define M 5
#define N 3
char elements[M]={'a','b','c','d','e'};
int x[N];
bool CanbeUsed(int k)
{
for(int i = 0; i < k; ++i)
if(x[i] == x[k])
return false;
if(k > 0 && elements[x[k]] < elements[x[k-1]])
{
return false;
}
return true;
}
void PrintResult()
{
for(int i = 0; i < N; ++i)
{
cout<<elements[x[i]]<< " ";
}
cout<<endl;
}
void Compose()
{
int k = 0;
x[k] = -1;
while( k >= 0 )
{
x[k] = x[k] + 1;
while(x[k] < M && !CanbeUsed(k))
x[k] = x[k] + 1;
if(x[k] > M - 1)
k = k - 1;
else if( k == N - 1)
{
PrintResult();
}
else
{
k = k + 1;
x[k] = -1;
}
}
}
int main()
{
Compose();
system("pause");
return 0;
}
5.回溯之0/1背包=============================================================
//////////////////////////////////////////////////
//回溯之0/1背包问题
//.0/1背包
//一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.
//若每种物品只有一件求旅行者能获得最大总价值。
#include<iostream>
using namespace std;
#define M 50
#define N 5
int weight[N] = {10,15,12,19,18};
int value[N] = {5,2,2,1,1};
int x[N]={-1,-1,-1,-1,-1};
int max_weight = 0;
int max_value = 0;
bool CanbeUsed(int k)
{
for(int i = 0; i < k ; ++i)
{
if(x[i] == x[k] )
return false;
}
return true;
}
void CalResult(int k)
{
int totalValue = 0;
int totalWeight= 0;
for(int i = 0 ; i <= k; ++i)
{
totalValue += value[x[i]];
totalWeight += weight[x[i]];
}
if(totalValue > max_value && totalWeight <= M )
{
max_value = totalValue;
max_weight = totalWeight;
cout<< totalWeight << " "<<totalValue<<endl;
}
}
void Bag()
{
//分别计算去1~N个背包的情况
for(int n = 1; n <= N; ++n)
{
int k = 0;
x[k] = -1;
while( k >= 0)
{
x[k] = x[k] + 1;
while(x[k] < n && !CanbeUsed(k))
x[k] = x[k] + 1;
if(x[k] > n - 1)
{
k = k - 1;
}
else if( k == n - 1)
{
CalResult(k);
}
else
{
k = k + 1;
x[k] = -1;
}
}
}
}
int main()
{
Bag();
cout<<"最优解为weight:" << max_weight << ",value:" <<max_value<<endl;
system("pause");
return 0;
}