1.8　试探算法思想

试探法也称为回溯法，它是一种系统地搜索问题解的方法，该算法设计思想适用范围相当广泛。例如，在棋手思考下一步该走哪里时，就是采用试探法：首先试想下一步所下的位置，计算对手的应对，再计算自己的应对，若对手的应对于我不利，则取消该下一步设想，然后重新计算另一个下一步的位置。这就是一步试探法。当然，下棋时如果只考虑一步肯定是不行的，随着棋力的增加，棋手可考虑后面几步的应对。

1.8.1　算法思路

试探法是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，但可以利用试探的技术求解。试探法是搜索算法中的一种控制策略。它的基本思想是：从问题的某一种状态（一般是默认的初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候，先退几步，接着从另一种可能的“状态”出发，继续搜索，直到所有的“路径”都尝试过。

编程经验　对于常见的迷宫问题，就可使用试探法来求解，具体过程为：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其他方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其他方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断试探、回溯、再搜索，直到找到新的出路或从原路返回入口处无解为止。

一般的递归试探算法的C语言伪代码如下。

提示　试探算法一般也采用递归形式编写程序。

---

对解集合中的各解进行试探
{
    if (满足条件)
    {
        保存结果
        if (完成集合中所有解的试探) 
            输出解
        else 
            重复本过程进行下一步的试探(递归调用本函数)
    }else
        恢复至上一步保存结果之前的状态, 进行另一步试探(递归调用本函数)
}

---

1.8.2　实例：生成彩票号码组合

常见的彩票号码都是由一些数字组成的，生成彩票号码其实就是将所有数字进行不同的组合。例如，假设有一种彩票，每注由7个1~29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。

解决这个问题，首先想到的是编写一个循环嵌套程序，【程序1-10】即按这种方法来编写。

【程序1-10】使用循环嵌套生成彩票组合

---

1    #include <stdio.h>
2    void main()
3    {
4        int i[7],j;                       //声明变量,数组i[7]用来保存生成的7个号码
5        for(i[0]=1;i[0]<=29;i[0]++)    //使用多次嵌套循环来生成7个号码
6            for(i[1]=1;i[1]<=29;i[1]++)
7            {
8                if(i[0]==i[1]) continue;
9                for(i[2]=1;i[2]<=29;i[2]++)
10                {
11                    if(i[0]==i[2] || i[1]==i[2]) continue;
12                        for(i[3]=1;i[3]<=29;i[3]++)
13                        {
14                            if(i[0]==i[3] || i[1]==i[3] || 
15                                i[2]==i[3]) continue;
16                            for(i[4]=1;i[4]<=29;i[4]++)
17                            {
18                                if(i[0]==i[4] || i[1]==i[4] || 
19                                    i[2]==i[4] || i[3]==i[4]) continue;
20                                for(i[5]=1;i[5]<=29;i[5]++)
21                                {
22                                    if(i[0]==i[5] || i[1]==i[5]  || 
23                                        i[2]==i[5] || i[3]==i[5] || 
24                                        i[4]==i[5]) continue;
25                                    for(i[6]=1;i[6]<=29;i[6]++)
26                                    {
27                                        if(i[0]==i[6] || i[1]==i[6]  || 
28                                            i[2]==i[6] || i[3]==i[6] || 
29                                            i[4]==i[6] || i[5]==i[6]) continue;
30                                        for(j=0;j<7;j++)
31                                            printf("%3d",i[j]);
32                                        printf("\n");
33                                        getch();
34                                    }
35                                }
36                            }
37                        }
38                    }
39            }
40    }

---

【程序说明】

以上程序中，使用循环分别生成彩票中的7位数，数组i[7]中的每一个元素表示一位。因为要求生成的号码中各位数字不能重复，因此需在循环中判断各位是否相等，如第8行、第11行、第14~15行等。

编译执行以上程序，按空格键将逐个生成号码，如图1-15所示。图中椭圆圈出部分是演示最后一位数到达29后，第6位和第7位数的变化情况。

图1-15　【程序1-10】执行结果

编程谬误　从上例代码可看出，该程序代码很烦琐，且程序不具有通用性。例如，要将程序改为生成5位数的不同组合，就需要删除其中的两层循环。

其实，解决这类问题更好的办法是使用试探法，逐步计算出所有可能的组合。首先，可按如下顺序生成彩票号码：

29　28　27　26　25　24　23

29　28　27　26　25　24　22

29　28　27　26　25　24　21

……

29　28　27　26　25　24　1

29　28　27　26　25　23　22

……

从上面列出的号码顺序可看出，生成彩票号码组合时，首先变化最后一位数（第7位），当最后一位数为1时，将回溯计算倒数第二位数（第6位），使该位减少1，然后再变化最后一位数（第7位），通过这样的递归调用，即可生成所有的号码组合。

如果只需要生成5位数的彩票号码，则从第5位开始变化即可，当第5位数为1时，再回溯计算第4位数，使该位数减少1。

按这种方法编写的程序代码如下：

【程序1-11】用试探法生成彩票组合

---

1    #include <stdio.h>
2    #define MAXN 7                     //设置每一注彩票的位数 
3    #define NUM 29                     //设置组成彩票的数字 
4    int num[NUM];
5    int lottery[MAXN];
6    void combine(int n, int m)
7    {
8         int i,j;                        //声明变量
9         for(i=n;i>=m;i--)
10         {
11             lottery[m-1]=num[i-1];        //保存一位数字 
12             if (m>1)
13                 combine(i-1,m-1);         //递归
14             else                            //若m=1,输出一注号码 
15             {
16                 for(j=MAXN-1;j>=0;j--)
17                     printf("%3d",lottery[j]);
18                 getch();
19                 printf("\n");
20             }
21         }
22    }
23    int main()
24    {
25        int i,j;
26        for(i=0;i<NUM;i++)                //设置彩票各位数字 
27            num[i]=i+1;
28        for(i=0;i<MAXN;i++)
29            lottery[i]=0;
30        combine(NUM,MAXN);                 //递归
31        getch();
32        return 0;
33    }

---

【程序说明】

·第6~22行为一个递归函数，用来生成彩票组合。若还未生成足够的位数，则执行第13行递归调用生成下一位号码。当生成完指定位数的号码后，执行第14~20行输出该注彩票号码。其中第18行是为了便于用户查看而添加的。

·第23~33行为主函数，用来初始化各数组的值，第30行调用递归函数combine生成彩票号码。

·编译执行以上程序，按空格键将逐个生成号码，如图1-16所示。图中椭圆圈出部分是演示最后一位数到达1后，第6位和第7位数的变化情况。

图1-16　【程序1-11】执行结果