人工智能實驗三漢諾塔的深度有界搜索求解

1、 實 驗 報 告 3 一、實驗?zāi)康?：掌握漢諾塔的深度有界搜索求解算法的基本思想。二、實驗要求：用 c語言實現(xiàn)漢諾塔的深度有界搜索求解三、實驗語言環(huán)境：c語言四、設(shè)計思路：含有深度界限的深度優(yōu)先搜索算法如下：(1) 把起始節(jié)點s放到未擴展節(jié)點open 表中。如果此節(jié)點為一目標節(jié)點，則得到一個解。(2) 如果 open 為一空表，則失敗退出。(3) 把第一個節(jié)點(節(jié)點 n) 從 open 表移到 closed 表。(4) 如果節(jié)點n 的深度等于最大深度，則轉(zhuǎn)向(2) 。(5) 擴展節(jié)點n，產(chǎn)生其全部后裔，并把它們放入open 表的前頭。如果沒有后裔，則轉(zhuǎn)向 (2) 。(6) 如果后繼節(jié)點中有任一

2、個為目標節(jié)點，則求得一個解，成功退出； 否則， 轉(zhuǎn)向 (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); que

3、ue0.floor = 1; /( 根節(jié)點 )第一層tail = head = 0; solve(); printf(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 &

4、amp;); while (tail =0; i-) mapi = e.map % 10; if (mapi = 0) space = i; e.map /= 10; visited(map); / 根節(jié)點要置為訪問過if (space = 3) /can up swap(mapspace - 3, mapspace); if (!visited(map) queue+head.map = compress(map); queuehead.floor = queuetail - 1.floor + 1; swap(mapspace - 3, mapspace); if (space = 5)

5、/can down swap(mapspace + 3, mapspace); if (!visited(map) queue+head.map = compress(map); queuehead.floor = queuetail - 1.floor + 1; swap(mapspace + 3, mapspace); if (space % 3 != 0) /can left swap(mapspace - 1, mapspace); if (!visited(map) queue+head.map = compress(map); queuehead.floor = queuetail

6、 - 1.floor + 1; swap(mapspace - 1, mapspace); if (space % 3 != 2) /can right swap(mapspace + 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 = y; y = x; x = y; long compress

7、(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;