Intro #
问题求解与搜索算法 #
问题求解涉及到两个方面:
-
- 问题的表示，比如枚举对象、状态表示
-
- 求解的方法，比如自顶向下的递归，自底向上的动态规划
搜索算法是一种通用的问题求解方法: 首先把问题表示 转换为一个状态空间图，然后设计特定的图遍历方法在状态空间中搜索问题的答案。
为了提高搜索的效率，在遍历状态空间时需要添加优化技术，比如剪枝策略用于尽可能避免无效搜索，启发式信息用来加速朝目标状态逼近的速度。
状态空间图 #
一个问题用搜索算法求解时，往往需要把问题描述为状态空间图，包括以下要素
- 状态 (State): 是为描述某类不同事物间的差别而引入的一组最少变量的有序集合，其矢量 形式为: 1 2 n ，其中每个分量 i 称为状态分量。
- 操作符 (运算符): 是指把一个状态转换为另外一个状态的操作或者运算。操作符可以是规划、数学运算和问题场景中行为等。
- 状态图: 如果把状态定义为图的结点，操作符定义为图的边，一个问题的全部可能状态则可 以表示为一个图，即状态图。
- 路径: 通过操作符序列连接起来的状态图中的一个状态序列。
- 路径耗散函数: 定义在路径上的一个数值函数，它反映了一条路径的性能度量或者求解问题 的代价。在求解最优化问题时，路径耗散函数往往与优化目标相关联。
状态空间图可以形式化地定义为一个四元组 (S，A，G，F)
- S 表示问题的初始状态，它是搜索的起点。
- A 是采取的操作符集合，初始状态和操作符隐含地定义了问题的状态图。
- G 表示目标测试，它判断给定的状态是否为目标状态。它可以是表示目标状态的一个状态集合，也可以是一个判定函数。
- F 代表路径耗散函数，它的定义需要具体问题具体分析。
搜索就是在状态空间图中从初始状态出发，执行特定的操作，试探地寻找目标状态的过 程。当然，也可以从目标结点到初始结点反向进行。状态空间图中从初始状态到目标状 态的路径则代表问题的解。解的优劣由路径耗散函数量度，最优解就是路径耗散函数值 最小的路径。
搜索算法类型 #
基于枚举的通用搜索 #
DFS #
深度优先搜索 (Depth First Search, DFS) 是一种通用的图和树的遍历方法，给 定图𝐺 = (𝑉, 𝐸)，深度优先搜索的基本思想为:
- 初始化
- 任选一个结点𝑣作为源结点，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 基本思想为
- 初始化
- 任选一个结点𝑣作为源结点， BFS 先访问源结点𝑣，并将其标记为已访问
- 由近及远，按层展开
- 层次遍历
- 从𝑣出发，依次访问𝑣的邻接点:𝑤1,𝑤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)
sonNodes = Expend(node, problem);
queue ← Insert-All(sonNodes, queue) //依次插入所有子状态
枚举 + 优化的通用搜索 #
回溯算法 #
深度优先搜索是一种依照“能进则进，不进则退”的策略进行的枚举算法，也就 意味着它可能遍历整个状态空间图，导致算法效率不高。给定一个问题的状态空 间表示，设计搜索算法时需要考虑以下两个事实:
- 并不是所有的状态都是合法状态
- 并不是所有的状态都能达到目标状态
回溯算法 = 深度优先搜索 + 剪枝策略
回溯算法需要定义问题的状态空间图，包括以下四个方面:
- 问题的状态表示: 一般用 k 元组表示，即𝑋 = [𝑥1, 𝑥2, ⋯ , 𝑥𝑘]，其中向量的维度，以及每一个分量的值域是状态表示的关键问题
- 约束条件:X 中每一个分量自身的取值约束; 分量之间的取值约束。注意: 约束条件是 剪枝策略的基础，需要深入分析和挖掘
- 操作符集合: 从一个状态转换到另外一个状态的操作，在状态空间图中它构成边集。
- 问题解和解空间: 问题的解可以认为是一类特殊的状态，即目标状态。对于问题的一个 实例，所有满足约束条件的解向量就构成该问题实例的解空间。
注意: 在回溯算法中，状态空间图并不是显式地构造，也就是说，并没有在内存中生成一个完整的状态空间图。实际上，回溯算法只是根据初始状态，目标状态和操作符集合 (它产生后续状态)，隐式地构造状态空间图。
剪枝策略
回溯算法需要设计合适的剪枝策略，尽量避免不必要的搜索。常用的剪枝策略包括两大类:
- 约束函数剪枝: 根据约束条件，状态空间图中的部分状态可能是不合法 的。因此，在状态空间图中以不合法状态为根的子图/子树是不可能包 含可行解的，故其子空间不需要搜索。
- 限界函数剪枝: 这种策略一般应用于最优化问题。假设搜索算法当前访 问的状态为𝑆，且存在一个判定函数: 它能判定以𝑺为根的子图/子树不 可能包含最优解，因此该子图/子树可以剪除而无需搜索
约束函数剪枝 可以剪除状态空间图中的不可行解
限界函数剪枝 用于剪除状态空间图中的可行但是非最优的解
| 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 循环执行完毕则回溯到父结点。
分支限界法 #
广度优先搜索是一种依照“由近及远，按层展开”的策略进行的枚举算法，也就 意味着它需要遍历整个状态空间图，导致算法效率不高。给定一个问题的状态空 间表示，设计搜索算法时需要考虑以下两个事实：
- 并不是所有的分支都包含可行解
- 并不是所有的分支都包含最优解
扩展子结点时，一次性生成它的 所有孩子结点，判断孩子结点是 舍弃还是保存?舍弃那些不可能 导致可行解或最优解的孩子结点， 其余的结点进入队列中
分支限界算法 = 广度优先搜索 + 剪枝策略
分支限界算法需要定义问题的状态空间图，包括以下四个方面:
- 问题的状态表示: 逻辑上用 k 元组表示，即𝑋 = [𝑥1, 𝑥2, ⋯ , 𝑥𝑘]，其中向量的维度，以及每 一个分量的值域是状态表示的关键问题
- 约束条件:X 中每一个分量自身的取值约束; 分量之间的取值约束。注意: 约束条件是 剪枝策略的基础，需要深入分析和挖掘
- 操作符集合: 从一个状态转换到另外一个状态的操作，在状态空间图中它构成边集。
- 问题解和解空间: 问题的解可以认为是一类特殊的状态，即目标状态。对于问题的一个 实例，所有满足约束条件的解向量就构成该问题实例的解空间。
注意: 在分支限界算法中，状态空间图并不是显式地构造，也就是说，并没有在内存中生成一个完整的状态空间图。实际上，分支限界算法只是根据初始状态，目标状态和操作符集合 (它产生后续状态)，隐式地构造状态空间图。
约束函数剪枝
- 根据约束条件，状态空间图中的部分状态可能是不合法 的。因此，在状态空间图中以不合法状态为根的分支不包含可行解，故 其分支可以剪枝。
限界函数剪枝
- 这种策略一般应用于最优化问题。假设搜索算法当前访 问的状态为𝑆，且存在一个判定函数: 它能判定以𝑺为根的分支不包含最 优解，因此该分支可以剪除而无需搜索
约束函数剪枝 可以剪除状态空间图中的不可行解
限界函数剪枝 用于剪除状态空间图中的可行但是非最优的解
| 1 | BFS | 分支限界算法 |
|---|---|---|
| 图搜索视角 | 遍历整棵完全二叉树 | 添加剪枝策略，尽量限制搜索无效的分支 |
| 枚举视角 | 全局判定 [𝑥1,𝑥2,⋯,𝑥n] | 局部预判 [𝑥1,?, ?, ⋯] [𝑥1,𝑥2,?, ⋯] |
分支限界算法设计通常包含以下 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);
}
}
启发式搜索 #
最佳优先搜索 #
最佳优先搜索
-
挖掘每一个状态描述估计其“启发值”，评估状态逼近目标状态的优势
-
设计评估函数 f(N)，估计状态 N 的启发值 (一般为实数)，既有 f(N) >= 0 一般的， f(N) 估计结点的成本， f(N) 越小，结点 N 更有利于逼近目标状态
-
最佳优先搜索则按照结点的评估值 f(N) 进行升序排列，优先扩展评估值比较小的结点如果多个结点的启发值 f(N) 相同，则这些结点随机排列
-
“最佳”不代表当前搜索路径是最优的
-
“最佳优先搜索”不一定能产生最优路径
评估函数设计
- 评估函数 f(N) 的两种常见设计策略:
- 经过结点 N 的路径的成本
- f(N) = g(N) + h(N), 要求:
- g(N) 表示从初始状态到状态 N 的成本
- h(N) 表示从状态 N 到目标状态的成本估计
- f(N) = g(N) + h(N), 要求:
- 从状态 N 到目标状态的成本
- f(N) = h(N) → 贪心策略
- 经过结点 N 的路径的成本
- 理论上评估函数可以是任何值域为正数的函数 f(N)，但是不见得所有 函数对于搜索算法有帮助。
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
- OPEN 表用来存放活结点表，一 般用优先队列实现;
- CLOSE 表保存已扩展结点，它 用于求解最优路径，用线性表 实现;
- 如果问题不需要求解最优路径， 而只需要最优值时，CLOSE 表可以省略。
启发式搜索
选择下一个扩展结点的策略总是选择评估函数 𝑓(∙) 值最 小的状态结点作为新扩展结点。
$$f (n) = g(n) + h(n)$$
- BFS 与分支限界法
- 如果𝑔(𝑛) 表示结点𝑛在解空间树中的深度, h(𝑛) = 0
- DFS 与回溯法
- 如果𝑔(𝑛) = 0，h(𝑛) 的定义满足:m 是 n 的儿子结点，则 h(𝑚) < h(𝑛)
- A* 算法
- 满足 h(𝑛) ≤ h∗(𝑛) ，其中 h∗(𝑛) 表示结点𝑛到目标结点的最佳路径成本
A* 算法 #
启发式搜索选择下一个扩展结点的策略总是选择评估函数 𝑓(∙) 值最小的状态结 点作为新扩展结点。
$$f (n) = g(n) + h(n)$$
如果𝒈(𝒏) 表示从初始状态到状态 N 的成本，𝒉(𝒏) 表示从状态 N 到目标状态的成本估计，𝒉∗(𝑵) 是从状态结点 N 到目标状态的最优路径成本，满足: $$𝟎 ≤ 𝒉(𝑵) ≤ 𝒉∗(𝑵)，𝒘(𝑁,𝑁’) ≥𝜖> 0$$ 其中𝑤(𝑁, 𝑁’) 表示任何两个状态之间的路径成本，要求大于 0。则最佳优先搜索得到 的解总是最优解，对应搜索算法称之为 A* 算法。 如果 N 是目标状态 G，则定义𝐻(𝐺) = 0。
A 算法的最优性证明*
- 【可采纳性定理】如果问题生成的状态空间图 G 和 h(𝑛) 满足稳定条件，即:
- 1 图中的每个结点的后继结点是有限的;
- 2 图中的弧的代价都大于某个正数𝜺 ;
- 3 对图中的所有结点𝑛，满足 h(𝑛) ≤ h∗(𝑛) ，即估计成本不会超过实际成本。 并且状态空间图中存在一条从开始状态结点𝑠到目标状态结点𝑔的有限代价的路径， 那么 A算法总是在𝒔到𝒈的最佳路径上停止搜索，也称之为 A算法是可采纳的。
- 证明思路
- Step1: 如果问题存在可行解，则 A* 算法终止且返回可行解
- Step2: 当 A* 算法扩展到目标状态 g 时，则其扩展路径对应最优解
对抗搜索 #
小结 #
搜索算法的基本原理
- 问题表示的状态空间图
- 状态表示
- 操作集合
- 路径/路径耗散函数
- 在状态空间图中搜索从初 始状态到目标状态的路径/ 最优路径。
常用的搜索策略
- 基于枚举的通用搜索
- 深度优先搜索
- 广度优先搜索
- 基于“枚举 + 优化”的通用搜索
- 回溯算法
- 分支限界法
- 基于规则的启发式搜索
- 最佳优先搜索
- A* 算法
e.g.s #
传教士问题 #
在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运 过河去，但是受到以下条件的限制:
1 教士和野人都会划船，但船一次最多只能装运两个;
2 在任何岸边野人数目都不得超过传教士，否则传教士会遭遇危险:被野人攻击甚至吃掉。 此外，假定野人会服从任何一种过河安排，试设计出一个确保全部成员安全过河的计划。
-
- 状态表示
- 确定问题的状态表示，以及每一个状态变量的值域。 渡河问题包括三类对象: 传教士，野人和渡船，得三元组𝑺 =(𝒎,𝒄,𝒃)，其中:
- m 为左岸传教士数，有𝑚 ={0,1,2,3}; 对应右岸的传教士数为 3-𝑚。
- c 为左岸的野人数，有𝑐 ={0,1,2,3}; 对应右岸野人数为 3-𝑐。
- b 为左岸渡船数，有𝑏 = {0, 1}，右岸的船数为 1 − 𝑏。
- 初始状态只有一个，即𝑆0 =(3,3,1)，表示全部成员在河的左岸; 目标状态也只一 个，即 𝑆𝑔 =(0,0,0)，表示全部成员从河左岸渡河完毕。
-
- 操作符集合
- 把船从左岸划向右岸定义为𝐿𝑖𝑗操作，第一下标𝑖表示船载的传教士数, 第二下标𝑗表示船载 的野人数。
- 从右岸将船划回左岸称之为𝑅𝑖𝑗操作，下标的定义同前。 ➢ 则共有 10 种操作，操作集为
- F={L01，L10，L11，L02，L20，R01，R10，R11，R02，R20}
-
- 状态表示: 𝑺 = (𝒎, 𝒄, 𝒃)
- 初始状态𝑆0 =(3,3,1)，目标状态𝑆𝑔 =(0,0,0)
-
- 操作符集合
- F = {L01，L10，L11，L02，L20，R01，R10，R11，R02，R20}
8 数码问题 #
把左图的 8 数码排列通过空格的 上下左右移动，转换为右图的 8 数码排列
- 状态表示 数字格与空格组成的排列
- 操作符集合 空格向上、下、左和右移动
- 路径耗散函数
- 每一次移动代价为 1，路径耗散等于移 动次数
背包问题 #
【例-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* 算法 #
