moinmiax搜索算法描述

moinmiax搜索算法描述？

搜索算法实际上是根据初始条件和自定义的一种搜索规则构造一颗“解答树”并寻找符合目标状态的节点的过程。所有的搜索算法从最终的算法实现上来看，都可以划分成两个部分——控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。其实，在这样的思考过程中，我们已经不知不 觉地将一个具体的问题抽象成了一个图论的模型——树，即搜索算法的使用第一步在于搜索树的建立。

初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。

二、回溯算法

是搜索算法中最基本的算法，采用走不通就掉头的方法作为控制结构，采用先根遍历的方法构造解答树，可用于找解以及最优解。

三、深度优先搜索

思想：先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。

深度优先搜索的优化

1、优化思想

减少所遍历的状态总数

2、三种方法

(1)减少节点数

思想：尽可能减少生成的节点数

(2)定制回溯边界

思想：定制回溯边界条件，剪掉不可能得到最优解的子树

在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵活地去定制回溯搜索的边界。

在深度优先搜索的过程当中，往往有很多走不通的“死路”。假如我们把这些“死路”排除在外，不是可以节省很多的时间吗？打一个比方，前面有一个路径，别人已经提示：“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。这样，浪费了很多的时间。针对这种情况，我们可以把“死路”给标记一下不走