启发式搜索算法在N数码问题中的应用

编号

南京航空航天大学毕业论文

题目启发式搜索算法在N数码问

题中的应用

学生姓名

学号

学院

专业

班级

指导教师

二〇一三年六月

南京航空航天大学

本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。

作者签名：年月日

（学号）：

启发式搜索算法在N数码问题中的应用

摘要

N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。

本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。

关键词：启发式搜索，数码问题，A*算法，遗传算法

The Application of Heuristic Search Algorithm

on N-Puzzle Problem

Abstract

N-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency.

This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data.

Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm

目录

摘要 (i)

Abstract (ii)

第一章引言 (1)

1.1N数码问题 (1)

1.2启发式搜索 (2)

1.2.1 A*算法简介 (2)

1.2.2 模拟退火算法简介 (3)

1.2.3 遗传算法简介 (4)

第二章系统设计 (6)

2.1数据结构设计 (6)

2.2UI设计 (7)

2.3 算法设计 (8)

2.3.1 普通搜索算法 (8)

2.3.2 A*算法 (9)

2.3.3 遗传算法 (11)

第三章系统实现 (13)

3.1 数据结构实现 (13)

3.1.1 状态存储结构 (13)

3.1.2 优先级队列的实现 (14)

3.2 算法实现 (14)

3.2.1 A*算法 (14)

3.2.2 遗传算法 (15)

第四章运行结果与讨论 (18)

4.1 8数码实验结果分析 (18)

4.2 15数码实验结果分析 (19)

4.3 24数码实验结果分析 (21)

第五章总结 (23)

参考文献 (24)

致谢 (25)