Php文档 Php问答行业资讯 Php论坛 Php手册 Php博客

游戏榜单

软件榜单

关闭导航

热搜榜

热门下载

热门标签

关闭搜索

php爱好者> php文档>回溯转载

回溯转载

时间：2010-10-09 来源：wqfhenanxc

转载自http://fuliang.javaeye.com/blog/164686和http://fuliang.javaeye.com/blog/164744

回溯法之一---算法框架及基础

回溯法其实也是一种搜索算法，它可以方便的搜索解空间。
回溯法解题通常可以从以下三步入手：
1、针对问题，定义解空间
2、确定易于搜索的解空间结构
3、以深度优先的方式搜索解空间，并在搜索的过程中进行剪枝
回溯法通常在解空间树上进行搜索，而解空间树通常有子集树和排列树。
针对这两个问题，算法的框架基本如下：
用回溯法搜索子集合树的一般框架：

Cpp代码

void backtrack(int t){
if(t > n) output(x);
else{
for(int i = f(n,t); i <= g(n,t);i++){
x[t] = h(i);
if(constraint(t) && bound(t)) backtrack(t+1);
}
}
}

void backtrack(int t){
  if(t > n) output(x);
  else{
    for(int i = f(n,t); i <= g(n,t);i++){
          x[t] = h(i);
          if(constraint(t) && bound(t)) backtrack(t+1);
     }
  }
}

用回溯法搜索排列树的算法框架：

Cpp代码

void backtrack(int t){
if(t > n) output(x);
else{
for(int i = f(n,t); i <= g(n,t);i++){
swap(x[t],x[i]);
if(constraint(t) && bound(t)) backtrack(t+1);
swap(x[t],x[i]);
}
}
}

void backtrack(int t){
  if(t > n) output(x);
  else{
    for(int i = f(n,t); i <= g(n,t);i++){
          swap(x[t],x[i]);
          if(constraint(t) && bound(t)) backtrack(t+1);
          swap(x[t],x[i]); 
    }
  }
}

其中f(n,t),g(n,t)表示当前扩展结点处未搜索过的子树的起始标号和终止标号,
h(i)表示当前扩展节点处，x[t]第i个可选值。constraint(t)和bound(t)是当前
扩展结点处的约束函数和限界函数。constraint(t)返回true时，在当前扩展结点
x[1:t]取值满足约束条件，否则不满足约束条件，可减去相应的子树。bound(t)返
回的值为true时，在当前扩展结点x[1:x]处取值未使目标函数越界，还需要由backtrack(t+1)
对其相应的子树进一步搜索。
用回溯法其实质上是提供了搜索解空间的方法，当我们能够搜遍解空间时，
显然我们就能够找到最优的或者满足条件的解。这便是可行性的问题，而效率可以
通过剪枝函数来降低。但事实上一旦解空间的结构确定了，很大程度上时间复杂度
也就确定了，所以选择易于搜索的解空间很重要。
下面我们看看两个最简单的回溯问题，他们也代表了两种搜索类型的问题：子集合问题和
排列问题。
第一个问题：
求集合s的所有子集(不包括空集),我们可以按照第一个框架来写代码：

Cpp代码

#include<iostream>
using namespace std;
int s[3] = {1,3,6};
int x[3];
int N = 3;
void print(){
for(int j = 0; j < N; j++)
if(x[j] == 1)
cout << s[j] << " ";
cout << endl;
}
void subset(int i){
if(i >= N){
print();
return;
}
x[i] = 1;//搜索右子树
subset(i+1);
x[i] = 0;//搜索左子树
subset(i+1);
}
int main(){
subset(0);
return 0;
}

#include<iostream>
using namespace std;

int s[3] = {1,3,6};
int x[3];
int  N = 3;
void print(){
   for(int j = 0; j < N; j++)
        if(x[j] == 1)
           cout << s[j] << " ";
   cout << endl;
}

void subset(int i){
        if(i >= N){
        print();
            return;
        }

        x[i] = 1;//搜索右子树
        subset(i+1);
        x[i] = 0;//搜索左子树
        subset(i+1);
}

int main(){
  subset(0);
  return 0;
}

下面我们看第二个问题：排列的问题，求一个集合元素的全排列。
我们可以按照第二个框架写出代码：

Cpp代码

#include<iostream>
using namespace std;
int a[4] = {1,2,3,4};
const int N = 4;
void print(){
for(int i = 0; i < N; i++)
cout << a[i] << " ";
cout << endl;
}
void swap(int *a,int i,int j){
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void backtrack(int i){
if(i >= N){
print();
}
for(int j = i; j < N; j++){
swap(a,i,j);
backtrack(i+1);
swap(a,i,j);
}
}
int main(){
backtrack(0);
return 0;
}

#include<iostream>
using namespace std;

int a[4] = {1,2,3,4};
const int N = 4;

void print(){
        for(int i = 0; i < N; i++)
                   cout << a[i] << " ";
    cout << endl;
}

void swap(int *a,int i,int j){
  int temp;
  temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

void backtrack(int i){
        if(i >= N){
                print();
        }
        for(int j = i; j < N; j++){
                swap(a,i,j);
                backtrack(i+1);
                swap(a,i,j);
        }
}

int main(){
  backtrack(0);
  return 0;
}

这两个问题很有代表性，事实上有许多问题都是从这两个问题演变而来的。第一个问题，它穷举了所有问题的子集，这是所有第一种类型的基础，第二个问题,它给出了穷举所有排列的方法，这是所有的第二种类型的问题的基础。理解这两个问题,是回溯算法的基础.
下面看看一个较简单的问题：
整数集合s和一个整数sum，求集合s的所有子集su,使得su的元素之和为sum。
这个问题很显然是个子集合问题，我们很容易就可以把第一段代码修改成这个问题的代码：

Cpp代码

int sum = 10;
int r = 0;
int s[5] = {1,3,6,4,2};
int x[5];
int N = 5;
void print(){
for(int j = 0; j < N; j++)
if(x[j] == 1)
cout << s[j] << " ";
cout << endl;
}
void sumSet(int i){
if(i >= N){
if(sum == r) print();
return;
}
if(r < sum){//搜索右子树
r += s[i];
x[i] = 1;
sumSet(i+1);
r -= s[i];
}
x[i] = 0;//搜索左子树
sumSet(i+1);
}
int main(){
sumSet(0);
return 0;
}

int sum = 10;
int r = 0;
int s[5] = {1,3,6,4,2};
int x[5];
int  N = 5;

void print(){
   for(int j = 0; j < N; j++)
        if(x[j] == 1)
           cout << s[j] << " ";
   cout << endl;
}
void sumSet(int i){
        if(i >= N){
                if(sum == r) print();
            return;
        }
        if(r < sum){//搜索右子树
          r += s[i];
          x[i] = 1;
          sumSet(i+1);
          r -= s[i]; 
        }
        x[i] = 0;//搜索左子树
        sumSet(i+1);
}

int main(){
  sumSet(0);
  return 0;
}

回溯法之二---8皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上.
问题分析:
第一步定义问题的解空间
这个问题解空间就是8个皇后在棋盘中的位置.
第二步定义解空间的结构
可以使用8*8的数组，但由于任意两个皇后都不能在同行，我们可以用数组下标表示
行，数组的值来表示皇后放的列，故可以简化为一个以维数组x[9]。
第三步以深度优先的方式搜索解空间，并在搜索过程使用剪枝函数来剪枝
根据条件:x[i] == x[k]判断处于同一列
abs(k-i) == abs(x[k]-x[i]判断是否处于同一斜线
我们很容易写出剪枝函数：
Cpp代码

bool canPlace(int k){
for(int i = 1; i < k; i++){
//判断处于同一列或同一斜线
if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i])) return false;
}
return true;
}

bool canPlace(int k){
        for(int i = 1; i < k; i++){
        //判断处于同一列或同一斜线
           if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i]))                      return false;
        }
        return true;
}

然后我们按照回溯框架一，很容易写出8皇后的回溯代码：
Cpp代码

void queen(int i){
if(i > 8){
print();
return;
}
for(int j = 1; j <= 8; j++){
x[i] = j;//记录所放的列
if(canPlace(i)) queen(i+1);
}
}

void queen(int i){
        if(i > 8){
                print();
                return;
        }
        for(int j = 1; j <= 8; j++){
          x[i] = j;//记录所放的列
          if(canPlace(i)) queen(i+1);
        }
}

整个代码：
Cpp代码

#include<iostream>
#include<cmath>
using namespace std;
int x[9];
void print(){
for(int i = 1; i <= 8; i++)
cout << x[i] << " ";
cout << endl;
}
bool canPlace(int k){
for(int i = 1; i < k; i++){
//判断处于同一列或同一斜线
if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i]))
return false;
}
return true;
}
void queen(int i){
if(i > 8){
print();
return;
}
for(int j = 1; j <= 8; j++){
x[i] = j;
if(canPlace(i)) queen(i+1);
}
}
int main(){
queen(1);
return 0;
}

八皇后问题的非递归实现
这里给出的递归实现和上面的差不多，放在这里主要是为了和下面的非递归作对应，因为它们的变量相似。
递归实现：

#include "stdio.h"

#include "stdlib.h"

#include "time.h"

/**//* 记录当前的放置方案 */

int *x;

/**//* 皇后的个数N 和方案数目 */

int n,sum=0;

/**//* 检查参数所指示的这一行皇后放置方案是否满足要求 */

int Place(int);

/**//* 递归方法求取皇后放置方案*/

void Queen1(void);

/**//* 用户递归求取皇后放置方案的递归方法 */

void TraceBack(int);

/**//* 打印当前成功的放置方案 */

void PrintMethod(void);

void main(void)

{

long start,stop;

printf("input n: ");

scanf("%d",&n);

x=(int *)malloc(sizeof(int)*n);

time(&start);/**//*记录开始时间*/

Queen1();

time(&stop);/**//*记录结束时间*/

printf("\nmethod total %d \n",sum);

printf("\nuse %d seconds \n",(int)(stop-start));

}

int Place(int r)

{

int i;

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

{

if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))

return 0;

}

return 1;

}

void TraceBack(int r)

{

int i;

if(r>=n)

{

sum++;

/**//* PrintMethod(); */

}else

{

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

{

x[r]=i;

if(Place(r)) TraceBack(r+1);

}

void PrintMethod(void)

{

int i,j;

printf("\nmethod %d\n",sum);

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

{

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

{

if(j==x[i]) printf("*");

else printf("#");

}

printf("\n");

}

void Queen1(void)

{

TraceBack(0);

}

非递归实现：

#include "stdio.h"

#include "stdlib.h"

#include "time.h"

/**//* 记录当前的放置方案 */

int *x;

/**//* 皇后的个数N 和方案数目 */

int n,sum=0;

/**//* 检查参数所指示的这一行皇后放置方案是否满足要求 */

int Place(int);

/**//* 非递归的方法求取皇后放置方案 */

void Queen2(void);

/**//* 打印当前成功的放置方案 */

void PrintMethod(void);

void main(void)

{

long start,stop;

printf("input n: ");

scanf("%d",&n);

x=(int *)malloc(sizeof(int)*n);

time(&start);/**//*记录开始时间*/

Queen2();

time(&stop);/**//*记录结束时间*/

printf("\nmethod total %d \n",sum);

printf("\nuse %d seconds \n",(int)(stop-start));

}

int Place(int r)

{

int i;

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

{

if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))

return 0;

}

return 1;

}

void Queen2(void)

{

int i,k;

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

x[i]=0;

k=0;

while(1)

{

if(x[k]>=n)

{

/**//* 如果当前第K行的放置位置超出了范围，那么检查该行是否为第0行

如果是第0行，说明所有的方案都已经遍历完毕，函数返回；否则回退到前一行

if(k==0) break;

x[k]=0; /**//* 下次遍历的初始位置 */

k--; /**//* 返回上一行 */

x[k]++; /**//*下一种放置方案*/

}

else if(!Place(k))

{

/**//* 如果当前第K行的放置方案不满足要求，采取下一种放置方案*/

x[k]++;

}

else

{

if(k==(n-1))

{

/**//* 如果已经是最后一行，那么表示已经成功得到一种放置方案*/

sum++;

/**//* PrintMethod(); */

x[k]=0; /**//*下次遍历的初始位置*/

k--; /**//*返回上一行*/

x[k]++; /**//*下一种放置方案*/

}else

k++; /**//* 否则开始配置下一行的皇后 */

}

void PrintMethod(void)

{

int i,j;

printf("\nmethod %d\n",sum);

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

{

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

{

if(j==x[i]) printf("*");

else printf("#");

}

printf("\n");

}

#include<iostream>
#include<cmath>
using namespace std;

int x[9];
void print(){
        for(int i = 1; i <= 8; i++)
                   cout << x[i] << " ";
        cout << endl;
}

bool canPlace(int k){
        for(int i = 1; i < k; i++){
            //判断处于同一列或同一斜线
           if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i])) 
                   return false;
        }
        return true;
}

void queen(int i){
        if(i > 8){
                print();
                return;
        }
        for(int j = 1; j <= 8; j++){
          x[i] = j;
          if(canPlace(i)) queen(i+1);
        }
}

int main(){
  queen(1);
  return 0;
}

回溯 转载

转载自http://fuliang.javaeye.com/blog/164686和http://fuliang.javaeye.com/blog/164744

回溯法之一---算法框架及基础

回溯法之二---8皇后问题

回溯转载