搜索算法

搜索

搜索算法就是在问题的解空间进行搜索，从而得到可行解或最优解。搜索的每一步，都有一个“状态”，搜索的时候需要找到合理的状态，进行搜索。一次成功的搜索就是在“状态”空间中找到一条从起点到终点的路径（可以想象为一棵树从根节点到某个叶子节点的路径）。

1. DFS和BFS

搜索一般分为两种：深度优先DFS和广度优先BFS。一般地，DFS时，常常将“状态”保存在DFS函数的参数，即栈内存中；而BFS时，常将“状态”单独保存在BFS函数外部的堆内存中。

2. DBFS

DBFS从起点和终点分别开始进行BFS搜索，直到一个扩展队列中出现另一个队列中已经扩展过的节点。在扩展节点的时候，每次都选择节点比较少的那个队列进行扩展，并不是机械的交替。

    void DBFS(){
    1. 将起点放入队列Q0，终点放入队列Q1
    2. 当两个队列都非空时，做如下操作：
    （1）如果队列Q0里的节点数 < Q1中的节点数，则扩展队列Q0
    （2）否则，扩展队列Q1
    3. 如果队列Q0未空，则不断扩展Q0，直到Q0为空
    4. 如果队列Q1未空，则不断扩展Q1，直到Q1为空
    }
    //扩展函数
    int Expand(int i){ //i 为队列的编号，0或者1
    取队列Qi的头结点H
    对H的每一个相邻节点adj:
    1.如果adj在队列Qi中出现过，则抛弃adj
    2.如果adj在队列Q中未出现过，则
    （1）将adj放入队列Qi
    （2）如果adj曾经在队列Q1-i中出现过，则输出找到的路径
    }

剪枝

    将在运用搜索方法进行求解的时候，通过对搜索空间进行合理的剪枝可以大大加快搜索的速度。常用的剪枝方法主要有两种：
可行性剪枝
    在进行下一步之前，判断是否可以继续进行，若不可能到达终点，则不扩展下一步的节点
最优性剪枝
一、一般最优性剪枝
    在一步步求解的过程中使用全局变量记录已经求得的最优解，如果当前节点未到达终点，但是当前的结果已经差于已经求出来的最优结果，则剪枝；同时，每次到达终点时，都更新最优解。

二、带估计函数的最优性剪枝
在一步步求解的过程中使用全局变量记录已经求得的最优解，如果继续进行下一步操作得到的结果肯定差于最优解，则不进行扩展；同时，每次到达终点时，都更新最优解。

启发式搜索（A算法）【针对BFS进行优化】

在BFS算法中，若对每个状态n都设定估计函数 f(n) = g(n) + h(n)，并且每次从队列中选取节点进行扩展时，都选取f值最小的节点，这种搜索方法为启发式搜索。
g(n): 从起点都当前节点n的代价
h(n): 从当前节点n到终点的估计代价

**A*算法【针对BFS进行优化】**

A算法中的估计函数若选取不当，则可能找不到解，或者找到的解不是最优。A*对估计函数做了限制，确保可以找到最优解。
在BFS搜索时，每个状态n都有估计函数，f*(n) = g(n) + h*(n)，
采用优先队列，扩展时，选取队列头元素（f(n)最小）。

**IDA*算法【针对DFS进行优化】**

深度每次增加1的方法：
（1）并不需要知道全局最优解，设置一个递归深度界限K，如果当前搜索深度超过K,则进行剪枝返回；
（2）若在深度不超过K的某次搜索中到达终点，则返回最优解；且需要注意对同样深度不超过K,D但是在该次递归之后的递归进行剪枝（因为在深度K处已经找到解了）
（3）若在深度不超过K的所有搜索中没有到达终点，则将K增加1，继续(2),(3)步骤
改进：
（1）将初始化深度设为 K = 1
（2）每次进行深度不超过K的递归：
（2.1）如果当前节点为终点，则返回成功；
（2.2）如果当前节点不是终点，且其深度不超过K,估计出该节点到达终点的最小步数h(n)，从起始点到该节点的步数为g(n)，用外部变量 next_K记录下 h(n)+g(n)的最小值。
（3）K设置为 next_K，重复执行（2）（3）