穷举搜索算法

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

要解决的问题只有有限种可能，在没有更好算法时总可以用穷举搜索的办法解决，即逐个的检查所有可能的情况。可以想象，情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况，常常是可以提前判断出某些情况不可能取到最优解，从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的情况，既减少了搜索量，又保证了不漏掉最优解。

【问题】 将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。

程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的整数，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。

# include <stdio.h>

void main()

{     int a,b,c,d,e,f;

       for (a=1;a<=6;a++)    //a,b,c,d,e依次取不同的值  

              for (b=1;b<=6;b++)              {

                     if (b==a)        continue;

                     for (c=1;c<=6;c++)              {

                            if (c==a)||(c==b)    continue;

                            for (d=1;d<=6;d++)              {

                                   if (d==a)||(d==b)||(d==c)      continue;

for (e=1;e<=6;e++)              {

                                   if (e==a)||(e==b)||(e==c)||(e==d) continue;

f=21-(a+b+c+d+e);//最后一个用减法算

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a))   {

printf(“%6d,a);

       printf(“%4d%4d”,b,f);

       printf(“%2d%4d%4d”,c,d,e);

       scanf(“%c”);

}

                                          }

                                   }

                            }

                     }

              }

按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形，每条边有4个变量的情况，程序的循环重数就要相应改变，循环的重数和变量的个数相关。

从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下