1.算法原理1.1 搜索问题的形式化定义解决搜索问题时，首先需要对搜索问题进行形式化表述。搜索问题从以下几个方面表述：

状态空间：对问题的形式化，表示需要进行搜索的空间动作：对真正动作的形式化，表示从一个状态到达另一个状态初始状态：表示当前的状态目标：表示需要达到的目标的状态启发方法：用于指挥搜索的前进方向的方法问题的解：一个从初始状态到达目标状态的动作序列搜索问题可以用状态空间树表示，每个节点对应着状态空间中的一种状态。节点的父节点表示产生该状态的上一个状态，父节点生成子节点时需要记录生成节点所采取的行动与代价。

搜索算法的性能需要考虑一个方面：

完备性：当问题有解时是否一定能找到解最优性：搜索策略是否一定能找到最优解时间复杂度：找到解所需要的时间，又称为搜索代价空间复杂度：执行搜索过程中需要多少内存空间1.2 无信息搜索的具体算法1.2.1 宽度优先搜索宽度优先搜索用一个先进先出的队列实现，节点的拓展顺序与目标节点的位置无关。从状态空间树上看，宽度优先搜索的拓展顺序是按树的层次顺序来进行的。这样一来，短的路径会在任何比它长的路径之前被遍历，因此宽度优先搜索具有完备性和最优性。

定义为问题中一个状态最大的后继状态个数，为最短解的动作个数，则有：

时间复杂度：空间复杂度：1.2.2 深度优先搜索把当前要扩展的状态的后继状态放在边界的最前面，边界上总是扩展最深的那个节点。在状态空间无限或在状态空间有限，但是存在无限的路径（例如存在回路） 的情况下不具有完备性。在状态空间有限，且对重复路径进行剪枝的情况下才有。不具有最优性。

定义m是遍历过程中最长路径的长度，则有：

时间复杂度：

空间复杂度：

1.2.3 一致代价搜索边界中，按路径的成本升序排列，总是扩展成本最低的那条路径。当每种动作的成本是一样的时候，和宽度优先是一样的。假设每个动作的成本都大于某个大于0的常量，所有成本较低的路径都会在成本高的路径之前被扩展。给定成本，该成本的路径数量是有限的；成本小于最优路径的路径数量是有限的，最终，我们可以找到最短的路径，因此具备完备性和最优性。

对于一致代价搜索，当最优解的成本为C* ，上述最低代价为 ，则有：

时间复杂度：空间复杂度：1.2.4 深度受限搜索深度受限搜索是深度优先搜索，但是预先限制了搜索的深度L，因此无限长度的路径不会导致深度优先搜索无法停止的问题。 但只有当解路径的长度 ≤ L 时，才能找到解，故不具有完备性和最优性。

时间复杂度：空间复杂度：1.2.5 迭代加深搜索一开始设置深度限制为L = 0，迭代地增加深度限制，对于每个深度限制都进行深度受限搜索 。如果找到解，或者深度受限搜索没有节点可以扩展的时候可以停止当前迭代，并提高深度限制L 。如果没有节点可以被剪掉（深度限制不能再提高）仍然 没有找到解，那么说明已经搜索所有路径，因此这个搜索不存在解。具有完备性，且在每个动作的成本一致时具有最优性。

1.2.6 双向搜索同时进行从初始状态向前的搜索和从目标节点向后搜索，在两个搜索在中间相遇时停止搜索。假设两个搜索都使用宽度优先搜索，则具有完备性，在每条边/每个动作的成本一致的情况下具有最优性。

为了便于比较算法差异，我实现了宽度优先搜索和双向搜索两种算法。

2.1 宽度优先搜索

判断队列是否有终点和输出路径较为简单，下面只讨论算法终点部分。

每次取出队列首个节点，记其坐标为(x,y)，向上下左右四个方向拓展新的四个节点。拓展节点的方式如下：

判断具体的节点是否要加入队列时，判断节点位置是否是通路’0’或终点’E’即可。考虑到迷宫四周一圈都是墙壁’1’，所以不需要考虑出界的问题。

完整的源码和详细的文档，上传到了 【WRITE-BUG数字空间】，需要的请自取：https://www.writebug.com/code/0c802727-c792-11ed-ac02-6479f0e5e323/#