人工智能 实验三 汉诺塔的深度有界搜索求解

1、 实 验 报 告 3一、实验目的：掌握汉诺塔的深度有界搜索求解算法的基本思想。二、实验要求：用C语言实现汉诺塔的深度有界搜索求解三、实验语言环境：C 语言四、设计思路：含有深度界限的深度优先搜索算法如下： 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个 解。如果 OPEN 为一空表，则失败退出。把第一个节点(节点n)从OPEN表移到CLOSED表。如果节点n的深度等于最大深度，则转向(2)。扩展节点n,产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则 转向(2)。如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。五、实验代码#

2、include #include typedef struct node long map;long floor; /记录第几层 node;node queue362880 / 2 + 1; / 奇偶各一半long tail, head;long hash362880 / 32 + 1;int main()void Solve();while (scanf(%ld, &queue0.map) & queue0.map) memset(hash, 0, sizeof(hash); queue0.floor = 1; /(根节点)第一层 tail = head = 0;Solve(); print

3、f(max_floor = %dn, queuehead.floor); printf(total node = %dn, head + 1);printf(total node in theory %dn, 362880 / 2);return 0;void Solve()node e;long i, map9, space;long Compress(long *);int Visited(long *);void swap(long &, long &);while (tail =0; i-) mapi = e.map % 10;if (mapi = 0) space = i; e.ma

4、p /= 10;Visited(map); / 根节点要置为访问过if (space = 3) /can upswap(mapspace - 3, mapspace);if (!Visited(map) queue+head.map = Compress(map); queuehead.floor = queuetail - 1.floor + 1;swap(mapspace - 3, mapspace);if (space = 5) /can downswap(mapspace + 3, mapspace);if (!Visited(map) queue+head.map = Compres

5、s(map); queuehead.floor = queuetail - 1.floor + 1;swap(mapspace + 3, mapspace); if (space % 3 != 0) /can leftswap(mapspace - 1, mapspace);if (!Visited(map) queue+head.map = Compress(map); queuehead.floor = queuetail - 1.floor + 1;swap(mapspace - 1, mapspace);if (space % 3 != 2) /can rightswap(mapspa

6、ce + 1, mapspace);if (!Visited(map) queue+head.map = Compress(map); queuehead.floor = queuetail - 1.floor + 1;swap(mapspace + 1, mapspace);void swap(long &x, long &y) x A= y; y a= x;x A= y;long Compress(long *map) long t = 0, i;for (i=0; i9; i+) t = t * 10 + mapi;return t;int Visited(long *map)long Hash(long *);long n = Hash(map);long a = n / 32;long b = 1 (n % 32);if (hasha & b) return 1;else hasha |= b; return 0;long Hash(long *map)static long t, i, j;static long formula9 = 1, 1, 2, 6, 24, 120, 720, 5040, 40320 ;static long temp9;for (i=0; i9