< 人工智能 > 实 验 报 告 3

一、实验目的： 掌握汉诺塔的深度有界搜索求解算法的基本思想。

二、实验要求：

用C语言实现汉诺塔的深度有界搜索求解

三、实验语言环境：

C语言

四、设计思路：

含有深度界限的深度优先搜索算法如下：

(1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。

(2) 如果OPEN为一空表，则失败退出。

(3) 把第一个节点(节点n)从OPEN表移到CLOSED表。

(4) 如果节点n的深度等于最大深度，则转向(2)。

(5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。

(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。

五、实验代码：

#include <stdio.h>

#include <string.h>

typedef struct node {

long map;

long floor; //记录第几层

} node;

node queue[362880 / 2 + 1]; //奇偶各一半

long tail, head;

long hash[362880 / 32 + 1];

int main()

{

void Solve();

while (scanf("%ld", &queue[0].map) && queue[0].map) { memset(hash, 0, sizeof(hash));

queue[0].floor = 1; //(根节点)第一层

tail = head = 0;

Solve();

printf("max_floor == %d\n", queue[head].floor); printf("total node == %d\n", head + 1);

printf("total node in theory [%d]\n", 362880 / 2); }

return 0;

}

void Solve()

{

node e;

long i, map[9], space;

long Compress(long *);

int Visited(long *);

void swap(long &, long &);

while (tail <= head) {

e = queue[tail++];

for (i=8; i>=0; i--) {

map[i] = e.map % 10;

if (map[i] == 0) { space = i; }

e.map /= 10;

}

Visited(map); //根节点要置为访问过

if (space >= 3) { //can up

swap(map[space - 3], map[space]);

if (!Visited(map)) {

queue[++head].map = Compress(map);

queue[head].floor = queue[tail - 1].floor + 1;

}

swap(map[space - 3], map[space]);

}

if (space <= 5) { //can down

swap(map[space + 3], map[space]);

if (!Visited(map)) {

queue[++head].map = Compress(map);

queue[head].floor = queue[tail - 1].floor + 1; }

swap(map[space + 3], map[space]);

}

if (space % 3 != 0) { //can left

swap(map[space - 1], map[space]);

if (!Visited(map)) {

queue[++head].map = Compress(map);

queue[head].floor = queue[tail - 1].floor + 1; }

swap(map[space - 1], map[space]);

}

if (space % 3 != 2) { //can right

swap(map[space + 1], map[space]);

if (!Visited(map)) {

queue[++head].map = Compress(map);

queue[head].floor = queue[tail - 1].floor + 1; }

swap(map[space + 1], map[space]);

}

}

}

void swap(long &x, long &y)

{

x ^= y;

y ^= x;

x ^= y;

}

long Compress(long *map)

{

long t = 0, i;

for (i=0; i<9; i++) {

t = t * 10 + map[i];

}

return t;

}

int Visited(long *map)

{

long Hash(long *);

long n = Hash(map);

long a = n / 32;

long b = 1 << (n % 32);

if (hash[a] & b) {

return 1;

}

else {

hash[a] |= b;

return 0;

}

}

long Hash(long *map)

{

static long t, i, j;

static long formula[9] =

{ 1, 1, 2, 6, 24, 120, 720, 5040, 40320 }; static long temp[9];

for (i=0; i<9; i++) {

temp[i] = map[i];

}

t = 0;

for (i=0; i<9; i++) {

t += temp[i] * formula[8 - i]; for (j=i+1; j<9; j++) {

if (temp[j] > temp[i]) temp[j]--; } } return t; }

 

第二篇：二阶汉诺塔

实验二：用状态空间搜索法解决二阶汉诺塔问题

一、实验目的：

解决汉诺塔问题；

掌握状态空间搜索法；

二、实验原理

我们可以用状态空间图表示法来求解问题。状态空间图是由节点以及节点间的连线所构成的图。节点对应问题的解决状态；连线对应状态转换操作，即算符。在二阶汉诺塔问题求解过程中，我们用Sk=(SK0，SK1)表示问题的状态，SK0表示盘A所在的柱号，SK1表示盘B所在的柱号。全部可能的状态有以下9种：

s0=(1,1)    s1=(1,2)     s2=(1,3)

s3=(2,1)    s4=(2,2)     s5=(2,3)

s6=(3,1)    s7=(3,2)     s8=(3,3)

问题的初始状态集合为s={s0}，目标状态集合为G={s4，s8}。算符分别用A（I,j）以及B（I,j）表示。A（I,j）表示把盘A从柱i移到柱j上。一用有12个算符，分别是：

A(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2)

B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)

根据9中可能的状态和12中可能的算符,画出下列的状态空间图.

三、实验过程

根据实验原理，在纸上完成二阶汉诺塔的求解过程。并总结用状态图求解的一般思路。

四、主意事项

二阶的是最简单的，在移动的时候主意思维要清晰，不要盲目，以养成好习惯。