搜索算法学习与编程实现（程序搞定）

趁着在学习人工智能，对于搜索算法以前也自学过，但缺乏实践，为自己定个小实践吧：以八数码难题这个简单的实例为例，系统回顾下搜索算法，包括广度优先搜索、深度优先搜索、代价树的广度和优先搜索，启发

式搜索中的A算法和A*算法，另外由于要用到链表，不妨把linux内核中常用的双链表拿来用吧。

知识准备：
西邮linux内核的双链表数据结构学习讲座：
http://www.xiyoulinux.cn/blog/?p=135
讲座ppt下载：

关于搜索：问题求解与搜索原理.pdf ：

八数码问题：（摘自《人工智能原理及其应用》教材）

  有一个3*3的方格棋盘，其中有0-8 9个数，0表示空格，

其他的代表牌吧，求由初始状态S0到达目标状态Sg步数最少的解。

 允许使用的操作：空格上下左右移动，即只允许把位于空格

左、上、右、下方的牌。

如

S0

2 8 3

1 0 4

7 6 5

sg

1 2 3

8 0 4

7 9 6

注：开始没注意在xp下用DEV-C++编译怎么都说list.h头文件有错（原因是：标准C与GCC的区别），

还是在linux下用gcc编译通过了。
文件:
datamove.tar.bz2
大小:
18KB
下载:
下载

解压: tar jxvf datamove.tar.bz2
dataMove/
|-- Makefile
|-- datamove1.c
|-- datamove1.txt
|-- datamove2.c
|-- datamove2.txt
|-- list.h
|-- out.txt
`-- readme

上述文件包中已经实现了广度搜索

和带深度限制dm的深度优先搜索，分别是datamove1.c

 和 datamove2.c，把书上关于算法的抽象内容

用程序表达出来就是了，

主要是open表和close表的使用以及节点扩展麻烦一点，

幸好我们这里有linux内核中的双链表榜样，拿来用吧
这里还有位达人的博客也讲了双链表，

如果上面西邮的讲座没看懂的话，参考着看下
http://blog.chinaunix.net/u2/74234/article_95716_2.html

A算法和A*算法程序：datamove3.c datamove4.c

文件:
datamove.tar.bz2
大小:
18KB
下载:
下载

2009-12-20 八数码问题从gcc移植到VC6.0工程下面

http://blogimg.chinaunix.net/blog/upfile2/091220115711.rar

2010-1-15 利用A*算法解决野人和修道士过河问题

设有3个修道士和3个野人来到河边，打算用一条船从河的左岸到河的右岸去。但船每次只能载两个人，在任何岸边野人的数目都不得超过修道士的数目，否则修道士就会被野人吃掉。假设野人服从任何一种过河安排，请使用状态空间的A*启发式搜索法，规划一使全部6人安全过河的方案。

这是研究生课程《人工智能》的一次大作业，还是使用了linux的双料表，所有算法参考教材，源程序自己编写

A*算法中需要用到Open表和Close表的操作，这里使用双链表的数据结构来表示这两个表。Linux内核源码中的双链表list.h具有很好的抽象性，适当修改list.h头文件并利用它来实现这里具体的状态节点操作，如：

将节点tmp添加至Open表首部list_add(&(tmp-list),&(openTable))；将节点tmp添加至Open表尾部

list_add_tail(&(tmp->list), &(openTable))；

将节点tmp从Open表中取出放入Close表

list_move_tail(&(tmp->list), &(closeTable));

其中tmp->list均为在Linux内核源码list.h中定义的struct list_head类型的结构体，我们在状态节点struct state_node中包含该类型的成员list，即可实现对状态节点数据的双链表操作，具有很好的抽象性。

附源码（VC工程下的控制台程序）、word算法描述：

文件:
人工智能---段力SY0903202.rar
大小:
89KB
下载:
下载