搜索分为广度搜索与深度搜索,不同的题目有不同的解决方法,有的题目两种方法都适用,但是总有一种相对简单,有的时候我们对于使用的方法是可知的,有的时候却是未知的。
看了看例题但仍然不会做,最近事情也好多,好没有精力去投入,要加油啊!
下面是广搜与深搜的模板框架:
广度优先搜索:

While Not Queue.Empty ()
Begin
可加结束条件
Tmp = Queue.Top ()
从Tmp循环拓展下一个状态Next
If 状态Next合法 Then
Begin
生成新状态Next
Next.Step = Tmp.Step + 1 
Queue.Pushback (Next)
End
Queue.Pop ()
End

深度优先搜索:深搜分递归与非递归两种方法:
递归实现:

Function Dfs (Int Step, 当前状态)
Begin
可加结束条件
从当前状态循环拓展下一个状态Next
If 状态Next合法 Then
Dfs (Step + 1, Next ))
End

非递归实现:

While Not Stack.Empty ()
Begin
Tmp = Stack.top()
从Tmp拓展下一个未拓展的状态Next
If 没有未拓展状态(到达叶节点) Then
Stack.pop() 
Else If 状态Next合法 Then
Stack.push(Next)
End

下面写一个深搜递归的例题:
素数环:从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。
这是一道回溯的题目。从1开始,每个空位有20种可能,只要填进去的数合法:与前面的数不相同;与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
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<<total<<endl;                    //输出总方案数
}
int search(int t)
{
    int i;
    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();}
             else search(t+1);
         b[i]=0;
      }
}
int print()
{
   total++;
   cout<<"<"<<total<<">";
   for (int j=1;j<=20;j++)
     cout<<a[j]<<" ";
   cout<<endl; 
  }
bool pd(int x,int y)
{
    int k=2,i=x+y;
    while (k<=sqrt(i)&&i%k!=0) k++;
    if (k>sqrt(i)) return 1;
       else return 0;
}

这道题目(大概以后的题目都是如此,search,printf等函数写到主函数之外,用于实现功能)
这样主函数的功能就很明确了,这有点像类的思想概念,所有功能尽量不使用主函数去调,而是从其他函数中去调用功能。我上次在弄ATM的时候记得就用的大模拟的思路,很多功能都弄到了主函数中(这样的代码就很不愿意让人看,思路虽然没问题,但是显得很乱,以后再做的时候会尽量用这种思路,把功能具体化,分到数据类与操作类中去。)

继续看例题,尽量试着再去做吧。