算法的优雅(八):众里寻TA千百度

ひとつ.如果你是个算法高手,请移步.....
ふたつ.如果你擅长搜索算法,请移步.....
みっつ.如果你是找人而在百度搜到这个文章的话,请移步......

作为一个万金油算法,可以应付所有问题了,当然,很多问题上时间复杂度是个问题......不够,在很多面试的时候,面试官只需要你一个思路而已,而且工作也不是搞ACM,对时间限制也不是很严格,所以,如果暂时没有思路,可以用搜索对付一下。

那么,具体起来,搜索是什么呢?

来个例子,我们有一个1元,一个2元,一个3元,一个4元,一个5元......于是,我们能有多少种组合呢?

从1元开始看,我们有两种选择,取或不取,加入,我们取,于是到了2元,还是两个选择,取或不取......于是一路下来,加入我们都取,于是有了1+2+3+4+5......这就是搜索出来的一个状态,之后,我们在5元能选择不取,于是1+2+3+4,这就是另一个状态,而这些状态就像一棵二叉树,我们搜索的结果就是根节点到叶子节点的路径。


算法的优雅(八):众里寻TA千百度_第1张图片

于是.....这就是我们对搜索的初步了解.....很多问题都能转换成取或不取之类的模型,这样就能搜索做了.....不过我们能看出这个复杂度是指数级别的,所以.....慎用......


搜索分为两大类:深度优先搜索和宽度优先搜素。


深度优先搜索(DFS):

如上图,我们可以看出来,搜索的模型是一棵树,每次选定一个路径走到叶子节点,就是深度优先搜索。

具体实现方法:

(1)访问顶点v;
(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 


宽度优先搜索(BFS):

看了上面的深度优先搜索,没有想到什么么?迷宫!人们一开始将深度优先搜索用来迷宫上去寻找出路,不过很快就有人发现这种方法太靠人品了,于是,一些人开始想,我能不能先把每一步的所有结果找出来,这样一步步逼近,于是宽度优先搜索诞生了。

每次把同一层的状态都搜索完,之后进入下一次,这就是宽度优先搜索和深度优先搜索的区别。


但是,我们可以看出,一棵树状态很多,时间复杂度很大.....所以,我们需要一个东西——剪枝——很形象的一个词哈~

剪枝,就是如果一个状态不满足你题目要求,那么其下面的子状态也是不符合的了,可以删除掉不要了,这样可以缩短一些时间,就像树上出现了不需要的枝叶,之后一剪子没了....


于是,我们对搜索有了初步的了解,那么,就要开始运用了。

POJ 1081 http://poj.org/problem?id=1081

首先....说一下这个题内容,就是有N个人,他们的互相是否认识给出了,要求分成两个班,如果一个班里存在一对不认识的,那么其中一个人可以花费1分钟去认识剩下所有人......很乱.....于是,问你怎么分班可以让花费的时间最少......

题目里N最下64,可是....数据很弱,大家完全可以搜索过.....因为我全排列代码跑了0MS.....

对于N个人,枚举状态,一班,或二班,这样每搜索出一个状态就有一个时间花费,取最小的就是结果。


POJ 1011 http://poj.org/problem?id=1011

很神奇的一个题,给出了一些木棍长度,那些木棍是由若干长度一样的木管断成的,求出可能最短的长度,

例如样例5 2 1 5 2 1 5 2 1,可以组成6 6 6,也能组成12 12,但要求最短,就是6了。

令InitLen为所求的最短原始棒长,maxlen为给定的棒子堆中最长的棒子,sumlen为这堆棒子的长度之和,那么InitLen必定在范围[maxlen,sumlen]中。
根据棒子的灵活度(棒子越长,灵活度越低) DFS前先对所有棒子降序排序。

但是,即使这样还是会AC不了.....因为有个错误叫TLE....超时......所以,这个题还有另一个考察点,剪枝。

1、  由于所有原始棒子等长,那么必有sumlen%Initlen==0;
2、  若能在[maxlen,sumlen-InitLen]找到最短的InitLen,该InitLen必也是[maxlen,sumlen]的最短;若不能在[maxlen,sumlen-InitLen]找到最短的InitLen,则必有InitLen=sumlen;
3、  由于所有棒子已降序排序,在DFS时,若某根棒子不合适,则跳过其后面所有与它等长的棒子;
4、  最重要的剪枝:对于某个目标InitLen,在每次构建新的长度为InitLen的原始棒时,检查新棒的第一根stick[i],若在搜索完所有stick[]后都无法组合,则说明stick[i]无法在当前组合方式下组合,不用往下搜索(往下搜索会令stick[i]被舍弃),直接返回上一层;


搜索是一个很常见的算法,也是面试中很好用的万金油算法,so....知道一点总不是坏处。

你可能感兴趣的