C 搜索入门.ppt

搜索专题
搜索
搜索算法:
是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法。
搜索树:
根据初始条件和扩展规则所构造成的一棵树称为搜索树,搜索算法就是在搜索树中寻找符合目标状态的节点的过程。
搜索算法分类
枚举
回溯法
深度优先搜索
广度优先搜索
。。。
枚举算法
枚举算法
即列举问题的所有状态从而寻找符合问题的解的方法。
适合用于状态较少,比较简单的问题上。
例如:
【百钱买百鸡】
公鸡5文钱一只,母鸡3文钱一只,小鸡3只一文钱,用100文钱买一百只鸡,其中公鸡,母鸡,小鸡都必须要有,问公鸡,母鸡,小鸡要买多少只刚好凑足100文钱。
【砝码称重】
给你若干个1g、2g、5g、10g、20g、50g的砝码,数量分别为a[1]a[2]…a[6],问这些砝码可以称出多少种重量(重量大于0,小于等于1000)。
二、数据结构之搜索
2、搜索算法的分类
在我们的数据结构中搜索分为两大类:深度优先搜索(DFS)和广度优先搜索(BFS)
(1)深度搜索:按照深度优先的顺序遍历状态空间,通常用递归或者栈来实现。
(2)广度搜索:如果代价和搜索树深度成正比,那么可以通过广度优先搜索得到解。由于空间占用大,BFS用处不是很广,一般只用在路径寻找问题中,但是一旦使用,将比深度优先搜括看得多。深度优先搜索往往使用队列来实现。
以上两种搜索方式是必须要掌握的,但是要想在比赛中有所造诣那么必须还要了解下面几种方式: 纯随机搜索、重复式搜索、迭代加深搜索、迭代加宽搜索、柱型搜索
二、数据结构之搜索
3、深度优先搜索(DFS)
算法描述:按照深度优先的顺序遍历状态空间,通常用递归或者栈来实现。
说白了就是往深里搜,当某个结点的所有子节点都搜索过了就返回父结点继续进行。
就像走迷宫,你没有办法用分身术来站在每个走过的位置。不撞南山不回头。
二、数据结构之搜索
3、深度优先搜索(DFS)
(1)一般形式:
void dfs ( state , depth ){
if ( state == 结束状态)退出;
枚举所有可行状态{
更新全局变量;
dfs( newstate , depth + 1 );
还原全局变量;也叫还原现场
}
}
但凡使用深度搜索的题目大都是上面的这个模式,但不会这么简单的,往往是需要我们加入一些判定条件。我们来仔细看上面的这个函数,大家是不是感觉跟我们前面的递归很相似?首先就是结束条件然后就是自己调用自己。
二、数据结构之搜索
(2)迷宫问题
寻找一条从入口到出口的通路
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
入口
出口
二、数据结构之搜索
前进方向:上(北)、下(南)、左(西)、右(东)
东
南
西(左)
首先从下方开始,按照逆时针方向搜索下一步可能前进的位置
二、数据结构之搜索
入口
出口
在迷宫周围加墙,避免判断是否出界
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
二、数据结构之搜索
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
在寻找出口的过程中,每前进一步,当前位置入栈;每回退一步,栈顶元素出栈
栈
(1,1)