文档介绍：搜索方法及竞赛题目讲解
彭超
状态空间搜索
搜索被称为“通用解题法”,在算法中占有重要的地位。
有巨大的局限性和自身的灵活性。
首先建立“状态空间”然后“盲目”搜索。常用方法:深度优先搜索,广度优先搜索,双向广度优先搜索,迭代加深,…
优化策略:剪枝、启发式、…
状态空间
状态:问题在某一时刻进展状况的数学描述。
状态转移:问题从一种状态到另一种或几种状态的操作。
状态空间:一个“图”,图结点对应于状态,点之间的边对应于状态转移。
搜索:寻找一种可行的操作序列,从起始状态经过一系列状态转移,达到目标状态。
例:过河问题
某人要带一条狗、一只鸡、一箩米过河,但小船除需要人划外,最多只能载一物过河,而当人不在场时,狗要咬鸡、鸡要吃米。问此人应如何过河?
例:过河问题
状态:建立四元组(人,狗,鸡,米)。用0表示在左岸,1表示在右岸。
起始状态(0,0,0,0),终止状态(1,1,1,1)
状态转移规则:
(a,b,c,d) →(1-a,1-b,c,d)(当a=b)
→(1-a,b,1-c,d)(当a=c)
→(1-a,b,c,1-d)(当a=d)
→(1-a,b,c,d)
约束:(a,b,c,d)中,当a≠b时b≠c;当a≠c时c≠d
例:过河问题
搜索:
(0,0,0,0) →(1,1,0,0)
→(1,0,1,0) →(0,0,1,0) →(1,0,1,1)
→(1,0,0,1) →(1,1,1,0)
→(1,0,0,0)
例:过河问题
搜索:
→(1,0,1,1) →(0,0,0,1)→(1,1,0,1)→(0,1,0,1) →(1,1,1,1)ok
→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)
→(0,0,1,1)
→(1,1,1,0) →(0,0,1,0)→(1,0,1,1)→(0,0,1,1)
→(0,1,0,0)→(1,1,0,1)→(0,1,0,1) →(1,1,1,1)ok
→(0,1,1,0)
例:过河问题
搜索在“图”中进行,但图不需要事先建立(“隐式图”)。
搜索过程就是对图的遍历过程,可以得到一棵“搜索树”。
搜索树的结点个数、分枝数、深度,决定着搜索的效率。
例:过河问题
搜索树
过河问题的程序实现
普通状态可以用4个整数表示
压缩状态用4个bit表示(char型有8个bit,足够用)。
用深度优先(DFS, Depth First Search)或广度优先(BFS, Breath First Search)。