搜索与回溯算法ppt课件.ppt

第五章搜索与回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。递归回溯法算法框架[一]
intSearch(intk)
{
for(i=1;i<=算符种数;i++)
if(满足条件)
{
保存结果
if(到目的地)输出解;
elseSearch(k+1);
恢复：保存结果之前的状态{回溯一步}
}
}
递归回溯法算法框架[二]
intSearch(intk)
{
if(到目的地)输出解;
else
for(i=1;i<=算符种数;i++)
if(满足条件)
{
保存结果;
Search(k+1);
恢复：保存结果之前的状态{回溯一步}
}
}【例1】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
【算法分析】
非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。
【算法流程】
1、数据初始化；2、递归填数：判断第i个数填入是否合法；
A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；
B、如果不合法：选择下一种可能；
【参考程序】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
usingnamespacestd;
boolb[21]={0};
inttotal=0,a[21]={0};
intsearch(int);//回溯过程
intprint();//输出方案
boolpd(int,int);//判断素数
intmain()
{
search(1);
cout<<total<<endl;//输出总方案数
system("pause");
}
intsearch(intt)
{
inti;
for(i=1;i<=20;i++)//有20个数可选
if(pd(a[t-1],i)&&(!b[i]))//判断与前一个数是否构成素数及该数是否可用
{
a[t]=i;
b[i]=1;
if(t==20){if(pd(a[20],a[1]))print();}
elsesearch(t+1);
b[i]=0;
}
}
intprint()
{
total++;
cout<<"<"<<total<<">";
for(intj=1;j<=20;j++)
cout<<a[j]<<"";
cout<<endl;
}
boolpd(intx,inty)
{
intk=2,i=x+y;
while(k<=sqrt(i)&&i%k!=0)k++;
if(k>sqrt(i))return1;
elsereturn0;
}【例2】设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数进行排列（r<n），试列出所有的排列。
#include<cstdio>
#include<iostream>
#include<iomanip>
usingnamespacestd;
intnum=0,a[10001]={0},n,r;
boolb[10001]={0};
intsearch(int);//回溯过程
intprint();//输出方案

intmain()
{
cout<<"inputn,r:";
cin>>n>>r;
search(1);
cout<<"number="<<num<<endl;//输出方案总数
}intsearch(intk)
{
inti;
for(i=1;i<=n;i++)
if(!b[i])//判断i是否可用
{
a[k]=i;//保存结果
b[i]=1;
if(k==r)print();
elsesearch(k+1);
b[i]=0;
}
}
intprint()
{
num++;
for(inti=1;i<=r;i++)
cout<<setw(3)<<a[i];
cout<<endl;
}【例3】任何一个大于1的自然数n，总可以拆分成若干个小于