搜索算法应用案例(1)题目：黑白棋游戏黑白棋游戏的棋盘由4×4方格阵列构成

棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子

这16枚棋子的每一种放置方案都构成一个游戏状态

在棋盘上拥有1条公共边的2个方格称为相邻方格

一个方格最多可有4个相邻方格

在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置

对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列

(2)分析这题我们可以想到用深度优先搜索来做，但是如果下一步出现了以前的状态怎么办？直接判断时间复杂度的可能会有点大，这题的最优解法是用广度优先搜索来做

我们就可以有初始状态按照广度优先搜索遍历来扩展每一个点，这样到达目标状态的步数一定是最优的（步数的增加时单调的）

但问题是如果出现了重复的情况我们就必须要判重，但是朴素的判重是可以达到状态数级别的，其实我们可以考虑用hash表来判重

Hash表：思路是根据关键码值进行直接访问

也就是说把一个关键码值映射到表中的一个位置来访问记录的过程

在Hash表中，一般插入，查找的时间复杂度可以在O（1）的时间复杂度内搞定

对于这一题我们可以用二进制值表示其hash值，最多2^16次方，所以我们开个2^16次方的表记录这个状态出现没有，这样可以在O（1）的时间复杂度内解决判重问题

进一步考虑：从初始状态到目标状态，必定会产生很多无用的状态，那还有什么优化可以减少这时间复杂度？我们可以考虑把初始状态和目标状态一起扩展，这样如果初始状态的某个被扩展的点与目标状态所扩展的点相同时，那这两个点不用扩展下去，而两个扩展的步数和也就是答案

上面的想法是双向广度优先搜索：就像图二一样，多扩展了很多不必要的状态

从上面一题可以看到我们用到了两种优化方法，即Hash表优化和双向广搜优化

一般的广度优先搜索用这两个优化就足以解决

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。