注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

不透明的雾的博客

人生是一次记忆的旅行

 
 
 

日志

 
 
 
 

穷举搜索::回溯与深搜  

2009-09-01 13:18:08|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

【建立解空间】
问题的解应该如何描述,如何建立?借助图论的思想,我们可以用图来描述,图的定义为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 100int 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;            }        }    }}int main(){    scanf("%d",&n);    dfs(0);    printf("total:%d\n",count);    return 0;}
  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017