摘 要：近年，互联网的迅速普及，数据的爆发式增长，信息技术的不断迭代改革，计算机越来越智能化，人工智能也逐渐兴起，计算机从被动输入到主动学习，这都预示着一切都在不断的变化，也在加快的变化，而在这变化之下是各种算法的更新迭代，与强大的算法理论在支撑。

本文针对日常生活中常常面临的路径规划问题进行探讨，对几种典型的搜索策略，包括DFS、BFS、双向BFS及A*算法进行探讨。对每种搜索策略，从算法的基本思想、算法的基本框架入手，并利用visual_studio开发工具，基于C/C++语言对典型应用问题进行分析和求解，包括树的遍历、八数码问题、马踏棋盘等，对搜索策略进行深入探究。论文最后，通过应用不同的搜索策略，实现路径的搜索问题的求解，对各个搜索策略进行对比分析，总结出每个算法的特点和适用场合，以便在具体的应用问题中，选择和设计合适的搜索策略。

 

关键词：搜索；DFS；BFS；A*；路径规划

 

目 录

摘 要

Abstract

第1章 绪 论 1

1.1研究目的和意义 1

1.2国内外发展（应用）现状 1

1.3论文所做工作及思想 2

1.4论文的结构 2

第2章 搜索算法 3

2.1算法概要 3

2.2解空间及解空间树 3

2.3结点与扩展 3

第3章 深度优先搜索（DFS） 4

3.1深度优先搜索（DFS）的概述 4

3.1.1 DFS基本思想 4

3.1.2 DFS算法框架 4

3.1.3典型问题及应用领域 5

3.2马踏棋盘问题 6

3.2.1问题提出 6

3.2.2问题分析 6

3.2.3算法描述与代码实现 7

3.2.4算法分析及优化策略 8

3.3在路径规划问题中的应用实例 9

3.3.1问题描述 9

3.3.2问题分析 10

3.3.3算法实现 10

3.3.4结果分析 11

第4章 广度优先搜索（BFS） 13

4.1广度优先搜索（BFS）的概述 13

4.1.1BFS基本思想 13

4.1.2BFS算法框架 13

4.1.3典型问题及其应用领域 14

4.2二叉树的遍历 14

4.2.1遍历的定义 14

4.2.2遍历的策略 14

4.2.3搜索过程及算法 15

4.2.4结果分析 16

4.3广度优先搜索（BFS）对路径的探索 16

4.3.1问题描述 16

4.3.2问题分析 17

4.3.3算法实现 17

4.3.4结果分析 18

第5章 双向广度搜索 19

5.1双向广度优先搜索的概述 19

5.1.1双向搜索的基本思想 19

5.1.2双向BFS算法框架 19

5.1.3应用领域 19

5.2双向广度优先搜索对路径的探索 20

5.2.1问题描述 20

5.2.2问题分析 20

5.2.3算法实现 20

5.2.4结果分析 22

第6章 启发式搜索（A*） 23

6.1启发式搜索（A*）的概述 23

6.1.1启发式搜索 23

6.1.2A*算法的基本思想 23

6.1.3A*算法框架 23

6.1.4应用领域 24

6.2八数码问题 24

6.2.1问题描述 24

6.2.2问题分析 24

6.2.3算法实现 25

6.2.4结果分析 27

6.3启发式搜索（A*）实现对路径的探索 27

6.3.1问题描述 27

6.3.2问题分析 27

6.3.3算法实现 27

6.3.4 总结分析 29

第7章 总结 30

7.1搜索算法 30

7.2对路径探索的比较 30

7.2.1对目标位置的需求 30

7.2.2对问题深度与宽度的需求 30

7.3拓展分析 30

致 谢 31

参考文献 32