readme.txt

8数码难题 深、广、a*

这是自12班曹子晟（2001010520）编写的八数码人工智能算法演示程序，采用c#语言编写，需要.NET Framework1.1支持。

chessApp.exe是界面工程。
chessArg.dll是算法库，包括所有的数据结构及算法定义。
chessApp.exe调用该dll文件实现，均为debug版本，请务必把两个文件放在同一目录夹内。

运行前请确认：
1。必须安装.NET Framework1.0/1.1
2。chessApp.exe & chessArg.dll在同一个目录夹下。

比较三种方法的异同：

宽度优先：
    在预设的一些可达值中，宽度优先的性能一般是较好的，无论从花费的步数还是搜索的时间上来看。这是很正常的，因为预设可达值时候，本身预设的搜索步数就不多，而宽度优先总能搜索到最小步数的结果。

深度优先：
    深度优先的性能一般是较差的，主要体现在它搜到的解得步数比较多，在时间方面，大部分时间一般略差于宽度。

A*算法：
    由于这是三种方法中唯一的有向搜索算法，所以性能从一定程度上来说不好比较。对于预设的有解情况，A*算法花费时间基本和宽度优先持平（其实是在秒级已经不好比较了），而步数介于宽度和深度之间，另外在某些状态下，A*可能会陷入不好的局面。从理论上来说，在更为复杂的情况下，A*算法确实会带来更好的性能。
    我觉得启发式算法更为适用情况或许应该在一些不需要得出解的情况下，比如说下棋的时候，不可能算出解而且短时间内得出解不现实，但却需要把握优解的方向，它适合提出一种搜索方向，预示着这个方向是好的状态趋势。
    另外，启发函数对于启发式算法的影响非常大，常常会导致启发式算法抛弃显而易见搜索方向而投向它认为的“好”方向去，这也在求解过程中遇到过。

对于图的一般搜索的理解:
    几乎所有的算法的区别都在于对Open,Closed表的处理上，宽度是先进先出的Open表，深度是先进后出的Open表，两者在选择节点扩展时都没有意图，所以是盲目的。启发式算法的特点是根据一定的评价对Open表的扩展节点进行选择，评价保留了已经的花费和将来前途的估计，按两部分的比重可以设计出各种特点的算法出来。启发函数对于算法性能的影响非常大。
    对于本次实验作业，比较基本的目的是找到解，而并没有体现出对于解的性质要求，所以我觉得这种状态下宽度优先更合适一些，A*的启发函数常常会把搜索带入歧途。