目录
引言：借助产生式系统和状态空间法，选择一种编程语言（我用的是java），完成题目要求。
一、八数码难题
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格可用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局，找到一种移动方法，实现从初始布局到目标布局的转变。
1. 需求分析
在一个3×3的棋盘格中，摆有1-8数字的八个棋子，剩余的空格用0表示。给出一种初始布局和目标布局，找到一种移动方法，实现从初始布局到目标布局的转变，规则是移动空格，并且空格不能移出棋盘外。
2. 数据结构、功能模块设计与说明
2.1 算法思路
采用广度优先搜索算法，从初始状态开始，每次进行可行操作（与0所在位置相邻数字交换），得到新的状态，并将其加入队列中，直到找到目标状态为止。
在搜索之前需要判断一下目标状态是否可达，根据八数码问题的特性，合法的移动操作只涉及两个数字的交换，空格左右移动不会改变任何两对数字之间的逆序对数量，因为整个序列的相对顺序保持不变。空格上下移动会改变两对数字之间的逆序对数量。当初始状态的空白格和目标状态的空白格在不同行时，只有通过上下移动才有可能改变逆序对的数量，从而实现初始状态到目标状态的转换。故当初始状态和结果状态逆序数奇偶性相同的时候才可达，否则不进行搜索。
当目标状态可达的时候，又因为有很多状态会重复出现，所以判断移动之后的状态是否出现过？这里用哈希表来去重，如果出现过则丢弃；否则，将它加入队列，并将它对应的步数设为前一个状态的步数+1，直到找到目标状态为止。
2.2 数据结构
（1）Scanner：用于从控制台读取输入。
（2）HashMap：用于存储状态路径信息和去重，其中键是状态的字符串表示，值是一个 State 对象，包含了上一个状态的字符串、到达当前状态的操作和已经移动的步数。
（3）队列：用于实现广度优先搜索算法，使用 LinkedList 类作为队列的实现。
（4）StringBuffer：创建一个 StringBuffer 对象，调用其 setCharAt() 方法进行字符交换。
3. 核心代码与测试结果说明
3.1 核心代码
（1）初始化状态
（2）判断可达性
①求逆序对
②判断初始布局和结束布局奇偶性是否相同
（3）哈希表
（4）队列实现bfs
3.2 测试结果说明
（1）测试数据
（2）控制台打印每一步的状态和操作
4. 存在的问题与体会
4.1 存在的问题
这种解法空间复杂度较高。使用广度优先搜索算法时，需要存储所有的状态和路径信息。通过哈希表来存储状态路径信息，可能会占用较大内存空间，特别是当搜索空间非常庞大时。所以可以考虑使用其他数据结构或优化算法，以减少空间复杂度。
4.2 体会
虽然代码存在一些问题和可以改进的地方，但我深入理解了广度优先搜索算法，并在实践中获得了关于数据结构和代码设计的经验。
二、传教士与野人渡河
设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船每一次只能装载2人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。请你设计一个方案怎样才能用这条船安全地把所有人都渡过河去？编程实现你的方案。
1. 需求分析
有3个传教士和3个野人从河右岸乘一只船到左岸，且该船每次只能装载2人。必须保证在任何时候，野人人数不能超过传教士人数，否则野人就会把传教士吃掉。设计一个方案怎样才能用这条船安全地把所有人都渡过河去？并且推广到有n个传教士和n个野人，河边的船每次至多可供k个人渡河的解决方案。
2. 数据结构、功能模块设计与说明
2.1 算法思路
使用深度优先搜索算法，寻找所有可能的移动方案。其中，每个状态包括左岸传教士和野人的数量，以及船的位置（左岸或右岸）。通过不断尝试不同的移动方案，最终找到一种能够使所有人都安全到达右岸的方法。
2.2 数据结构
（1）自定义属性如下
（2）设计State类，属性如下
（3）用list记录路径
（4）存储可枚举的方法
3. 核心代码与测试结果说明
3.1 核心代码
（1）初始化数据
（2）列出可枚举的方法，即不同人数的乘客在船上的组合方式。
（3）过河问题的状态
（4）dfs算法
3.2 运行结果
4. 存在的问题与体会
更加深刻的理解了dfs算法，以及它在实际情况中的应用。
标签：状态,传教士,人工智能,移动,空格,野人,数码,数据结构 From： https://blog.csdn.net/m0_67830223/article/details/140403987