回溯法子集树和排序树-白红宇

回溯法子集树和排序树

阅读量：6239 次

发布时间：2019-06-22

本文共 3211 字，大约阅读时间需要 10 分钟。

当所给问题是从n个元素的集合S中找出满足某种性质的子集时，解空间为

子集树。例如：

0-1背包问题

当所给问题是从n个元素的集合S中找出满足某种性质的排列时，解空间为

排列树。例如：

旅行售货员问题

回溯法搜索子集树算法描述为：

void backtrack(int t)

{

if(t>n)

output(x);

else

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

//注意，这里的0,1 是X[i]的取值范围，t表示层数

{

x[t] = i;

if(constraint(t) && bound(t))

backtrack(t+1);

}

回溯法搜索排列树的描述为：

void backtrack(int t)

{

if(t>n)

output(x);

else

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

//这里的n表示层数，不要和子集树搞混了

{

swap(x[t], x[i]);

if(constraint(t) && bound(t)) backtrack(t+1);

swap(x[t], x[i]);

}

具体实例：

#include

#define N 3

int x[N+1];

void Backtrace(int t)

{

if(t>N)

{

for(int i=1;i<=N;i++)

{

printf("%d ",x[i]);

}

printf("\n");

}

else

{

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

{

x[t]=i;

Backtrace(t+1);

}

int main()

{

memset(x,0,(N+1)*sizeof(int));

Backtrace(1);

}

--------------------------------------------------------------------------------------------------

#include

#define N 3

int x[N+1]={0,1,2,3};

void swap(int &a,int &b)

{

int temp=a;

a=b;

b=temp;

}

void Backtrace(int t)

{

if(t>N)

{

for(int i=1;i<=N;i++)

{

printf("%d ",x[i]);

}

printf("\n");

}

else

{

for(int i=t;i<=N;i++)

{

swap(x[t],x[i]);

Backtrace(t+1);

swap(x[t],x[i]);

}

int main()

{

Backtrace(1);

}

子集树实例：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 9 void printVector(vector
            
              array );10 11 void dfs(vector
             
              & array, int dep)12 {13 int size = array.size();14 if(dep == size)15 {16 printVector(array);17 return;18 }19 //dfs to the next level20 for(int i = 0; i < 2; i++)21 {22 array[dep] = i;23 dfs(array, dep+1);24 }25 26 }27 28 29 void printVector(vector
              
                array )30 {31 for(int i = 0; i

b ;39 b.resize(5, 0);40 dfs(b, 0);41 42 return 0;43 }

打印结果：

0 0 0 0 0

0 0 0 0 1

0 0 0 1 0

0 0 0 1 1

0 0 1 0 0

0 0 1 0 1

0 0 1 1 0

0 0 1 1 1

0 1 0 0 0

0 1 0 0 1

0 1 0 1 0

0 1 0 1 1

0 1 1 0 0

0 1 1 0 1

0 1 1 1 0

0 1 1 1 1

1 0 0 0 0

1 0 0 0 1

1 0 0 1 0

1 0 0 1 1

1 0 1 0 0

1 0 1 0 1

1 0 1 1 0

1 0 1 1 1

1 1 0 0 0

1 1 0 0 1

1 1 0 1 0

1 1 0 1 1

1 1 1 0 0

1 1 1 0 1

1 1 1 1 0

1 1 1 1 1

排序树实例：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 9 void printVector(vector
            
              array );10 11 int dfs(vector
             
              & array, int t)12 {13 size_t size = array.size();14 if(t == size)15 printVector(array);16 17 //dfs to the next level18 for(int i = t; i < size; i++)19 {20 int j = i;21 string s;22 while(j --)23 s += "\t" ;24 //cout <
              << "================ start ==================================;; i =" <<< endl;25 swap(array[t],array[i]);26 //cout <<< "begin to swap " << array[i]<< " and " << array[t] <

b ;48 #if 149 b.push_back(5);50 b.push_back(6);51 b.push_back(7);52 b.push_back(8);53 #else54 b.push_back(4);55 b.push_back(3);56 b.push_back(2);57 b.push_back(1);58 b.push_back(0);59 #endif60 61 sort(b.begin(), b.end());62 dfs(b, 0);63 64 return 0;65 }

打印结果

5 6 7 8

5 6 8 7

5 7 6 8

5 7 8 6

5 8 7 6

5 8 6 7

6 5 7 8

6 5 8 7

6 7 5 8

6 7 8 5

6 8 7 5

6 8 5 7

7 6 5 8

7 6 8 5

7 5 6 8

7 5 8 6

7 8 5 6

7 8 6 5

8 6 7 5

8 6 5 7

8 7 6 5

8 7 5 6

8 5 7 6

8 5 6 7

从结果看，回溯法排序树并不满足 permutation_sequence 的要求。。

递归分析：

转载地址：http://kjdia.baihongyu.com/