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

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

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

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

回溯法C语言举例

八皇后问题是能用回溯法解决的一个经典问题。

八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：

a[] a[i]=0表示第i行上还没有皇后；

b[] b[i]=0表示第i列反斜线/上没有皇后；

c[] c[i]=0表示第i列正斜线\上没有皇后。

棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线\上的方格的行号与列号之差均相同，这就是判断斜线的依据。

初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #include<stdio.h>

#include<stdlib.h>

#define Queens 8

int a[Queens+1]//八皇后问题的皇后所在每一行位置，从1开始算

int main()

{

int i,k,flag,not_finish=1,count=0

i=1//初始

a[1]=1

printf(the possible configuration of 8 queesns are:\n)

while(not_finish) //not_finsh=1:处理未结束

{

while(not_finish &&i<Queens+1) //处理未结束

{

for(flag=1,k=1flag &&k<ik++)//判断是否有多个皇后在同一行

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

flag=0

for(k=1flag &&k<ik++) //判断是否有多个皇后在对角线

if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))

flag=0

if(!flag) //若存在矛盾 重设第i个元素

{

if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值

{

i--//退回一步 重新试探处理前一个元素

if(i>1 &&a[i]==Queens)

a[i]=1// 当a[i]为 Queens时 将a[i]的值重置

else

if(i==1 &&a[i]==Queens)//当第一未位的值达到Queens时结束

not_finish=0

else

a[i]++

}

else

if(a[i]==Queens)

a[i]=1

else

a[i]++

}

else

if(++i<=Queens) //若前一个元素的值为Queens

if(a[i-1]==Queens)

a[i]=1

else //否则元素为前一个元素的下一个值

a[i]=a[i-1]+1

}

if (not_finish)

{

++count

printf((count-1)%3?[%2d]::\n[%2d]:,count)

for(k=1k<=Queensk++) //输出结果

printf(%d,a[k])

if(a[Queens-1]<Queens)

a[Queens-1]++

else

a[Queens-1]=1

i=Queens-1

}

}

system(pause)

} var

n,k,t,i:longint

x:array[1..100] of integer

function pa(k:integer):boolean

begin

pa:=true

for i:=1 to k-1 do

if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false

end

procedure try(k:integer)

var

i:integer

begin

if k>n then

begin

t:=t+1

exit

end

for i:=1 to n do

begin

x[k]:=i

if pa(k) then try(k+1)

end

end

begin

read(n)

t:=0

try(1)

write(t)

end. #include

#include

#define m 5

#define n 6

int sf=0

int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}}

void search(int x,int y)

{

if((x==m-1)&&(y==n-1))

sf=1

else

{

mase[x][y]=1

if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)

search(x,y+1)

if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)

search(x+1,y)

if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)

search(x,y-1)

if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)

search(x-1,y)

}

mase[x][y]=0

if(sf==1)

mase[x][y]=5//通过路径用数字的表示

}

int main()

{

int i=0,j=0

//clrscr()

search(0,0)

for(i=0i<mi++) p=></mi++)>

{

for(j=0j<nj++) p=></nj++)>

printf(%d,mase[i][j])

printf(\n)

}

system(pause)

return 0

}

回溯法解决迷宫问题PASCAL语言

program migong

var

n,k,j,x,y:integer

a:array[0..10000,0..10000] of integer

b:array[0..1000000,0..2] of integer

procedure search(x,y,i:integer)

begin

a[x,y]:=1

if (x=n) and (y=n) then

begin

for j:=1 to i-1 do

writeln(j,':(',b[j,1],',',b[j,2],')')

writeln(i,':(',x,',',y,')')

halt

end

if a[x-1,y]=0 then begin b[i,1]:=xb[i,2]:=ysearch(x-1,y,i+1)end

if a[x+1,y]=0 then begin b[i,1]:=xb[i,2]:=ysearch(x+1,y,i+1)end

if a[x,y-1]=0 then begin b[i,1]:=xb[i,2]:=ysearch(x,y-1,i+1)end

if a[x,y+1]=0 then begin b[i,1]:=xb[i,2]:=ysearch(x,y+1,i+1)end

a[x,y]:=0

end

begin

read(n)

for k:=1 to n do

for j:=1 to n do

read(a[k,j])

for k:=0 to n+1 do

begin

a[k,0]:=-1

a[k,n+1]:=-1

a[n+1,k]:=-1

a[0,k]:=-1

end

x:=1y:=1

if a[x+1,y]=0 then begin a[x,y]:=1b[1,1]:=xb[1,2]:=ysearch(x+1,y,1)a[x,y]:=0end

if a[x,y+1]=0 then begin a[x,y]:=1b[1,1]:=xb[1,2]:=ysearch(x,y+1,1)a[x,y]:=0end

end.

以java为例，希望能够帮到你。

电路板排列问题

问题描述

将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。

例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8}其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。

左上图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。插槽6和7之间无跨越连线。其余插槽之间只有1条跨越连线。在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。

问题分析

电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入。B[i][j]的值为1当且仅当电路板i在连接块Nj中。设total[j]是连接块Nj中的电路板数。对于电路板的部分排列x[1:i]，设now[j]是x[1:i]中所包含的Nj中的电路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]！=total[j]。用这个条件来计算插槽i和i+1间的连线密度。

重点难点

算法具体实现如下：

//电路板排列问题 回溯法求解

#include "stdafx.h"

#include <iostream>

#include <fstream>

using namespace std

ifstream fin("5d11.txt")

class Board

{

friend int Arrangement(int **B, int n, int m, int bestx[])

private:

void Backtrack(int i,int cd)

int n,      //电路板数

m,      //连接板数

*x,     //当前解

*bestx,//当前最优解

bestd,  //当前最优密度

*total, //total[j]=连接块j的电路板数

*now,   //now[j]=当前解中所含连接块j的电路板数

**B    //连接块数组

}

template <class Type>

inline void Swap(Type &a, Type &b)

int Arrangement(int **B, int n, int m, int bestx[])

int main()

{

int m = 5,n = 8

int bestx[9]

//B={1,2,3,4,5,6,7,8}

//N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}

cout<<"m="<<m<<",n="<<n<<endl

cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<<endl

cout<<"二维数组B如下："<<endl

//构造B

int **B = new int*[n+1]

for(int i=1 i<=n i++)

{

B[i] = new int[m+1]

}

for(int i=1 i<=n i++)

{

for(int j=1 j<=m j++)

{

fin>>B[i][j]

cout<<B[i][j]<<" "

}

cout<<endl

}

cout<<"当前最优密度为:"<<Arrangement(B,n,m,bestx)<<endl

cout<<"最优排列为："<<endl

for(int i=1 i<=n i++)

{

cout<<bestx[i]<<" "

}

cout<<endl

for(int i=1 i<=n i++)

{

delete[] B[i]

}

delete[] B

return 0

}

//核心代码

void Board::Backtrack(int i,int cd)//回溯法搜索排列树

{

if(i == n)

{

for(int j=1 j<=n j++)

{

bestx[j] = x[j]

}

bestd = cd

}

else

{

for(int j=i j<=n j++)

{

//选择x[j]为下一块电路板

int ld = 0

for(int k=1 k<=m k++)

{

now[k] += B[x[j]][k]

if(now[k]>0 && total[k]!=now[k])

{

ld ++

}

}

//更新ld

if(cd>ld)

{

ld = cd

}

if(ld<bestd)//搜索子树

{

Swap(x[i],x[j])

Backtrack(i+1,ld)

Swap(x[i],x[j])

//恢复状态

for(int k=1 k<=m k++)

{

now[k] -= B[x[j]][k]

}

}

}

}

}

int Arrangement(int **B, int n, int m, int bestx[])

{

Board X

//初始化X

X.x = new int[n+1]

X.total = new int[m+1]

X.now = new int[m+1]

X.B = B

X.n = n

X.m = m

X.bestx = bestx

X.bestd = m+1

//初始化total和now

for(int i=1 i<=m i++)

{

X.total[i] = 0

X.now[i] = 0

}

//初始化x为单位排列并计算total

for(int i=1 i<=n i++)

{

X.x[i] = i

for(int j=1 j<=m j++)

{

X.total[j] += B[i][j]

}

}

//回溯搜索

X.Backtrack(1,0)

delete []X.x

delete []X.total

delete []X.now

return X.bestd

}

template <class Type>

inline void Swap(Type &a, Type &b)

{

Type temp=a

a=b

b=temp

}

算法效率

在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd>=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。

程序运行结果为：

/*

* snake

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define DEBUG 0

#define printpos() \

printf("File: %s\tLine: %d\n", __FILE__, __LINE__)fflush(stdout)

#define CALLOC(ARRAY, NUM, TYPE) \

ARRAY = (TYPE*) calloc(NUM, sizeof(TYPE)) \

if (ARRAY == NULL) { \

printf("File: %s, Line: %d: ", __FILE__, __LINE__)\

printf("Allocating memory failed.\n") \

exit(0) \

}

#define REALLOC(ARRAY, NUM, TYPE) \

ARRAY = (TYPE*) realloc(ARRAY, (NUM)*sizeof(TYPE)) \

if (ARRAY == NULL) { \

printf("File: %s, Line: %d: ", __FILE__, __LINE__)\

printf("Allocating memory failed.\n") \

exit(0) \

}

const int START = -1

const int HOME = -2

#if DEBUG

int m=4, n=4

int a[4][4] = {{7, 0, 4, 18}, {4, 0, 1, 1}, {15, 7, 11, -1}, {0, 12, -2, 0}}

#else

int m=0, n=0

int **a=NULL

#endif

struct pos {

int x

int y

}

typedef struct pos pos

struct node {

pos p

int mv

int n

}

typedef struct node node

const pos mv[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }

/*

* get m, n, a and check them

*/

int setup()

{

int nstart=0, nhome=0

int i, j

#if DEBUG

#else

//get the dimension of the matrix and allocate memory

printf("Please input the number of rows of the matrix: ")

scanf("%d", &m)

if (m<=0) {

printf("Number of rows must be greater than 0.\n")

exit(0)

}

a = (int**) calloc(m, sizeof(int*))

if (a == NULL) {

printf("Allocate memory failed.\n")

exit(1)

}

printf("Please input the number of columns of the matrix: ")

scanf("%d", &n)

if (n<=0) {

printf("Number of columns must be greater than 0.\n")

exit(0)

}

for (i=0i<mi++) {

a[i] = (int*) calloc(n, sizeof(int))

if (a[i] == NULL) {

printf("Allocate memory failed.\n")

exit(1)

}

}

//get the matrix

printf("Please input the matrix, entities seperated by blank:\n")

for (i=0i<mi++) {

for (j=0j<nj++) {

scanf("%d", &a[i][j])

}

}

#endif

//check the matrix

for (i=0i<mi++) {

for (j=0j<nj++) {

if (a[i][j] == START) {

nstart++

if (nstart >1) {

printf("More than 1 starting point.\n")

exit(0)

}

} else if (a[i][j] == HOME) {

nhome++

if (nhome >1) {

printf("More than 1 home point.\n")

exit(0)

}

} else if (a[i][j] <0) {

printf("a[%d][%d] = %d has no meaning.\n", i, j, a[i][j])

exit(0)

}

}

}

if (nstart == 0) {

printf("No starting point.\n")

exit(0)

}

if (nhome == 0) {

printf("No home point.\n")

exit(0)

}

//output the matrix

printf("The matrix (%d X %d):\n", m, n)

for (i=0i<mi++) {

for (j=0j<nj++) {

printf("%d\t", a[i][j])

}

printf("\n")

}

return 0

}

int solve(node** optpath)

{

pos dest //destinating point

node* curpath = NULL //current path

node** sol = NULL

int nsol = 0

int nsteps //number of steps

int i, j

int curmv = -1

int sucmv = 0 //sucessfully moved

int sum

int maxsum=0

//setup starting point

for (i=0i<mi++) {

for (j=0j<nj++) {

if (a[i][j] == START) {

dest.x = i

dest.y = j

break

}

}

}

nsteps = 0

CALLOC(curpath, nsteps+1, node)

curpath[0].p.x = dest.x

curpath[0].p.y = dest.y

curpath[0].mv = -1

a[dest.x][dest.y] = 0

curmv = 0

while (1) {

for (sucmv=0, curmv=curpath[nsteps].mv+1curmv<4curmv++) {

dest.x = curpath[nsteps].p.x + mv[curmv].x

dest.y = curpath[nsteps].p.y + mv[curmv].y

if (dest.x <0 || dest.x >= m || dest.y <0 || dest.y >= n) {

curpath[nsteps].mv = curmv

continue

}

if (a[dest.x][dest.y] == 0) {

curpath[nsteps].mv = curmv

continue

}

nsteps++

REALLOC(curpath, nsteps+1, node)

curpath[nsteps].p.x = dest.x

curpath[nsteps].p.y = dest.y

curpath[nsteps-1].mv = curmv

curpath[nsteps].mv = -1

curpath[nsteps].n = a[dest.x][dest.y]

a[dest.x][dest.y] = 0

sucmv = 1

break

}

if (sucmv) {

if (curpath[nsteps].n == HOME) {

nsol++

REALLOC(sol, nsol, node*)

CALLOC(sol[nsol-1], nsteps+1, node)

memcpy(sol[nsol-1], curpath, (nsteps+1)*sizeof(node))

//back

a[curpath[nsteps].p.x][curpath[nsteps].p.y] = curpath[nsteps].n

nsteps--

if (nsteps == -1 &&curpath[0].mv == 3) break

REALLOC(curpath, nsteps+1, node)

} else {

continue

}

} else {

a[curpath[nsteps].p.x][curpath[nsteps].p.y] = curpath[nsteps].n

nsteps--

if (nsteps == -1 &&curpath[0].mv == 3) break

REALLOC(curpath, nsteps+1, node)

}

}

//printf("number of solutions: %d\n", nsol)

for (maxsum=0, i=0i<nsoli++) {

//printf("Solution %d \n", i)

//printf("\tPath: ")

sum = -1*HOME

for (j=0j++) {

//printf("(%d, %d)\t", sol[i][j].p.x, sol[i][j].p.y)

sum += sol[i][j].n

if (sol[i][j].mv == -1) break

}

//printf("\n\tSum of apples: %d\n", sum)

if (sum>maxsum) {

maxsum = sum

*optpath = sol[i]

}

}

return 0

}

int output(node* path)

{

int i=0, sum=0

printf("Path: ")

sum = -1*HOME

for (i=0i++) {

printf("(%d, %d)\t", path[i].p.x, path[i].p.y)

sum += path[i].n

if (path[i].mv == -1) break

}

printf("\nSum of apples: %d\n", sum)

return 0

}

int main()

{

node* path=NULL

setup()

solve(&path)

output(path)

return 0

}

编译、链接、运行程序，输入与输出如下：

:!gcc -Wall tmp.c -o tmp

:! ./tmp

Please input the number of rows of the matrix: 5

Please input the number of columns of the matrix: 5

Please input the matrix, entities seperated by blank:

1 7 9 7 0

-2 8 10 8 7

0 10 8 2 -1

4 3 0 7 0 9

1 2 5 1 0 7

The matrix (5 X 5):

1 7 9 7 0

-2 8 10 8 7

0 10 8 2 -1

4 3 0 7 0

9 1 2 5 1

Path: (2, 4)(1, 4) (1, 3) (0, 3) (0, 2) (1, 2) (2, 2) (2, 3) (3, 3) (4, 3) (4, 2) (4, 1) (4, 0) (3, 0) (3, 1) (2, 1) (1, 1) (0, 1) (0, 0) (1, 0)

Sum of apples: 108

:!gcc -Wall tmp.c -o tmp

:! ./tmp

Please input the number of rows of the matrix: 4

Please input the number of columns of the matrix: 4

Please input the matrix, entities seperated by blank:

7 0 4 18

4 0 1 1

15 7 11 -1

0 12 -2 0

The matrix (4 X 4):

7 0 4 18

4 0 1 1

15 7 11 -1

0 12 -2 0

Path: (2, 3) (1, 3) (0, 3) (0, 2) (1, 2) (2, 2) (2, 1) (3, 1) (3, 2)

Sum of apples: 54

---