搜索算法

Intro #

问题求解与搜索算法 #

问题求解涉及到两个方面:

搜索算法是一种通用的问题求解方法: 首先把问题表示 转换为一个状态空间图,然后设计特定的图遍历方法在状态空间中搜索问题的答案。

为了提高搜索的效率,在遍历状态空间时需要添加优化技术,比如剪枝策略用于尽可能避免无效搜索,启发式信息用来加速朝目标状态逼近的速度。

状态空间图 #

一个问题用搜索算法求解时,往往需要把问题描述为状态空间图,包括以下要素

状态空间图可以形式化地定义为一个四元组 (S,A,G,F)

搜索就是在状态空间图中从初始状态出发,执行特定的操作,试探地寻找目标状态的过 程。当然,也可以从目标结点到初始结点反向进行。状态空间图中从初始状态到目标状 态的路径则代表问题的解。解的优劣由路径耗散函数量度,最优解就是路径耗散函数值 最小的路径。

搜索算法类型 #

基于枚举的通用搜索 #

DFS #

深度优先搜索 (Depth First Search, DFS) 是一种通用的图和树的遍历方法,给 定图𝐺 = (𝑉, 𝐸),深度优先搜索的基本思想为:

基于栈的 DFS 算法框架:


function DFS(problem,stack){
    node = Make-node(Initial-State[problem]);
    stack <- insert(node,stack);
    while(1){
        if(stack == empty){
            return;
        }
        node = pop(stack);
        visit(node);
        if(state[node]== GOAL){
            return Solution(node);
        }
        sonNodes = Expand(node,problem);
        stack <- InsertAll(sonNodes,stack);
    }
}

基于递归的 DFS 算法框架:

function DFS(problem, node)
    if State[node] == Goal/Failure // 递归出口
        return Solution(node); 
    else
        visit(node); // 访问当前结点
        for(iterator sonNode = Init(node); sonNode <= Last(node); sonNode++)
            if notVisited(sonNode)
                DFS(sonNode); // 递归遍历其子树
    return;
//注解:for循环用于扩展node的所有未访问子结点,并依次递归 调用,其中Init表示node的第一个子结点,Last表示最后一个子结点。

BFS #

广度优先搜索 (Breadth First Search, BFS) 类似于树的按层次遍历的过程,是 另外一种通用的图和树的遍历方法。给定图𝐺 = (𝑉, 𝐸),BFS 基本思想为

function BFS(problem,queue)
    node = Make-Node(Initial-State[problem]); 
    queue ← Insert(node, queue);
    do while(1)
        if queue == Empty 
            return failure
        node ← Remove-First(queue) visit(node);
        if State[node] == Goal
            return Solution(node)
        sonNodes = Expend(node, problem);
        queue ← Insert-All(sonNodes, queue) //依次插入所有子状态

枚举 + 优化的通用搜索 #

回溯算法 #

深度优先搜索是一种依照“能进则进,不进则退”的策略进行的枚举算法,也就 意味着它可能遍历整个状态空间图,导致算法效率不高。给定一个问题的状态空 间表示,设计搜索算法时需要考虑以下两个事实:

回溯算法 = 深度优先搜索 + 剪枝策略

回溯算法需要定义问题的状态空间图,包括以下四个方面:

  1. 问题的状态表示: 一般用 k 元组表示,即𝑋 = [𝑥1, 𝑥2, ⋯ , 𝑥𝑘],其中向量的维度,以及每一个分量的值域是状态表示的关键问题
  2. 约束条件:X 中每一个分量自身的取值约束; 分量之间的取值约束。注意: 约束条件是 剪枝策略的基础,需要深入分析和挖掘
  3. 操作符集合: 从一个状态转换到另外一个状态的操作,在状态空间图中它构成边集。
  4. 问题解和解空间: 问题的解可以认为是一类特殊的状态,即目标状态。对于问题的一个 实例,所有满足约束条件的解向量就构成该问题实例的解空间。

注意: 在回溯算法中,状态空间图并不是显式地构造,也就是说,并没有在内存中生成一个完整的状态空间图。实际上,回溯算法只是根据初始状态,目标状态和操作符集合 (它产生后续状态),隐式地构造状态空间图。

剪枝策略

回溯算法需要设计合适的剪枝策略,尽量避免不必要的搜索。常用的剪枝策略包括两大类:

  1. 约束函数剪枝: 根据约束条件,状态空间图中的部分状态可能是不合法 的。因此,在状态空间图中以不合法状态为根的子图/子树是不可能包 含可行解的,故其子空间不需要搜索。
  2. 限界函数剪枝: 这种策略一般应用于最优化问题。假设搜索算法当前访 问的状态为𝑆,且存在一个判定函数: 它能判定以𝑺为根的子图/子树不 可能包含最优解,因此该子图/子树可以剪除而无需搜索

约束函数剪枝 可以剪除状态空间图中的不可行解

限界函数剪枝 用于剪除状态空间图中的可行但是非最优的解

DFS 回溯算法
搜索视角 遍历整棵完全二叉树 添加剪枝策略,尽量避免不必要的搜索
枚举视角 全局判定 [𝑥1,𝑥2,⋯,𝑥n] 局部预判 [𝑥1,?,?, ⋯] [𝑥1,𝑥2,?, ⋯]

回溯算法程序框架:

回溯算法设计通常包含以下 2 个主要步骤:

void backtrack(int t) {
    if (t > n)
        output(x);
    else {
        for (int i = Init(n, t); i <= Last(n, t); i++) {
            x[t] = Node(i);
            if (constraint(x) && bound(x)) {
                backtrack(t + 1);
            }
        }
    }

注解:for 循环体依次扩展当前结点的所有子结点,Init() 和 Last() 是一种抽象表示,返回开始子结点和末尾子结点的编号。for 循环执行完毕则回溯到父结点。

分支限界法 #

广度优先搜索是一种依照“由近及远,按层展开”的策略进行的枚举算法,也就 意味着它需要遍历整个状态空间图,导致算法效率不高。给定一个问题的状态空 间表示,设计搜索算法时需要考虑以下两个事实:

扩展子结点时,一次性生成它的 所有孩子结点,判断孩子结点是 舍弃还是保存?舍弃那些不可能 导致可行解或最优解的孩子结点, 其余的结点进入队列中

分支限界算法 = 广度优先搜索 + 剪枝策略

分支限界算法需要定义问题的状态空间图,包括以下四个方面:

  1. 问题的状态表示: 逻辑上用 k 元组表示,即𝑋 = [𝑥1, 𝑥2, ⋯ , 𝑥𝑘],其中向量的维度,以及每 一个分量的值域是状态表示的关键问题
  2. 约束条件:X 中每一个分量自身的取值约束; 分量之间的取值约束。注意: 约束条件是 剪枝策略的基础,需要深入分析和挖掘
  3. 操作符集合: 从一个状态转换到另外一个状态的操作,在状态空间图中它构成边集。
  4. 问题解和解空间: 问题的解可以认为是一类特殊的状态,即目标状态。对于问题的一个 实例,所有满足约束条件的解向量就构成该问题实例的解空间。

注意: 在分支限界算法中,状态空间图并不是显式地构造,也就是说,并没有在内存中生成一个完整的状态空间图。实际上,分支限界算法只是根据初始状态,目标状态和操作符集合 (它产生后续状态),隐式地构造状态空间图。

约束函数剪枝

限界函数剪枝

约束函数剪枝 可以剪除状态空间图中的不可行解

限界函数剪枝 用于剪除状态空间图中的可行但是非最优的解

1 BFS 分支限界算法
图搜索视角 遍历整棵完全二叉树 添加剪枝策略,尽量限制搜索无效的分支
枚举视角 全局判定 [𝑥1,𝑥2,⋯,𝑥n] 局部预判 [𝑥1,?, ?, ⋯] [𝑥1,𝑥2,?, ⋯]

分支限界算法设计通常包含以下 2 个主要步骤:

  1. 针对所给问题,定义问题的状态空间图
  2. 以广度优先方式搜索状态空间图,并在搜索过程中用剪枝策略避免无效搜索
function BFS(problem,queue)
    node = Make-Node(Initial-State[problem]); 
    queue ← Insert(node, queue);
    do while(1)
        if queue == Empty 
            return failure
        node ← Remove-First(queue) visit(node);
        if State[node] == Goal
            return Solution(node)
        while(sonNode = Next(problem,node)!=NULL){
            if(constraint(sonNode) && bound(sonNode)){
                Insert(queue,sonNode);
            }
        }

启发式搜索 #

最佳优先搜索 #

最佳优先搜索

评估函数设计

BestFirstSearch() {
    Open = [起始结点];
    Closed = [];
    while (Open表非空) {
        从Open中取得一个结点X, 并从OPEN表中删除.if (X是目标结点) {
            求得路径PATH;
        }
        for (每一个X的合法子结点Y) {
            if (Y不在OPEN表和CLOSED表中) 求Y的估价值 f(Y);
            并将Y插入OPEN表中; // 还没有排序 else if( Y在OPEN表中 )
            if (Y的估价值小于OPEN表的估价值)
                更新OPEN表中的估价值;
            else { // Y在CLOSED表中
                if (Y的估价值小于CLOSED表的估价值) 更新CLOSED表中的估价值;
                从CLOSED表中移出结点, 并放入OPEN表中;
            } // end for
            将X结点插入CLOSED表中;
            按照估价值将OPEN表中的结点排序;
        } // end while } //end func

启发式搜索

选择下一个扩展结点的策略总是选择评估函数 𝑓(∙) 值最 小的状态结点作为新扩展结点。

$$f (n) = g(n) + h(n)$$

A* 算法 #

启发式搜索选择下一个扩展结点的策略总是选择评估函数 𝑓(∙) 值最小的状态结 点作为新扩展结点。

$$f (n) = g(n) + h(n)$$

如果𝒈(𝒏) 表示从初始状态到状态 N 的成本,𝒉(𝒏) 表示从状态 N 到目标状态的成本估计,𝒉∗(𝑵) 是从状态结点 N 到目标状态的最优路径成本,满足: $$𝟎 ≤ 𝒉(𝑵) ≤ 𝒉∗(𝑵),𝒘(𝑁,𝑁’) ≥𝜖> 0$$ 其中𝑤(𝑁, 𝑁’) 表示任何两个状态之间的路径成本,要求大于 0。则最佳优先搜索得到 的解总是最优解,对应搜索算法称之为 A* 算法。 如果 N 是目标状态 G,则定义𝐻(𝐺) = 0。

A 算法的最优性证明*

对抗搜索 #

小结 #

搜索算法的基本原理

常用的搜索策略

e.g.s #

传教士问题 #

在河的左岸有三个传教士、一条船和三个野人,传教士们想用这条船将所有的成员都运 过河去,但是受到以下条件的限制:
1 教士和野人都会划船,但船一次最多只能装运两个;
2 在任何岸边野人数目都不得超过传教士,否则传教士会遭遇危险:被野人攻击甚至吃掉。 此外,假定野人会服从任何一种过河安排,试设计出一个确保全部成员安全过河的计划。

8 数码问题 #

把左图的 8 数码排列通过空格的 上下左右移动,转换为右图的 8 数码排列

背包问题 #

【例-1】对于 𝑛 = 3 的0-1背包问题,其中背包容量𝑐 = 30,每个物品的重 量和价值分别为:𝑤 =< 16,15,15 >, 𝑝 =< 45,25,25 >。

旅行商问题 #

【例-2】某商人要到若干城市去推销商品,已知各城市之间的旅行费用,他要 选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的费用 最少。试构造下图对应问题实例的最优旅行方案。

装载问题 #

问题描述:有n个集装箱要装上2艘载重量分别为C1和C2的轮船,其中集装箱 i 的重量为Wi, 且 ∑ Wi ≤C1+C2。请设计算法确定是否有一个合理的装载方案可将这些集装箱上这2艘轮 船。 输入:多组测试数据。每组测试数据包括两行:第一行输入集装箱数目n(n<1000), 以及两艘轮船的载重C1和C2;第二行输入n个整数,表示每个集装箱的重量。 输出:如果存在合理装载方案,输出第一艘轮船的最大装载重量;否则,输出“No”。

把原问题简化为一艘轮船的装载问题。容易证明下述 结论: 如果一个给定装载问题实例有解,则采用下面 的策略可得到最优装载方案: (1) 首先将第一艘轮船尽可能装满; (2) 将剩余的集装箱装上第二艘轮船。

#define MaxBox 1000
int globalWeight[MaxBox], globalNum, globalC1; // 输入参数
int globalX[MaxBox],
    globalAns; // 保存状态X和最优值的全局变量
void loadingDFS(int t) {
    if (t == globalNum) { // 边界条件,判定一个n维-1向量是否是可行解 int
                          // sumWeight1=0;
        for (int i = 0; i < globalNum; i++) {
            sumWeight1 += globalX[i] * globalWeight[i];
        } // 计算装载量
        if ((sumWeight1 <= globalC1) && sumWeight1 > globalAns) {
            globalAns = sumWeight1;
        }
        return;
    } // end of if
    globalX[t] = 1;
    loadingDFS(t+1);    //扩展左子树
    globalX[t] = 0;
    loadingDFS(t+1);    //扩展右子树
}

DFS- 回溯算法 #

约束函数剪枝 #

限界函数剪枝 #

#define MaxBox 1000 int globalWeight[MaxBox], globalNum, globalC1;
int globalX[MaxBox];
int globalWt, globalBd, globalMaxWt;
void loadingBacktrack(int t) {
    if (t == globalNum) {
        globalMaxWt = globalWt;
        return;
    } // end of if
    globalBd -= globalWeight[t];
    if (globalWt + globalWeight[t] <= globalC1) {
        globalX[t] = 1;
        globalWt += globalWeight[t];
        loadingBacktrack(t + 1);
        globalWt -= globalWeight[t];
    }
    if (globalWt + globalBd > globalMaxWt) {
        globalX[t] = 0;
        loadingBacktrack(t + 1);
    }
    globalBd += globalWeight[t];
}

BFS- 分支限界算法 #

约束函数剪枝 #

限界函数剪枝 #

A* 算法 #