本文共 5909 字,大约阅读时间需要 19 分钟。
为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。
搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。
如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步步向前试探前进,如果碰到死胡同,说明前进方向已无路可走,这时,首先看其它方向是否还有路可走,如果有路可走,则沿该方向再向前试探;如果已无路可走,则返回一步,再看其它方向是否还有路可走;如果有路可走,则沿该方向再向前试探。按此原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口处无解为止。
递归回溯法算法框架[一]int Search(int k){ for (i=1;i<=算符种数;i++) if (满足条件) { 保存结果 if (到目的地) 输出解; else Search(k+1); 恢复:保存结果之前的状态{ 回溯一步} }}递归回溯法算法框架[二]int Search(int k) { if (到目的地) 输出解; else for (i=1;i<=算符种数;i++) if (满足条件) { 保存结果; Search(k+1); 恢复:保存结果之前的状态{ 回溯一步} } }
【题目】素数环:从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。
【算法分析】 非常明显,这是一道回溯的题目。从1开始,每个空位有20种可能,只要填进去的数合法:与前面的数不相同;与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。 【算法流程】 1、数据初始化; 2、递归填数:判断第i个数填入是否合法; A、如果合法:填数;判断是否到达目标(20个已填完):是,打印结果;不是,递归填下一个; B、如果不合法:选择下一种可能;#include#include #include #include using namespace std;bool b[21]={ 0};int total=0,a[21]={ 0};int search(int); //回溯过程int print(); //输出方案bool pd(int,int); //判断素数int main(){ search(1); cout< < "; for (int j=1;j<=20;j++) cout< <<" "; cout< sqrt(i)) return 1; else return 0;}//最终答案有6309300种方式
【题目】设有n个整数的集合{1,2,…,n},从中取出任意r个数进行排列(r<n),试列出所有的排列。
/**搜索和回溯基本框架search(i){ for(所有算子){ if(条件成立){ 存储结果 if(到达目的地) 输出 else search(i+1) 回溯 } }}*/#include#include #include using namespace std;int num=0,a[10001]= { 0},n,r;bool b[10001]= { 0};int search(int); //回溯过程int print(); //输出方案int main() { cout<<"input n,r:"; cin>>n>>r; search(1); cout<<"number="< <
【题目】任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法: 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 total=14 【参考程序】#include#include #include using namespace std;int a[10001]= { 1},n,total;int search(int,int);//在指定开始位置的数组中存储指定大小的数int print(int);int main() { cin>>n; search(n,1); //将要拆分的数n传递给s cout<<"total="< < 0时,继续递归 s+=i;//回溯:加上拆分的数,以便产分所有可能的拆分 }}int print(int t) { cout< <<"="; for (int i=1; i<=t-1; i++)//输出一种拆分方案 cout< <<"+"; cout< <
【题目】八皇后问题:要在国际象棋棋盘中放八个皇后,使任意两个皇后都不能互相吃。(提示:皇后能吃同一行、同一列、同一对角线的任意棋子。)
放置第i个(行)皇后的算法为: int search(i); { int j; for (第i个皇后的位置j=1;j<=8;j++ ) //在本行的8列中去试 if (本行本列允许放置皇后) { 放置第i个皇后; 对放置皇后的位置进行标记; if (i==8) 输出 //已经放完个皇后 else search(i+1); //放置第i+1个皇后 对放置皇后的位置释放标记,尝试下一个位置是否可行; } } 【算法分析】 显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后;可以从矩阵的特点上找到规律,如果在同一行,则行号相同;如果在同一列上,则列号相同;如果同在/ 斜线上的行列值之和相同;如果同在\ 斜线上的行列值之差相同;从下图可验证: 考虑每行有且仅有一个皇后,设一维数组A[1…8]表示皇后的放置:第i行皇后放在第j列,用A[i]=j来表示,即下标是行数,内容是列数。例如:A[3]=5就表示第3个皇后在第3行第5列上。 判断皇后是否安全,即检查同一列、同一对角线是否已有皇后,建立标志数组b[1…8]控制同一列只能有一个皇后,若两皇后在同一对角线上,则其行列坐标之和或行列坐标之差相等,故亦可建立标志数组c[1…16]、d[-7…7]控制同一对角线上只能有一个皇后。 如果斜线不分方向,则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下,要表示两个皇后I和J不在同一列或斜线上的条件可以描述为:A[I]<>A[J] AND ABS(I-J)<>ABS(A[I]-A[J]){I和J分别表示两个皇后的行号} 【参考程序】#include#include #include #include using namespace std;bool d[100]={ 0},b[100]={ 0},c[100]={ 0};int sum=0,a[100];int search(int);int print();int main(){ search(1); //从第1个皇后开始放置}int search(int i){ int j; for (j=1;j<=8;j++) //每个皇后都有8位置(列)可以试放 if ((!b[j])&&(!c[i+j])&&(!d[i-j+7])) //寻找放置皇后的位置 //由于C++不能操作负数组,因此考虑加7 { //放置皇后,建立相应标志值 a[i]=j; //摆放皇后 b[j]=1; //宣布占领第j列 c[i+j]=1; //占领两个对角线 d[i-j+7]=1; if (i==8) print(); //8个皇后都放置好,输出 else search(i+1); //继续递归放置下一个皇后 b[j]=0; //递归返回即为回溯一步,当前皇后退出 c[i+j]=0; d[i-j+7]=0; }}int print(){ int i; sum++; //方案数累加1 cout<<"sum="< <
马的遍历,中国象棋半张棋盘如图4(a)所示。马自左下角往右上角跳。今规定只许往右跳,不许往左跳。比如图4(a)中所示为一种跳行路线,并将所经路线打印出来。打印格式为:0,0->2,1->3,3->1,4->3,5->2,7->4,8…
【算法分析】 如图4(b),马最多有四个方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为: 1: (i,j)→(i+2,j+1); (i<3,j<8) 2: (i,j)→(i+1,j+2); (i<4,j<7) 3: (i,j)→(i-1,j+2); (i>0,j<7) 4: (i,j)→(i-2,j+1); (i>1,j<8) 搜索策略: S1:A[1]:=(0,0); S2:从A[1]出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下一个到达的顶点; S3:打印路径。#include#include #include using namespace std;int a[100][100],t=0; //路径总数和路径int x[4]={ 2,1,-1,-2}, //四种移动规则y[4]={ 1,2,2,1};int search(int); //搜索 int print(int); //打印int main() //主程序{ a[1][1]=0;a[1][2]=0; //从坐标(0,0)开始往右跳第二步 search(2); }; int search(int i){ for (int j=0;j<=3;j++) //往4个方向跳 if (a[i-1][1]+x[j]>=0&&a[i-1][1]+x[j]<=4 &&a[i-1][2]+y[j]>=0&&a[i-1][2]+y[j]<=8) //判断马不越界 { a[i][1]=a[i-1][1]+x[j]; //保存当前马的位置 a[i][2]=a[i-1][2]+y[j]; if(a[i][1]==4&&a[i][2]==8) print(i); else search(i+1); //搜索下一步 }}int print(int ii){ t++; cout< <<": "; for(int i=1;i<=ii-1;i++) cout< <<","< <<"-->"; cout<<"4,8"<
转载地址:http://zplvn.baihongyu.com/