皇后问题的状态空间搜索策略与动态演示.doc

摘要：求解问题解，可利用状态空间进行搜索，它是一种问题求解策略，是一种模拟人类人工智能方法的问题的解决过程，问题的求解过程就是图搜索过程，从初始结点出发，根据一定搜索策略，一直到出现目的结点为止。搜索策略和设计是核心问题-解决问题搜索进程在存储空间的占用和计算的复杂性，它会影响效率的解决问题的能力，也是人工智能领域之一。

本文以一个经典的皇后问题的求解对解空间的生成、搜索策略进行分析研究。利用回溯法、分支限界法及启发式搜索算法对问题的状态空间进行搜索，然后对算法进行综合分析比较，得出有意义的结论。最后将求解过程进行动态演示，形象展示问题解的生成和求解过程。

关键词： 状态空间 n皇后问题 搜索策略 回溯法 分支限界法 启发式搜索法

目录

摘要

Abstract

1绪论-1

1.1研究背景-1

2状态空间及搜索策略-1

2.1状态空间-1

2.2几种搜索策略-2

2.2.1回溯法-2

2.2.2分支限界法-2

2.2.3启发式算法-3

3 n皇后问题的状态空间及搜索策略-3

3.1 问题描述-3

3.2 n皇后问题的状态空间及数据结构表示-3

3.3 n皇后问题的状态空间的搜索策略及算法实现-4

3.3.1回溯法-4

3.3.2分支限界法-6

3.3.3启发式搜索法-10

3.4 三种搜索算法的分析对比-13

4 n皇后问题搜索策略演示分析-14

5总结与展望-18

致谢-19

参考文献-20