经典算法学习之回溯法

回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。 

若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

回溯法将问题的候选解按照某一顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解,若当前候选解符合要求,且还未达到求解的规模,则继续扩展当前候

选解的规模,如果候选解已经满足了所有要求,并且也达到了问题的规模,那么该候选解就是问题的一个解。

 例、在9(3*3)的方格内填入1到N(N>=10)内的某9个数字,每个方格填入一个数字,使方格内所有相邻的两个数的和为质数,试求出满足要求的所有填法。

伪代码:

 1 int m=0;       //已经填入m个数
 2 bool ok=true;//ture表示已经填入的前m个数都符合要求
 3 int n=8;      //填入最后一个数字的下标
 4 do
 5 {
 6     if(ok)
 7     {
 8         if(m==n)
 9         {
10             print();//输出这个解
11             change();//调整最后一个值,找下一个解
12         }
13         else
14         {
15             extend();//往下一个空的方格中填入数字
16         }
17     }
18     else
19     {
20         change();//调整最近填入的一个值
21     }
22     ok=检查前m个数是否都符合要求;
23 }while(m>=0)//由于是求解所有解,所以必须回溯到根的所有情况才算结束

程序如下:

  1 #include<iostream>
  2 #include<math.h>
  3 using namespace std;
  4 const int N=12;
  5 int a[10];//记录符合条件的数
  6 bool b[N+1];//记录某个数是否已经被用过true,被用过,false,没被用过
  7 int checkmatrix[][3]={{-1},{0,-1},{1,-1},
  8                       {0,-1},{3,1,-1},{4,2,-1},
  9                       {3,-1},{6,4,-1},{7,5,-1}};//checkmatirx用来验证相邻的两个数的和是否为指数用的,-1是人为添加的截止符号
 10 int m;//已经符合条件的个数
 11 void print(int * a)
 12 {
 13     for(int i=0;i<3;i++)
 14     {
 15         for(int j=0;j<3;j++)
 16         {
 17             cout<<a[i+j*3]<<" ";
 18         }
 19         cout<<endl;
 20     }
 21 }
 22 bool isprime(int m)
 23 {
 24     if(1==m)
 25     {
 26         return false;
 27     }
 28     if(2==m)
 29     {
 30         return true;
 31     }
 32     int n=sqrt((float)m);
 33     for(int i=2;i<=n;i++)
 34     {
 35         if(m%i==0)
 36         {
 37             return false;
 38         }
 39     }
 40     return true;
 41 }
 42 //返回从start开始的第一个没被用过的数
 43 int select(int start)
 44 {
 45     for(int i=start;i<=N;i++)
 46     {
 47         if(b[i]==false)
 48         {
 49             return i;
 50         }
 51     }
 52     return 0;//如果全都被使用过了就返回0 
 53 }
 54 int extend(int m)
 55 {
 56     a[++m]=select(1);
 57     b[a[m]]=true;
 58     return m;
 59 }
 60 int change(int m)
 61 {
 62     int pos;
 63     while(m>=0 && (pos=select(a[m]+1))==0)
 64     {
 65         b[a[m--]]=false;
 66     }
 67     if(m<0)
 68     {
 69         return -1;
 70     }
 71     else
 72     {
 73         b[a[m]]=false;
 74         a[m]=pos;
 75         b[a[m]]=true;
 76     }
 77     return m;
 78 }
 79 bool check(int m)
 80 {
 81     int j;
 82     if(m<0)
 83     {
 84         return false;
 85     }
 86     int k=m;
 87     while(k>=0)
 88     {
 89         for(int i=0;(j=checkmatrix[k][i])>=0;i++)
 90         {
 91             if(!isprime(a[k]+j))
 92             {
 93                 return false;
 94             }
 95         }
 96         k--;
 97     }
 98 
 99     return true;
100 }
101 int main()
102 {
103     //先全都初始化为未使用过
104     for(int i=0;i<N+1;i++)
105     {
106         b[i]=false;
107     }
108     m=0;
109     a[m]=1;
110     b[a[m]]=true;
111     bool ok=true;//前m个数都满足条件的话ok为true否则为false
112     do
113     {
114         if(ok)
115         {
116             if(8==m)
117             {
118                 print(a);
119                 //调整
120                 m=change(m);
121 
122             }
123             else
124             {
125                 //扩展
126                 m=extend(m);
127             }
128         }
129         else
130         {
131             //调整
132             m=change(m);
133         }
134         //检查前m个数是否都满足条件
135         ok=check(m);
136     }while(m>=0);
137 
138     return 0;
139 }

如果将题目改成找出一种填法,则不需要回溯到根,而是找到一个解就可以结束了 伪代码如下:

 1 int m=0;
 2 bool ok=true;
 3 int n=8;
 4 do
 5 {
 6     if(ok)
 7     {
 8          extend()//扩展解
 9     }
10     else
11     {
12          change();//调整最近填入的数字
13     }
14     ok=检查填入的m个数的合理性;
15 }while((m!=n||!ok)&&m!=0)
16 if(m==n)
17 {
18     print();//输出解
19 }
20 else
21 {
22     无解;
23 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mwangblog

整数的存储:符号加绝对值表示法

1232
来自专栏王亚昌的专栏

A*算法C实现

参考 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html 实现了A*算法,模拟了一下,...

952
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1213
来自专栏小樱的经验随笔

hihoCoder #1142 : 三分求极值

#1142 : 三分·三分求极值 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 这一次我们就简单一点了,题目在此: ? 在直...

3499
来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

3828
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

1231
来自专栏瓜大三哥

视频压缩编码技术(H.264) 之算术编码

早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对芯源的编码,并从理论上论证了它的优越性。1960年, Peter E...

1163
来自专栏深度学习之tensorflow实战篇

tensorflow载入数据的三种方式 之 TF生成数据的方法

Tensorflow数据读取有三种方式: Preloaded data: 预加载数据 Feeding: Python产生数据,再把数据喂给后端。 Reading...

4164
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

2848
来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

1.3K8

扫码关注云+社区

领取腾讯云代金券