计算机常用算法大致有两大类，一类叫蛮干算法，一类叫贪心算法，前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。

【建立解空间】
问题的解应该如何描述，如何建立？借助图论的思想，我们可以用图来描述，图的定义为G<V,E>，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。描述了解，那如何建立解空间，即如何对图进行搜索？

【深度优先搜索】
(Depth First Search)是用栈的机制对图的顶点进行深度优先的搜索。简易流程如下：

DFS(V0（起始顶点）)
访问V0
for(v=V0的第一个子结点 到 最后一个子结点（边所对的顶点））
  如果v未被访问，DFS(v);

搜索过程是先往结点深处搜索，一旦有子结点未访问就向下遍历。这样的方法类似回溯算法，先往下试探，如果不行出退回（回溯）。

【回溯】
回溯的经典例子是8皇后问题。
例：在国际象棋地图上（8×8）放上8个皇后，使任意两个皇后都不在同一行或同一列或同一斜行，找出所有解。
每一个皇后的位置可以认为是一个顶点，而皇后之间不在同一行或同一列或同一斜行的性质认为是顶点之间的关系，我们可以用回溯试探的方法考虑：先依次试探每一个皇后的位置，如果有不满足条件的情况则退回，直到完成所有解的计数和输出。

用数组存储：int pos[8];
pos[0]表示第一个皇后的位置（0,1,...7)依次类推。
流程：
dfs(c)//c从0开始
for(v=0;v<8;++v)
  如果pos[c]:=v满足条件，dfs(c+1);
  退回之后pos[c]:=0;

这跟书上的回溯算法不太一样，因为是采用深搜的方法写的，其实思想是一致的，要仔细体会。

附N皇后C语言代码：
/*p118.4*/
/*N Queen Problem*/
#include<stdio.h>
#define MAX 100
int s[MAX];
int n;
int m1[MAX],m2[MAX],m3[MAX];
long count=0;
void output_solution()
{
    int i,j;
    printf("No.%d\n",++count);
    for(i=0;i<n;++i)
    {
 for(j=0;j<s[i];++j)printf(" ");
 printf("Q\n");
    }
    printf("---------------\n");
}
void dfs(int c)
{
    int i;
    if(c==n)
    {
 /*output_solution();*/
 ++count;
    }
    else
    {
 for(i=0;i<n;++i)
 {
      if(m1[i]==0&&m2[c+i]==0&&m3[n+i-c-1]==0)
      {
    s[c]=i;
    m1[i]=1;
    m2[c+i]=1;
    m3[n+i-c-1]=1;
    dfs(c+1);
    m1[i]=0;
    m2[c+i]=0;
    m3[n+i-c-1]=0;
      }
 }
    }
}
void main()
{
    scanf("%d",&n);
    dfs(0);
    printf("total:%d\n",count);
}

评论