摘要人工智能作为计算机行业的一个分支，在近三十年来获得了迅速的发展，并且在很多科学的领域被广泛的应用，并有着显赫的成果。A*算法是人工智能在最优路径选择这方面最典型的一个代表，而八数码问题就是A*算法解决寻径问题的最经典的一个例子，本文就对八数码寻径问题进行一个详细的讨论。79341

本文介绍了八数码问题的核心，并对A*算法解决八数码问题的过程进行了详细分析。针对八数码问题事先作了判定，给出并证明了路径不存在时的条件。通过定义灵活的估价函数和分析估价函数对程序效率的影响,从而能对Closed表进行了相关的优化，提高其搜索的效率，并能够找到最短的路径来完成寻径。

毕业论文关键词  智能寻径 A*算法 八数码问题 启发式搜索

毕业设计说明书外文摘要

Title    Research and implementation of intelligent algorithm for optimal path searching     

Abstract As an important branch of computer science, artificial intelligence has gained rapid development in the past thirty years。 It has been widely used in many fields, and has achieved fruitful results。 A * algorithm is artificial intelligence in the optimal path selection the most typical representative, and the eight digital problem is the a * algorithm to solve routing problems of the classical an example。 In this paper, the eight digital routing problem for a detailed discussion。

This paper describes the core of the eight digital issues, and the A* algorithm to solve the problem of eight digital process is analyzed in detail。 To determine the eight digital issues in advance, given and proved that the path does not exist when the conditions。 A flexible valuation function is defined, and the effect of the evaluation function on the program efficiency is analyzed。 The Closed table is optimized to improve the search efficiency and to find the shortest path to complete the search。

Keywords   intelligent routing A* algorithm eight digital problem heuristic search algorithm。

目   次

1 绪论 1

1。1 引言 1

1。2 八数码问题 1

1。3问题的搜索形式描述 2

1。4程序设计思路 2

2 A*算法 3

2。1 A*算法背景介绍 3

2。2 A*算法原理介绍 6

2。3启发式函数的选择对于A*寻径的影响 8

2。4算法伪代码 8

3 算法实现 10

3。1如何在八数码问题中应用A*算法 10

3。2 程序执行步骤 10

3。3程序数据结构 11

3。3。1 open表的数据结构表示 11

3。3。2 closed表的数据结构表示 11

3。3。3 解决结点重复扩展问题 12

3。4 实验结果图示 12

3。5用java实现A*算法的相关代码及功能注释 13

4 结论 17

5 致谢 18

6 参考文献 19