下载文档原格式
人工智能九宫格重移——搜索1.问题描述：八数码问题也称为九宫问题。
在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。
棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。
要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。
棋子移动后，状态就会发生改变。
解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
2.九宫重移有无答案检查（逆序数）我们把每个9宫格横向展开，如第一个123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然123456789的逆序数为0；考虑横向平移，那么逆序数的增量为2或0或-2；纵向平移，逆序数的增量为4或0或-4；但147258369的逆序数为奇数。
所以147258369是无解的情况。
由此也可以类推当将9宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。
3.BFS算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点ArrayList map = new ArrayList();//存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找3.1．BFS算法介绍广度优先搜索算法BFS基本思想：从图中某顶点v出发，逐层对节点进行拓展，并考察是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层节点进行扩展。
对九宫重排问题，即构造广度优先搜索树，从初始状态，利用广度优先搜索算法逐步找到目标状态的节点。
3.2．状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号0……8，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。
人工智能-----启发式搜索一．问题背景人工智能的宗旨是寻找一种有效的方式把智能的问题求解、规划和通信技巧应用到更广泛的实际问题中，集中于不存在算法解的问题，这也是为什么启发式搜索是一种主要的AI问题求解技术的原因。
对于人工智能系统而言，问题可能状态的数量随搜索的深入呈现指数或阶乘增长，为了明智地找出正解，将沿最有希望的路径穿越空间来降低这种复杂性，这便是启发式求解。
把没有希望的状态及这些状态的后代排除，这样便可以克服组合爆炸，找到可接受的解。
二．基本简介启发式求解对问题求解过程中下一步要采取的措施的一种精明猜测，是建立于强大的知识库的由经验总结出的求解方式。
简单的启发可以排除搜索空间的绝大部分。
启发式搜索由两部分组成：启发度量及是有这个度量进行空间搜索的算法。
下面介绍两种算法1.爬山法爬山策略在搜索中现扩展当前状态，然后再评估它的“孩子”。
而后选择“最佳的”孩子做进一步扩展；而且过程中既不保留它的兄弟姐妹，也不保留它的双亲。
因为这种策略不保存任何历史记录，所以它不具有从失败中恢复的能力。
图1 使用3层预判的爬山方法遇到的局部最大化问题爬山策略的一个主要问题是容易陷入局部最大值。
如果这种策略达到了一个比其他任何孩子都好的状态，它便停止。
因此为了提高性能，需要局部改进评估多项式。
2.最佳优先搜索算法最佳优先搜索算法使用了优先级队列，使得从诸如陷入局部优先等情况中恢复成为可能，从而使启发式搜索更加灵活。
最佳优先搜索算法使用列表来维护状态：用open列表来记录搜索的当前状态，用close列表记录已经访问过的状态。
在这种算法中新加的一步是对open 中的状态进行排序，排序的依据是对状态与目标“接近程度”的某种启发性估计。
最佳优先搜索算法总是选择最有希望的状态做进一步扩展。
然而由于他正在使用的启发可能被证明是错误的，所以它并不抛弃所有状态而是把他们维护在open中。
一旦发现启发将搜索引导到一条证明不正确的路径，那么算法会从open 中取出一些以前产生的“次优先”的状态，从而把搜索的焦点转移到空间的另一部分。
人工智能搜索算法1. 介绍人工智能（Artificial Intelligence，AI）搜索算法是指通过计算机程序对问题空间进行搜索，以找到最优解或接近最优解的方法。
在许多领域，如信息检索，机器学习，自然语言处理等，人工智能搜索算法都发挥着重要的作用。
本文将介绍人工智能搜索算法的基本原理和常见的搜索算法。
2. 搜索问题搜索问题是指在一个给定的问题空间中寻找目标解的问题。
问题空间由问题的状态和操作构成。
状态是问题解的表示形式，操作则是从一个状态到另一个状态的转换。
搜索问题的目标是找到一系列操作，使得从初始状态到目标状态的转换。
3. 盲目搜索算法3.1 深度优先搜索算法深度优先搜索算法（Depth-First Search，DFS）是一种经典的搜索算法，它通过栈的方式实现。
算法从起始状态开始，依次选择一个操作，然后转移到下一个状态，直到找到目标解或者无法转移到下一个状态为止。
def dfs(problem, state):if problem.goal_test(state):return statefor action in problem.actions(state):child = problem.result(state, action)result = dfs(problem, child)if result is not None:return resultreturn None3.2 广度优先搜索算法广度优先搜索算法（Breadth-First Search，BFS）是另一种常见的搜索算法，它通过队列的方式实现。
算法从起始状态开始，逐层地扩展状态空间，直到找到目标解。
def bfs(problem, state):queue = [state]while len(queue) !=0:state = queue.pop(0)if problem.goal_test(state):return statefor action in problem.actions(state):child = problem.result(state, action)queue.append(child)return None4. 启发式搜索算法4.1 A*算法A算法是一种常用的启发式搜索算法，它通过估计从当前状态到目标状态的代价来选择下一步操作。
