深度、广度和双向搜索优化及其应用

1、 ABCD E FGHI的每个元素是一个动作(action)的集合Fn将初态S0变换为另一个状态F(S0)nF中各动作的执行顺序不影响F(S0)n如果F(S0)是符合要求的S*, 那么F是真解, 否则是伪解nBool Dfs(int nUnusedSticks, int nLeft ) ;nFunction dfs(nUnusedSticks:longint, nLeft:longint):longintn 表示: 当前有nUnusedSticks根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度短了nLeft, 那么在这种情况下能否全部拼成功。nboolDfs(int nUnusedSti

2、cks, int nLeft) n.n if( nLeft = 0 ) /一根刚刚拼完nnLeft := L; /开始拼新的一根n找一根长度不超过nLeft的木棒（假设长为len）拼在当前棍子上，然后nexit Dfs(nUnusedSticks 1, nLeft len );nnboolDfs(int nUnusedSticks, int nLeft ) nif( nUnusedSticks = 0 and nLeft = 0 )nexit true;n if( nLeft = 0 ) /一根刚刚拼完nnLeft := L; /开始拼新的一根n找一根长度不超过nLeft的木棒（假设长为len

3、）拼在当前棍子上，然后nexit Dfs(nUnusedSticks 1, nLeft len )；nn拼每一根棍子的时候，应该确保已经拼好的部分，长度是从长到短排列的n由于取木棒是从长到短的，所以如果长得在前，短的在后不可行的话，那么相反的一定不可行2 8 3 1 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 52 31 8 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 6 47 52 81 4 37 6 52 8 31 4 57 68 32 1 47 6 52

4、8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 3 6 41 7 52 8 31 67 5 42 81 4 37 6 52 8 31 4 57 68 32 1 47 6 58 1 32 47 6 52 8 37 46 4 52 8 37 1 46 51 2 37 8 4 6 51 2 38 47 6 5图 3.4八 数 码 难 题 的 宽 度 优 先 搜 索 树2 8 31 47 6 51S023456789101112131415161718192021222324252627SgnBFS()nn初始化队列nwhile(队列不为空且未找到目标节点)nn取队首节点扩展，并将扩展出的节点放入队尾；n必要时要记住每个节点的父节点；nnn为节点编号n把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号n排列总数：9!=362880n只需要一个整数(4字节)即可存下一个节点n一个boolean标志数组flag 记录当前状态是否重复n判重用的标志数组只需要362,880字节即可。n此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。n输入数据：n2 3 4 1 5 x 7 6 8n输出结果