搜索问题总结

diggersun

一、两种题型：
   1.简明的数学模型揭示问题本质。对于这一类试题，我们  尽量用解析法求解。
   2.对给定的问题建立数学模型，或即使有一定的数学模型，但采用数学方法解决有一定困难。对于这一类试题，我们只好用模拟或搜索求解。
二、搜索的本质：
    搜索的本质就是逐步试探，在试探过程中找到问题的解。
三、搜索问题考察的范围
  1.算法的实现能力
  2.优化算法的能力
四、经典例题
1、M个数字中选N个
2、8皇后问题
3、01背包的回溯解法
4、间隔排列
5、1*2骨牌覆盖
6、2的N次方最少要算多少次 BFS和DFS两种
7、生日蛋糕
8、埃及分数
9、8数码问题
10、magic魔板
11、老鼠迷宫
12、马的周游
13、[L,R]中约数最多的是哪个数
14、N枚硬币，正面朝上，每次可以把N-1枚翻面，最少几次全部反过来

15、 N张邮票，有多少种形状

16、 迷宫，最少转弯次数

17、中国盒子


五、解题框架
1、状态如何表示
2、综合数据库如何设计
3、BFS or DFS
4、规则如何表示，约束条件是什么
5、终止条件
6、alpha beta剪枝
7、其他优化
六、BFS框架
七、DFS框架
八、显示图的搜索与产生式系统，尽量用前者
九、增强部分

1、 有的深搜深度固定，有的不固定，有的是递减

2、 递归和非递归的深搜

3、 递归带参数的设计

4、 搜索对象和策略的选取

5、 深搜空间小，速度略慢，广搜速度快，空间需求大。

6、 框架都好写，主要考优化

7、 深搜：alpha beta剪枝

8、 广搜  启发式，双向，状态存储时的优化