搜索技术

状态空间搜索：是一种通用的问题求解方法，它首先把问题描述转换为一个状态空间图，然
后设计特定的图遍历方法在状态空间中搜索问题的解。需要注意的是，为了提高搜索的效率，
在遍历状态空间时需要添加优化技术，比如剪枝策略用于尽可能避免不必要的无效搜索，启发式信息用来加速朝目标状态逼近的速度。

问题的状态空间表示

状态：

X=[x1,x2,⋯ ,xn]X=\left[x_1, x_2, \cdots, x_n\right]

状态分量：每个元素 xix_i（i=0,1,⋯ ,ni=0,1,\cdots,n）。

操作符：把一个状态转变成另一个状态的操作或者运算。

状态图：状态定义为图的结点，操作符定义为图的边，一个问题的全部可能状态则可以表示为一个图。

路径：操作符序列连接起来的状态图中的一个状态序列。

路径耗散：一条路径性能或求解问题的代价。

状态空间图：(S,A,G,F)(S,A,G,F)

  • SS：问题的初始状态。
  • AA：操作符集合。
  • GG：目标测试，目标状态的状态集合 or\text {or} 判定函数。
  • FF：路径耗散函数。

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

【传教士渡河问题】在河的左岸有三个传教士、一条船和三个野人，传教士们想用
这条船将所有的成员都运过河去，但是受到以下条件的限制：

① 教士和野人都会划船，但船一次最多只能装运两个人；

② 在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至
被吃掉。

此外，假定野人会服从任何一种过河安排，试设计出一个确保全部成员安全过河的计划。

（1）状态表示

S=(m,c,b)S=(m,c,b)：

  • mm：左岸传教士数，m={0,1,2,3}m=\{0,1,2,3\}
  • cc：左岸的野人数，c={0,1,2,3}c=\{0,1,2,3\}
  • bb：左岸渡船数，b={0,1}b=\{0,1\}

初始状态：S0=(3,3,1)S_0=(3,3,1)

目标状态：Sg=(0,0,0)S_g=(0,0,0)

（2）操作符集合

左岸 →\rightarrow 右岸：LijL_{ij}

右岸 →\rightarrow 左岸：RijR_{ij}

ii 船载的传教士数

jj 船载的野人数

F={L01,L10,L11,L02,L20,R01,R10,R11,R02,R20}F=\left\{L_{01}, L_{10}, L_{11}, L_{02}, L_{20}, R_{01}, R_{10}, R_{11}, R_{02}, R_{20}\right\}

 状态 (m,c,b) 状态 (m,c,b) 状态 (m,c,b) 状态 (m,c,b)S0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S31000\begin{array}{|c|c||c|c||c|c||c|c|} \hline \text { 状态 } & (m, c, b) & \text { 状态 } & (m, c, b) & \text { 状态 } & (m, c, b) & \text { 状态 } & (m, c, b) \\ \hline S_0 & 331 & S_8 & 131 & S_{16} & 330 & S_{24} & 130 \\ \hline S_1 & 321 & S_9 & 121 & S_{17} & 320 & S_{25} & 120 \\ \hline S_2 & 311 & S_{10} & 111 & S_{18} & 310 & S_{26} & 110 \\ \hline S_3 & 301 & S_{11} & 101 & S_{19} & 300 & S_{27} & 100 \\ \hline S_4 & 231 & S_{12} & 031 & S_{20} & 230 & S_{28} & 030 \\ \hline S_5 & 221 & S_{13} & 021 & S_{21} & 220 & S_{29} & 020 \\ \hline S_6 & 211 & S_{14} & 011 & S_{22} & 210 & S_{30} & 010 \\ \hline S_7 & 201 & S_{15} & 001 & S_{23} & 200 & S_{31} & 000 \\ \hline \end{array}

  1. 删除左岸野人数目超过传教士的情况：S4,S8,S9,S20,S24,S25S_4, S_8, S_9, S_{20}, S_{24}, S_{25}
  2. 删除右岸野人数目超过传教士的情况：S6,S7,S11,S22,S23,S27S_6, S_7, S_{11}, S_{22}, S_{23}, S_{27}
  3. 删除四种不可能的情况：
    1. 船不可能停靠在无人的岸边：S15S_{15} 和 S16S_{16}
    2. 传教士不可能在野人数量占优势的情况下把船安全划回来：S3S_3
    3. 传教士不可能在野人数量占优势的情况下把船安全划过去：S28S_{28}

综上所述，真正符合约束条件的只有 1616 个合理状态，对应状态空间图如下：

状态空间搜索算法分类：

  • 基于枚举策略的搜索
    • 深度优先搜索
    • 广度优先搜索
  • “优化+枚举”的搜索
    • 回溯算法：深度优先搜索 + 剪枝策略
    • 分支限界算法：广度优先搜索 + 剪枝策略
  • 启发式搜索：基于规则的优化搜索算法

深度优先搜索

深度优先搜索（Depth First Search,DFS\text {Depth First Search,DFS}）：给定图 G=(V,E)G=(V,E)，初始时，所有顶点均未被访问过，任选一个顶点 vv 作为源顶点，DFS\text {DFS} 先访问源顶点 vv，并将其标记为已访问过。然后从 vv 出发，选择 vv 的下一个未访问的邻接顶点（子结点），记为 ww，访问 ww 并标记为已访问过，并以 ww 为新的扩展结点，继续进行深度优先搜索。如果 ww 及其子结点均已搜索完毕，则返回到 vv，再选择 vv 的另外一个未访问的邻接点继续搜索，直到图中所有和 vv 有路径相连的顶点均已访问过为止。若此时图 GG 中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源顶点重复上述过程，直到图中所有顶点均被访问过为止。

能进则进，不进则换，无换则退

举例：给定有向图 Ga=(V,E)G_{a}=(V,E) 和无向图 Gb=(V,E)G_b=(V,E)，相关的深度优先搜索访问序列。

visted[]visted[]：标记图中的顶点是否被访问过。

依次是 {A,B,C,D,E,F,G,H,I}\{A,B,C,D,E,F,G,H,I\}

visted[]visted[] 有向图依次访问节点
{0,0,0,0,0,0,0,0,0}\{0,0,0,0,0,0,0,0,0\}
{1,0,0,0,0,0,0,0,0}\{1,0,0,0,0,0,0,0,0\} AA
{1,0,0,0,0,1,0,0,0}\{1,0,0,0,0,1,0,0,0\} FF
{1,0,0,0,1,1,0,0,0}\{1,0,0,0,1,1,0,0,0\} EE
{1,0,1,0,1,1,0,0,0}\{1,0,1,0,1,1,0,0,0\} CC
{1,0,1,1,1,1,0,0,0}\{1,0,1,1,1,1,0,0,0\} DD
{1,0,1,1,1,1,1,0,0}\{1,0,1,1,1,1,1,0,0\} GG
{1,1,1,1,1,1,1,0,0}\{1,1,1,1,1,1,1,0,0\} BB
{1,1,1,1,1,1,1,0,1}\{1,1,1,1,1,1,1,0,1\} II
{1,1,1,1,1,1,1,1,1}\{1,1,1,1,1,1,1,1,1\} HH
visted[]visted[] 无向图依次访问节点
{0,0,0,0,0,0,0,0,0}\{0,0,0,0,0,0,0,0,0\}
{1,0,0,0,0,0,0,0,0}\{1,0,0,0,0,0,0,0,0\} AA
{1,1,0,0,0,0,0,0,0}\{1,1,0,0,0,0,0,0,0\} BB
{1,1,1,0,0,0,0,0,0}\{1,1,1,0,0,0,0,0,0\} CC
{1,1,1,0,0,1,0,0,0}\{1,1,1,0,0,1,0,0,0\} FF
{1,1,1,1,0,1,0,0,0}\{1,1,1,1,0,1,0,0,0\} DD
{1,1,1,1,1,1,0,0,0}\{1,1,1,1,1,1,0,0,0\} EE
{1,1,1,1,1,1,1,0,0}\{1,1,1,1,1,1,1,0,0\} GG
{1,1,1,1,1,1,1,1,0}\{1,1,1,1,1,1,1,1,0\} HH
{1,1,1,1,1,1,1,1,1}\{1,1,1,1,1,1,1,1,1\} II

🌟基于栈的 DFS\text {DFS} ​的算法框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function DFS(problem, stack) {
    node = Make-Node(Initial-State[problem]);
    stack <- Insert(node, stack);
    do while(1) {
        if stack == Empty
            return failure;
        node <- Remove-First(stack);
        visit(node);
        if State[node] == Goal
            return Solution(node)
        sonNodes = Expand(node, problem);
        stack <- Insert-All(sonNodes, stack);
    }
    return;
}

🌟基于递归的 DFS\text {DFS} 的算法框架：

1
2
3
4
5
6
7
8
9
10
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;
}

广度优先搜索

深度优先搜索（Breadth First Search,BFS\text {Breadth First Search,BFS}）：给定图 G=(V,E)G=(V,E)，初始时，所有顶点均未被访问过，任选一个顶点 vv 作为源顶点，BFS\text {BFS} 先访问源顶点 vv，并将其标记为已访问过。然后从 vv 出发，依次选择 vv 的邻接顶点（子结点），记为 w1,w2,⋯ ,wtw_1, w_2, \cdots, w_t，访问 wi(i=1,2,⋯ ,t)w_i(i=1,2,\cdots,t) 并标记为已访问过，将其插入先进先出的队列中，然后，依次从队列头部位置取出结点标记为已访问过并拓展子结点把未访问的子结点插入队列，直到图中所有和 vv 有路径相连的顶点均已访问过为止。若此时图 GG 中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源顶点重复上述过程，直到图中所有顶点均被访问过为止。

由近及远，按层展开

举例：给定有向图 Ga=(V,E)G_{a}=(V,E) 和无向图 Gb=(V,E)G_b=(V,E)，相关的深度优先搜索访问序列。

visted[]visted[]：标记图中的顶点是否被访问过。

依次是 {A,B,C,D,E,F,G,H,I}\{A,B,C,D,E,F,G,H,I\}

visted[]visted[] 有向图依次访问节点
{0,0,0,0,0,0,0,0,0}\{0,0,0,0,0,0,0,0,0\}
{1,0,0,0,0,0,0,0,0}\{1,0,0,0,0,0,0,0,0\} AA
{1,1,0,0,0,0,0,0,0}\{1,1,0,0,0,0,0,0,0\} BB
{1,1,1,0,0,0,0,0,0}\{1,1,1,0,0,0,0,0,0\} CC
{1,1,1,1,0,0,0,0,0}\{1,1,1,1,0,0,0,0,0\} DD
{1,1,1,1,1,0,0,0,0}\{1,1,1,1,1,0,0,0,0\} EE
{1,1,1,1,1,1,0,0,0}\{1,1,1,1,1,1,0,0,0\} FF
{1,1,1,1,1,1,0,1,0}\{1,1,1,1,1,1,0,1,0\} HH
{1,1,1,1,1,1,1,1,0}\{1,1,1,1,1,1,1,1,0\} GG
{1,1,1,1,1,1,1,1,1}\{1,1,1,1,1,1,1,1,1\} II
visted[]visted[] 无向图依次访问节点
{0,0,0,0,0,0,0,0,0}\{0,0,0,0,0,0,0,0,0\}
{1,0,0,0,0,0,0,0,0}\{1,0,0,0,0,0,0,0,0\} AA
{1,1,0,0,0,0,0,0,0}\{1,1,0,0,0,0,0,0,0\} BB
{1,1,0,0,0,0,0,0,1}\{1,1,0,0,0,0,0,0,1\} II
{1,1,0,0,0,1,0,0,1}\{1,1,0,0,0,1,0,0,1\} FF
{1,1,0,0,1,1,0,0,1}\{1,1,0,0,1,1,0,0,1\} EE
{1,1,0,0,1,1,1,0,1}\{1,1,0,0,1,1,1,0,1\} GG
{1,1,1,0,1,1,1,0,1}\{1,1,1,0,1,1,1,0,1\} CC
{1,1,1,0,1,1,1,1,1}\{1,1,1,0,1,1,1,1,1\} HH
{1,1,1,1,1,1,1,1,1}\{1,1,1,1,1,1,1,1,1\} DD

🌟基于队列的 BFS\text {BFS} 的算法框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function BFS(problem, stack) {
    node = Make-Node(Initial-State[problem]);
    queue <- Insert(node, stack);
    do while(1) {
        if queue == Empty
            return failure;
        node <- Remove-First(queue);
        visit(node);
        if State[node] == Goal
            return Solution(node)
        sonNodes = Expand(node, problem);
        queue <- Insert-All(sonNodes, queue);
    }
    return;
}

回溯算法

回溯算法：状态空间搜索算法，关于问题的状态空间图，包括：

  • 问题状态：X=[x1,x2,⋯ ,xk]\boldsymbol{X}=\left[x_1, x_2, \cdots, x_k\right]
  • 约束条件：每个分量自身约束以及分量之间的约束
  • 操作符集合
  • 解空间：问题的解 (x1,x2,⋯ ,xn)\left(x_1, x_2, \cdots, x_n\right) 构成的集合

常用的剪枝策略：

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

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

基于枚举策略的深度优先搜索算法：

  1. 获取 nn 维向量 (x1,x2,⋯ ,xn)\left(x_1, x_2, \cdots, x_n\right)
  2. 测试是否是问题解

基于回溯策略的深度优先搜索算法：

  1. 构造长度为 kk 的部分向量 (x1,x2,⋯ ,xk)\left(x_1, x_2, \cdots, x_k\right)，1⩽k⩽n1 \leqslant k \leqslant n
  2. 测试是否能导出问题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Backtrack(problem, node, bestSolution) {
    if State[node] == Goal:
        return Solution(node)
    else:
        for sonNode in Next(problem, node):
            if Constraint(sonNode) and Bound(sonNode, bestSolution):
                result = Backtrack(problem, sonNode, bestSolution)
                if result != failure:
                    bestSolution = UpdateSolution(bestSolution, result)
        return bestSolution
}

function Recursive-Backtracking(problem) {
    startNode = Make-Node(Initial-State[problem])
    bestSolution = None  # Or appropriate initial value
    return Backtrack(problem, startNode, bestSolution)
}

0-1 背包问题

举例：对于n=3n=3 的 0−10-1 背包问题，背包容量 c=30c=30，每个物品重量和价值分别为：w=⟨16,15,15⟩w=\langle 16,15,15\rangle，p=⟨45,25,25⟩p=\langle 45,25,25\rangle。试构造最优的装包方案。

解析：

问题状态：

X=[x1,⋯ ,xk]\boldsymbol{X}=\left[x_1, \cdots, x_k\right]

  • 1⩽k⩽31 \leqslant k \leqslant 3，表示已经处理过的物品数目，即 1,2,⋯ ,k1,2, \cdots, k 的物品已被处理
  • xi={0,1}x_i=\{0,1\}，取值为 11 表示第 ii 号物品已装入背包，否则被抛弃

约束条件：

∑i=1kxiwi⩽C\sum_{i=1}^k x_i w_i \leqslant C

操作符：

  • 第 k+1k+1 个物品装入背包，有 xk+1=1x_{k+1}=1
  • 第 k+1k+1 个物品被抛弃，有 xk+1=0x_{k+1}=0

得到新的问题状态：

X′=[x1,x2,⋯ ,xk,xk+1]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k, x_{k+1}\right]

问题解和解空间：



3 个物品的 0-1 背包问题的完全状态空间图
$$ C_s(\boldsymbol{X})=\sum_{i=1}^k x_i w_i $$

X=[x1,x2,⋯ ,xk]\boldsymbol{X}=\left[x_1, x_2, \cdots, x_k\right]，X′=[xk+1,xk+2,⋯ ,xn]\boldsymbol{X}^{\prime}=\left[x_{k+1}, x_{k+2}, \cdots, x_n\right]，Xs=[X,X′]\boldsymbol{X}_s=\left[\boldsymbol{X}, \boldsymbol{X}^{\prime}\right]

Val(Xs)=∑i=1nxivi=∑i=1kxivi+∑i=k+1nxivi=Val(X)+Val(X′)Val\left(\boldsymbol{X}_s\right)=\sum_{i=1}^n x_i v_i=\sum_{i=1}^k x_i v_i+\sum_{i=k+1}^n x_i v_i=Val(\boldsymbol{X})+Val\left(\boldsymbol{X}^{\prime}\right)

令 Bd(X′)=∑i=k+1n1×vi⩾Val(X′)Bd\left(\boldsymbol{X}^{\prime}\right)=\sum_{i=k+1}^n 1 \times v_i \geqslant Val\left(\boldsymbol{X}^{\prime}\right) （表示将剩下 n−kn-k 个物品装入背包）

Bound(Xs)=Val(X)+Bd(X′)Bound\left(\boldsymbol{X}_s\right)=Val(\boldsymbol{X})+Bd\left(\boldsymbol{X}^{\prime}\right)

Bound(Xs)Bound\left(\boldsymbol{X}_s\right) 是 Val(Xs)Val\left(\boldsymbol{X}_s\right) 的上界

假设已找到的最优值是 BestVBestV，如果 Bound(Xs)<BestVBound\left(\boldsymbol{X}_s\right) < BestV， Xs\boldsymbol{X}_s 不可能包含最优，因此剪除以 X\boldsymbol{X} 为根的子树。

X\boldsymbol{X} X′\boldsymbol{X}^{\prime} Cs(X)⩽CC_s(\boldsymbol{X}) \leqslant C Val(X)Val\left(\boldsymbol{X}\right) Bd(X′)Bd\left(\boldsymbol{X}^{\prime}\right) Bound(Xs)Bound\left(\boldsymbol{X}_s\right) BestVBestV
[][] [1,1,1][1,1,1] 00 00 9595 9595 00
[1][1] [1,1][1,1] 1616 4545 5050 9595
[1,1][1,1] [1][1] 3131
[1,0][1,0] [1][1] 1616 4545 2525 6565
[1,0,1][1,0,1] [][] 3131 00
[1,0,0][1,0,0] [][] 1616 4545 00 4545 4545
[0][0] [1,1][1,1] 00 00 5050 5050
[0,1][0,1] [1][1] 1515 2525 2525 5050
[0,1,1][0,1,1] [][] 3030 5050 00 5050 5050
[0,1,0][0,1,0] [][] 1515 2525 00 2525
[0,0][0,0] [1][1] 00 00 2525 2525

旅行商问题

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

解析：

问题状态：

X=[x1,⋯ ,xk]\boldsymbol{X}=\left[x_1, \cdots, x_k\right]

  • k⩽4k \leqslant 4，表示已经旅行过的城市数目，即 1,2,⋯ ,k1,2, \cdots, k 的城市已经被访问过
  • xi={1,2,3,4}x_i=\{1,2,3,4\}

约束条件：每个城市最多只能访问一次，xi≠xjx_i \neq x_j，∀i≠j\forall i \neq j，i,j∈{1,…,k}i,j \in\{1, \ldots, k\}

操作符：从 n−kn-k 个城市任意选择一个作为下一个旅行的城市。

问题解和解空间：

X′=[x1,x2,⋯ ,xk] X′=[xk+1,xk+2,⋯ ,xn]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k\right] \ \boldsymbol{X}^{\prime}=\left[x_{k+1}, x_{k+2}, \cdots, x_n\right]

Xs=[X,X′]\boldsymbol{X}_s=\left[\boldsymbol{X}, \boldsymbol{X}^{\prime}\right]

Val(Xs)=∑i=1nC(xi,xi+1)+C(xn,x1)=∑i=1k−1C(xi,xi+1)+∑i=knC(xi,xi+1)+C(xn,x1)=Val(X)+Val(X′)Val\left(\boldsymbol{X}_s\right)=\sum_{i=1}^n C\left(x_i, x_{i+1}\right)+C\left(x_n, x_1\right)=\sum_{i=1}^{k-1} C\left(x_i, x_{i+1}\right)+\sum_{i=k}^n C\left(x_i, x_{i+1}\right)+C\left(x_n, x_1\right)=Val\left(\boldsymbol{X}\right) + Val\left(\boldsymbol{X}^{\prime}\right)

Val(X′)⩾0Val\left(\boldsymbol{X}^{\prime}\right) \geqslant 0

Val(Xs)⩾Val(X)Val\left(\boldsymbol{X}_s\right) \geqslant Val\left(\boldsymbol{X}\right)

Bound(Xs)=Val(X)Bound\left(\boldsymbol{X}_s\right)=Val\left(\boldsymbol{X}\right)

假设已找到的最优值是 BestVBestV，如果 Bound(Xs)⩾BestVBound\left(\boldsymbol{X}_s\right) \geqslant BestV， Xs\boldsymbol{X}_s 不可能包含最优，因此剪除以 X\boldsymbol{X} 为根的子树。

序号 X\boldsymbol{X} Val(X)Val\left(\boldsymbol{X}\right) Val(Xs)Val\left(\boldsymbol{X}_s\right) BestVBestV
AA {1}\{1\} 00 +∞+ \infty
BB {1,2}\{1,2\} 33
EE {1,2,3}\{1,2,3\} 88
KK {1,2,3,4}\{1,2,3,4\} 1010 1414 1414
FF {1,2,4}\{1,2,4\} 1818
CC {1,3}\{1,3\} 2020
DD {1,4}\{1,4\} 44
II {1,4,2}\{1,4,2\} 1919
JJ {1,4,3}\{1,4,3\} 66
PP {1,4,3,2}\{1,4,3,2\} 1111 1414 1414

🌟基于递归回溯算法框架：

1
2
3
4
5
6
7
8
9
10
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);
    	}
}

装载问题

题目描述

有 nn 个集装箱要装上 22 艘载重量分别为 C1C_1 和 C2C_2 的轮船，其中集装箱 ii 的重量为 wiw_i,，且 ∑wi⩽C1+C2\sum w_i \leqslant C_1+C_2 。请设计算法确定是否有一个合理的装载方案可将这些集装箱装上这 22 艘轮船。

输入数据

多组测试数据。每组测试数据包括两行：

  • 第一行输入集装箱数目 n（n<1000）n（n<1000），以及两艘轮船的载重 C1C_1 和 C2C_2
  • 第二行输入 nn 个整数，表示每个集装箱的重量
输出数据

如果存在合理装载方案，输出第一艘轮船的最大装载重量；否则，输出“No\text {No}”。

样例输入
1
2
3
4
3 50 50
10 40 40
3 50 50
20 40 40
样例输出
1
2
50
No

问题分析

  1. 将第一艘轮船尽可能装满；
  2. 将剩余的集装箱装上第二艘轮船。

max⁡∑i=1nwixi st. {∑i=1nwixi⩽C1xi∈{0,1},1⩽i⩽n\begin{aligned} & \max \sum_{i=1}^n w_i x_i \\ & \text { st. }\left\{\begin{array}{l} \sum_{i=1}^n w_i x_i \leqslant C_1 \\ x_i \in\{0,1\}, 1 \leqslant i \leqslant n \end{array}\right. \end{aligned}

算法实现与分析

问题状态：

X=[x1,⋯ ,xk]\boldsymbol{X}=\left[x_1, \cdots, x_k\right]

  • 1⩽k⩽n1 \leqslant k \leqslant n，表示已经处理过的集装箱数目，即 1,2,⋯ ,k1,2, \cdots, k 的集装箱已经被处理过
  • xi={0,1}x_i=\{0,1\}

约束条件：

∑i=1kxiwi⩽C1\sum_{i=1}^k x_i w_i \leqslant C_1

操作符：

  • 第 k+1k+1 个集装箱装入轮船 C1C_1，有 xk+1=1x_{k+1}=1
  • 第 k+1k+1 个集装箱不装入轮船 C1C_1，有 xk+1=0x_{k+1}=0

得到新的问题状态：

X′=[x1,x2,⋯ ,xk,xk+1]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k, x_{k+1}\right]

问题解和解空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <cmath>
#define MaxBox 1000

int num;
int C1, C2;
int weight[MaxBox];
int status[MaxBox];
int totalWeight = 0;
int maxWeight = 0;

void DFS(int);

void DFS(int depth)
{
    if (depth == num)
    {
        int sumWeight = 0;
        for (int i = 0; i < num; i++)
            sumWeight += status[i] * weight[i];
        if ((sumWeight <= C1) && sumWeight > maxWeight)
            maxWeight = sumWeight;
        return;
    }
    status[depth] = 1;
    DFS(depth + 1);
    status[depth] = 0;
    DFS(depth + 1);
}

int main()
{
    while (scanf("%d %d %d", &num, &C1, &C2) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%d", &weight[i]);
            totalWeight += weight[i];
        }
        DFS(0);
        if (totalWeight - maxWeight <= C2)
            printf("%d\n", maxWeight);
        else
            printf("No\n");
    }
    return 0;
}

DFS(0)DFS(0)：

  • status[0]=1status[0]=1，DFS(1)DFS(1)

    • status[1]=1status[1]=1，DFS(2)DFS(2)

      • status[2]=1status[2]=1，DFS(3)DFS(3)：status[]=[1,1,1]status[]=[1,1,1]

      sumWeight=1×10+1×40+1×40>C1\begin{aligned} sumWeight & = 1 \times 10 + 1 \times 40 + 1 \times 40 > C_1 \\ \end{aligned}

      • status[2]=0status[2]=0，DFS(3)DFS(3)：status[]=[1,1,0]status[]=[1,1,0]

      sumWeight=1×10+1×40+0×40=50maxWeight=sumWeight=50\begin{aligned} sumWeight & = 1 \times 10 + 1 \times 40 + 0 \times 40 = 50 \\ maxWeight & = sumWeight =50 \end{aligned}

    • status[1]=0status[1]=0，DFS(2)DFS(2)

      • status[2]=1status[2]=1，DFS(3)DFS(3)：status[]=[1,0,1]status[]=[1,0,1]

      sumWeight=1×10+0×40+1×40=50maxWeight=sumWeight=50\begin{aligned} sumWeight & = 1 \times 10 + 0 \times 40 + 1 \times 40 = 50 \\ maxWeight & = sumWeight =50 \end{aligned}

      • status[2]=0status[2]=0，DFS(3)DFS(3)：status[]=[1,0,0]status[]=[1,0,0]

      sumWeight=1×10+0×40+0×40=10<maxWeight\begin{aligned} sumWeight = 1 \times 10 + 0 \times 40 + 0 \times 40 = 10 < maxWeight \\ \end{aligned}

  • status[0]=0status[0]=0，DFS(1)DFS(1)

    • status[1]=1status[1]=1，DFS(2)DFS(2)

      • status[2]=1status[2]=1，DFS(3)DFS(3)：status[]=[0,1,1]status[]=[0,1,1]

      sumWeight=0×10+1×40+1×40=80>C1\begin{aligned} sumWeight = 0 \times 10 + 1 \times 40 + 1 \times 40 = 80 > C_1 \end{aligned}

      • status[2]=0status[2]=0，DFS(3)DFS(3)：status[]=[0,1,0]status[]=[0,1,0]

      sumWeight=0×10+1×40+0×40=40<maxWeight\begin{aligned} sumWeight = 0 \times 10 + 1 \times 40 + 0 \times 40 = 40 < maxWeight \end{aligned}

    • status[1]=0status[1]=0，DFS(2)DFS(2)

      • status[2]=1status[2]=1，DFS(3)DFS(3)：status[]=[0,0,1]status[]=[0,0,1]

      sumWeight=0×10+0×40+1×40=40<maxWeight\begin{aligned} sumWeight = 0 \times 10 + 0 \times 40 + 1 \times 40 = 40 < maxWeight \end{aligned}

      • status[2]=0status[2]=0，DFS(3)DFS(3)：status[]=[0,0,0]status[]=[0,0,0]

      sumWeight=0×10+0×40+0×40=0<maxWeight\begin{aligned} sumWeight = 0 \times 10 + 0 \times 40 + 0 \times 40 = 0 < maxWeight \end{aligned}

添加剪枝策略：

  • 约束函数剪枝：不合法状态，∑i=1kxiwi>C1\sum_{i=1}^k x_i w_i > C_1，递归搜索右子树之前不需要约束测试。
  • 限界函数剪枝：递归搜索左子树之前不需要限界测试。

Cs(X)=∑i=1kxiwiC_s(\boldsymbol{X})=\sum_{i=1}^k x_i w_i

X′=[x1,x2,⋯ ,xk] X′=[xk+1,xk+2,⋯ ,xn]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k\right] \ \boldsymbol{X}^{\prime}=\left[x_{k+1}, x_{k+2}, \cdots, x_n\right]

Xs=[X,X′]\boldsymbol{X}_s=\left[\boldsymbol{X}, \boldsymbol{X}^{\prime}\right]

Val(Xs)=∑i=1nxiwi=∑i=1kxiwi+∑i=k+1nxiwi=Val(X)+Val(X′)Val\left(\boldsymbol{X}_s\right)=\sum_{i=1}^n x_i w_i=\sum_{i=1}^k x_i w_i+\sum_{i=k+1}^n x_i w_i=Val(\boldsymbol{X})+Val\left(\boldsymbol{X}^{\prime}\right)

令 Bd(X′)=∑i=k+1n1×wi⩾Val(X′)Bd\left(\boldsymbol{X}^{\prime}\right)=\sum_{i=k+1}^n 1 \times w_i \geqslant Val\left(\boldsymbol{X}^{\prime}\right) （表示将剩下 n−kn-k 个集装箱装入轮船 C1C_1）

Bound(Xs)=Val(X)+Bd(X′)Bound\left(\boldsymbol{X}_s\right)=Val(\boldsymbol{X})+Bd\left(\boldsymbol{X}^{\prime}\right)

Bound(Xs)Bound\left(\boldsymbol{X}_s\right) 是 Val(Xs)Val\left(\boldsymbol{X}_s\right) 的上界

假设已找到的最优值是 BestVBestV，如果 Bound(Xs)<BestVBound\left(\boldsymbol{X}_s\right) < BestV， Xs\boldsymbol{X}_s 不可能包含最优，因此剪除以 X\boldsymbol{X} 为根的子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cmath>
#define MaxN 1000

int num;
int C1, C2;
int weight[MaxN];
int status[MaxN];
int totalWeight = 0;
int maxWeight = 0;
int mW = 0;
int Bd;

void Backtrack(int);

void Backtrack(int depth)
{
    if (depth == num)
    {
        maxWeight = mW;
        return;
    }
    Bd -= weight[depth];
    if (mW + weight[depth] <= C1)
    { // 约束剪枝
        status[depth] = 1;
        mW += weight[depth];
        Backtrack(depth + 1);
        mW -= weight[depth];
    }
    if (mW + Bd > maxWeight)
    { // 限界剪枝
        status[depth] = 0;
        Backtrack(depth + 1);
    }
    Bd += weight[depth];
}

int main()
{
    while (scanf("%d %d %d", &num, &C1, &C2) != EOF)
    {

        for (int i = 0; i < num; i++)
        {
            scanf("%d", &weight[i]);
            totalWeight += weight[i];
        }
        Bd = totalWeight;
        Backtrack(0);
        if (totalWeight - maxWeight <= C2)
            printf("%d\n", maxWeight);
        else
            printf("No\n");
    }
    return 0;
}

圆排列问题

题目描述

给定 nn 个大小不等的圆 C1,C2,⋯ ,CnC_1, C_2, \cdots, C_n，现要将这 nn 个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从 nn 个圆的所有排列中找出有最小长度的圆排列。

输入数据

多组测试数据，每组测试数据包括两行：

  • 第一行输入圆的个数 n(n<1000)n(n<1000)
  • 第二行输入 nn 个整数，表示每一个圆的半径
输出数据

最小长度圆排列的长度，保留小数点后 nn 位有效数字，每组测试数据输出一行。

样例输入
1
2
3
1 1 2
样例输出
1
7.6569

问题分析

问题状态：

X=[x1,⋯ ,xk]\boldsymbol{X}=\left[x_1, \cdots, x_k\right]

  • 1⩽k⩽n1 \leqslant k \leqslant n，表示已经排列过的圆数目，即 1,2,⋯ ,k1,2, \cdots, k 的圆已经排列
  • xi={1,2,⋯ ,n−1,n}x_i=\{1,2,\cdots,n-1,n\}

约束条件：每个圆最多只能出现一次，xi≠xjx_i \neq x_j，∀i≠j\forall i \neq j，i,j∈{1,…,k}i,j \in\{1, \ldots, k\}

操作符：从 n−kn-k 个圆中任意选择一个作为下一个排列的圆。

得到新的问题状态：

X′=[x1,x2,⋯ ,xk,xk+1]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k, x_{k+1}\right]

问题解和解空间：

X′=[x1,x2,⋯ ,xk] X′=[xk+1,xk+2,⋯ ,xn]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k\right] \ \boldsymbol{X}^{\prime}=\left[x_{k+1}, x_{k+2}, \cdots, x_n\right]

Xs=[X,X′]\boldsymbol{X}_s=\left[\boldsymbol{X}, \boldsymbol{X}^{\prime}\right]

Val(Xs)=Val(X)+Val(X′)Val\left(\boldsymbol{X}_s\right)=Val\left(\boldsymbol{X}\right) + Val\left(\boldsymbol{X}^{\prime}\right)

Val(X′)⩾0Val\left(\boldsymbol{X}^{\prime}\right) \geqslant 0

Val(Xs)⩾Val(X)Val\left(\boldsymbol{X}_s\right) \geqslant Val\left(\boldsymbol{X}\right)

Bound(Xs)=Val(X)Bound\left(\boldsymbol{X}_s\right)=Val\left(\boldsymbol{X}\right)

假设已找到的最优值是 BestVBestV，如果 Bound(Xs)⩾BestVBound\left(\boldsymbol{X}_s\right) \geqslant BestV， Xs\boldsymbol{X}_s 不可能包含最优，因此剪除以 X\boldsymbol{X} 为根的子树。

❗注意（假定第一个圆的圆心坐标 (x1,y1)=(0,r1)(x_1,y_1)=(0,r_1)）

  • 第一个圆未必决定左边界，最后一个圆未必决定右边界
    • 左边界 LL：L=min⁡i=1n(xi−ri)L=\min _{i=1}^n\left(x_i-r_i\right)
    • 右边界 RR：R=max⁡i=1n(xi+ri)R=\max _{i=1}^n\left(x_i+r_i\right)
1
2
3
4
5
6
7
8
9
10
11
12
13
void permLength()
{
    double high = 0, low = 0;
    for (int i = 0; i < num; i++)
    {
        if (centerX[i] + radius[i] > high)
            high = centerX[i] + radius[i];
        if (centerX[i] - radius[i] < low)
            low = centerX[i] - radius[i];
    }
    if (high - low < min)
        min = high - low;
}
  • 第 i+1i+1 个圆未必与第 ii 个圆相切

两圆相切，圆心之间的距离公式：(xi−xj)2+(yi−yj)2=(ri+rj)2\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2=\left(r_i+r_j\right)^2

第 ii 个圆的圆心坐标求法：在考虑与左边框相切后，

假定第 ii 个圆圆心坐标为 (xi,yi)(x_i,y_i)与前 i−1i-1 个圆 Circlek(1⩽k⩽i−1)Circle_k(1 \leqslant k \leqslant i-1) 圆心坐标为 (xk,yk)(x_k,y_k) 都相切：

(xi−xk)2=(ri+rk)2−(yi−yk)2\left(x_i-x_k\right)^2=\left(r_i+r_k\right)^2-\left(y_i-y_k\right)^2

xi−xk=±(ri+rk)2−(yi−yk)2x_i-x_k= \pm \sqrt{\left(r_i+r_k\right)^2-\left(y_i-y_k\right)^2}

又 xi>xkx_i > x_k

xi−xk=(ri+rk)2−(yi−yk)2x_i-x_k=\sqrt{\left(r_i+r_k\right)^2-\left(y_i-y_k\right)^2}

又 yi=riy_i=r_i，yk=rky_k=r_k

xi−xk=(ri+rk)2−(ri−rk)2x_i-x_k=\sqrt{\left(r_i+r_k\right)^2-\left(r_i-r_k\right)^2}

xi=xk+2rkrix_i=x_k + 2 \sqrt{r_kr_i} 

1
2
3
4
5
6
7
8
9
10
11
double curCenter(int depth)
{
    double temp = radius[depth] - radius[0];
    for (int k = 0; k < depth; k++)
    {
        double valuex = centerX[k] + 2.0 * sqrt(radius[k] * radius[depth]);
        if (valuex > temp)
            temp = valuex;
    }
    return temp;
}

算法实现与分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cmath>
#define MaxN 1000
#define INF 0x03F3F3F3F

int num;
double radius[MaxN];
double centerX[MaxN];
double min;

double curCenter(int depth);
void permLength();
void swap(double &circleA, double &circleB);
void Backtrack(int);

double curCenter(int depth)
{
    double temp = radius[depth] - radius[0];
    for (int k = 0; k < depth; k++)
    {
        double valuex = centerX[k] + 2.0 * sqrt(radius[k] * radius[depth]);
        if (valuex > temp)
            temp = valuex;
    }
    return temp;
}

void permLength()
{
    double high = 0, low = 0;
    for (int i = 0; i < num; i++)
    {
        if (centerX[i] + radius[i] > high)
            high = centerX[i] + radius[i];
        if (centerX[i] - radius[i] < low)
            low = centerX[i] - radius[i];
    }
    if (high - low < min)
        min = high - low;
}

void swap(double &circleA, double &circleB)
{
    double temp = circleA;
    circleA = circleB;
    circleB = temp;
}

void Backtrack(int depth)
{
    if (depth == num)
    {
        permLength();
        return;
    }
    else
    {
        for (int i = depth; i < num; i++)
        {
            swap(radius[depth], radius[i]);
            double centerx = curCenter(depth);
            if (centerx + radius[depth] + radius[0] < min)
            { // 简单剪枝，粗略估算
                centerX[depth] = centerx;
                Backtrack(depth + 1);
            }
            swap(radius[depth], radius[i]);
        }
    }
}

int main()
{
    while (scanf("%d", &num) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%lf", &radius[i]);
            centerX[i] = 0;
        }
        min = INF;
        Backtrack(0);
        printf("%.4f\n", min);
    }
    return 0;
}

分支限界

分支限界法：首先将根结点加入活结点表中，从活结点表中取出首节点作为当前拓展结点，一次性生成所有孩子结点，判断孩子结点是舍弃还是保留（舍弃不可能导致可行解或最优解的孩子结点）在活结点表中。继续从活结点表中取出首节点作为当前结点，重复上述过程，直到找到问题的解或活结点表为空。

在此过程中，每一个活结点最多只有一次机会成为扩展结点。

🌟基于队列的分支限定法的算法框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function BranchBound(problem, stack) {
    node = Make-Node(Initial-State[problem]);
    queue <- Insert(node, stack);
    do while(1) {
        if queue == Empty
            return failure;
        node <- Remove-First(queue);
        visit(node);
        if State[node] == Goal
            return Solution(node)
            while((sonNodes = Next(problem,node)) != NULL)
                if（constraint(sonNode) && bound(sonNode))
                    Insert(sonNode, queue)
    }
    return;
}

0-1 背包问题

举例：对于n=3n=3 的 0−10-1 背包问题，背包容量 c=30c=30，每个物品重量和价值分别为：w=⟨16,15,15⟩w=\langle 16,15,15\rangle，p=⟨45,25,25⟩p=\langle 45,25,25\rangle。试构造最优的装包方案。

解析：

问题状态：

X=[x1,⋯ ,xk]\boldsymbol{X}=\left[x_1, \cdots, x_k\right]

  • 1⩽k⩽31 \leqslant k \leqslant 3，表示已经处理过的物品数目，即 1,2,⋯ ,k1,2, \cdots, k 的物品已被处理
  • xi={0,1}x_i=\{0,1\}，取值为 11 表示第 ii 号物品已装入背包，否则被抛弃

约束条件：

∑i=1kxiwi⩽C\sum_{i=1}^k x_i w_i \leqslant C

操作符：

  • 第 k+1k+1 个物品装入背包，有 xk+1=1x_{k+1}=1
  • 第 k+1k+1 个物品被抛弃，有 xk+1=0x_{k+1}=0

得到新的问题状态：

X′=[x1,x2,⋯ ,xk,xk+1]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k, x_{k+1}\right]

问题解和解空间：


3 个物品的 0-1 背包问题的完全状态空间图

Cs(X)=∑i=1kxiwiC_s(\boldsymbol{X})=\sum_{i=1}^k x_i w_i

X′=[x1,x2,⋯ ,xk] X′=[xk+1,xk+2,⋯ ,xn]\boldsymbol{X}^{\prime}=\left[x_1, x_2, \cdots, x_k\right] \ \boldsymbol{X}^{\prime}=\left[x_{k+1}, x_{k+2}, \cdots, x_n\right]

Xs=[X,X′]\boldsymbol{X}_s=\left[\boldsymbol{X}, \boldsymbol{X}^{\prime}\right]

Val(Xs)=∑i=1nxivi=∑i=1kxivi+∑i=k+1nxivi=Val(X)+Val(X′)Val\left(\boldsymbol{X}_s\right)=\sum_{i=1}^n x_i v_i=\sum_{i=1}^k x_i v_i+\sum_{i=k+1}^n x_i v_i=Val(\boldsymbol{X})+Val\left(\boldsymbol{X}^{\prime}\right)

令 Bd(X′)=∑i=k+1n1×vi⩾Val(X′)Bd\left(\boldsymbol{X}^{\prime}\right)=\sum_{i=k+1}^n 1 \times v_i \geqslant Val\left(\boldsymbol{X}^{\prime}\right) （表示将剩下 n−kn-k 个物品装入背包）

Bound(Xs)=Val(X)+Bd(X′)Bound\left(\boldsymbol{X}_s\right)=Val(\boldsymbol{X})+Bd\left(\boldsymbol{X}^{\prime}\right)

Bound(Xs)Bound\left(\boldsymbol{X}_s\right) 是 Val(Xs)Val\left(\boldsymbol{X}_s\right) 的上界

假设已找到的最优值是 BestVBestV，如果 Bound(Xs)<BestVBound\left(\boldsymbol{X}_s\right) < BestV， Xs\boldsymbol{X}_s 不可能包含最优，因此剪除以 X\boldsymbol{X} 为根的子树。

装载问题

装载问题的广度优先搜索算法程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#define MaxN 1000

struct node
{
    int id;
    int weight;
};

int num;
int C1, C2;
int weight[MaxN];
int totalWeight = 0;
int maxWeight = 0;

std::queue<node> nodeQueue;

void BFS();

void BFS()
{
    node headNode, sonNode;
    headNode.weight = 0;
    headNode.id = -1;
    nodeQueue.push(headNode);
    while (!nodeQueue.empty())
    {
        headNode = nodeQueue.front();
        if (headNode.id == num)
        {
            if ((headNode.weight <= C1) && (headNode.weight > maxWeight))
                maxWeight = headNode.weight;
        }
        else
        {
            sonNode.id = headNode.id + 1;
            sonNode.weight = headNode.weight + weight[sonNode.id];
            nodeQueue.push(sonNode);
            sonNode.weight = headNode.weight;
            nodeQueue.push(sonNode);
        }
        nodeQueue.pop();
    }
}

int main()
{
    while (scanf("%d %d %d", &num, &C1, &C2) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%d", &weight[i]);
            totalWeight += weight[i];
        }
        BFS();
        if (totalWeight - maxWeight <= C2)
            printf("%d\n", maxWeight);
        else
            printf("No\n");
    }
    return 0;
}

添加剪枝策略：

  • 约束函数剪枝：不合法状态，∑i=1kxiwi>C1\sum_{i=1}^k x_i w_i > C_1，递归搜索右子树之前不需要约束测试。
  • 限界函数剪枝：递归搜索左子树之前不需要限界测试。

Cs(X)=∑i=1kxiwiC_s(\boldsymbol{X})=\sum_{i=1}^k x_i w_i

X=[x1,x2,⋯ ,xk]\boldsymbol{X}=\left[x_1, x_2, \cdots, x_k\right]，X′=[xk+1,xk+2,⋯ ,xn]\boldsymbol{X}^{\prime}=\left[x_{k+1}, x_{k+2}, \cdots, x_n\right]，Xs=[X,X′]\boldsymbol{X}_s=\left[\boldsymbol{X}, \boldsymbol{X}^{\prime}\right]

Val(Xs)=∑i=1nxiwi=∑i=1kxiwi+∑i=k+1nxiwi=Val(X)+Val(X′)Val\left(\boldsymbol{X}_s\right)=\sum_{i=1}^n x_i w_i=\sum_{i=1}^k x_i w_i+\sum_{i=k+1}^n x_i w_i=Val(\boldsymbol{X})+Val\left(\boldsymbol{X}^{\prime}\right)

令 Bd(X′)=∑i=k+1n1×wi⩾Val(X′)Bd\left(\boldsymbol{X}^{\prime}\right)=\sum_{i=k+1}^n 1 \times w_i \geqslant Val\left(\boldsymbol{X}^{\prime}\right) （表示将剩下 n−kn-k 个集装箱装入轮船 C1C_1）

Bound(Xs)=Val(X)+Bd(X′)Bound\left(\boldsymbol{X}_s\right)=Val(\boldsymbol{X})+Bd\left(\boldsymbol{X}^{\prime}\right)

Bound(Xs)Bound\left(\boldsymbol{X}_s\right) 是 Val(Xs)Val\left(\boldsymbol{X}_s\right) 的上界

假设已找到的最优值是 BestVBestV，如果 Bound(Xs)<BestVBound\left(\boldsymbol{X}_s\right) < BestV， Xs\boldsymbol{X}_s 不可能包含最优，因此剪除以 X\boldsymbol{X} 为根的子树。

装载问题的分支限界算法程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#define MaxN 1000

struct node
{
    int id;
    int weight;
    int bd;
};

int num;
int C1, C2;
int weight[MaxN];
int totalWeight = 0;
int maxWeight = 0;

std::queue<node> nodeQueue;

void BranchBound();

void BranchBound()
{
    node headNode, sonNode;
    headNode.id = -1;
    headNode.weight = 0;
    headNode.bd = totalWeight;
    nodeQueue.push(headNode);
    while (!nodeQueue.empty())
    {
        headNode = nodeQueue.front();
        if (headNode.id == num)
        {
            if ((headNode.weight <= C1) && (headNode.weight > maxWeight))
                maxWeight = headNode.weight;
        }
        else
        {
            sonNode.id = headNode.id + 1;
            sonNode.weight = headNode.weight + weight[sonNode.id];
            sonNode.bd = headNode.bd - weight[sonNode.id];
            if (sonNode.weight <= C1)
            {
                nodeQueue.push(sonNode);
                maxWeight = sonNode.weight;
            }
            sonNode.weight = headNode.weight;
            if (sonNode.weight + sonNode.bd > maxWeight)
                nodeQueue.push(sonNode);
        }
        nodeQueue.pop();
    }
}

int main()
{
    while (scanf("%d %d %d", &num, &C1, &C2) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%d", &weight[i]);
            totalWeight += weight[i];
        }
        BranchBound();
        if (totalWeight - maxWeight <= C2)
            printf("%d\n", maxWeight);
        else
            printf("No\n");
    }
    return 0;
}

启发式搜索

评估函数 ff：状态描述的实数值函数，帮助选择下一个要扩展的最佳结点。

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

  • f(n)f(n)：经过结点 nn 的从开始结点到目标结点的最佳路径成本估计
  • g(n)g(n)：从初始结点到结点 nn 的路径成本
  • h(n)h(n)：从结点 nn 到目标结点的最佳路径成本估计【未知】

h∗(n)h^*(n)：从结点 nn 到目标结点的最佳路径成本。

AA 算法：基于评估函数的启发式搜索算法。

A∗A^{*} 算法：满足 h(n)⩽h∗(n)h(n) \leqslant h^*(n) 的启发式搜索算法。

相关定理：

定理 1\text {1}：如果状态空间图和 h(n)h(n) 具有满足稳定条件，即：

  1. 图中的每个结点的后继结点是有限的。
  2. 图中的弧的代价都大于某个正数 ε\varepsilon。
  3. 对图中的所有结点 nn，满足 h(n)⩽h∗(n)h(n) \leqslant h^*(n)。

并且状态空间图中存在一条从开始结点 ss 到目标结点 gg 的有限代价的路径，那么 A∗A^* 算法
总是在 ss 到 gg 的最佳路径上停止搜索，也称之为 A∗A^* 算法是可采纳的。

定理 2\text {2}：在任意状态空间图中，如果 nn 是 n′n^{\prime} 的后继，而且满足三角不等关系式,，即 h(n)⩽h(n′)+c(n,n′)h(n) \leqslant h\left(n^{\prime}\right)+c\left(n, n^{\prime}\right), 其中 c(n,n′)c\left(n, n^{\prime}\right) 表示连接 nn 与 n′n^{\prime} 的边的权重，则称 hh 满足单调条件。对于满足单调条件的 A∗A^* 算法，当算法扩展到结点 nn 时, 则表明它已经找到了到达结点 nn 的一条最优路径。

定理 3\text {3}：如果 A∗A^* 算法有两个版本 A2\mathrm{A}_2 和 A1\mathrm{A}_1，其差别是：对所有的非目标结点：h1<h2h_1<h_2，那么 A2\mathrm{A}_2 比 A1\mathrm{A}_1 更灵通，也就是说，对任意一个状态空间图，如果存在从开始结点 ss 到目标结点的一条路径，在搜索终止时，被 A2\mathrm{A}_2 扩展过的结点也被 A1\mathrm{A}_1 扩展过。

定理 作用
定理 1\text {1} 可行性
定理 2\text {2} 单调性
定理 3\text {3} 性能比较

启发式搜索：维护 Open\text {Open} 集（未探索的节点）和 Closed\text {Closed} 集（已探索的节点）两个集合：算法从 Open\text {Open} 集中选取一个节点，然后探索其合法的子节点。根据子节点的估价值，可能会将其加入 Open\text {Open} 集，或者更新已存在于 Open\text {Open} 集或 Closed\text {Closed} 集中的估价值。搜索继续进行直到找到目标状态，或者 Open\text {Open} 集为空时结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
HeuristicSearch(){
    Open = [初始状态节点];
    Closed = [];
    while (Open 集非空) {
        从 Open 中取得一个节点 X，并从 OPEN 集中删除。
        if (X 是目标状态) {
            寻得路径 PATH;
            返回路径 PATH;
        }
        for (每一个 X 的合法子节点 Y) {
            if (Y 不在 OPEN 集和 CLOSED 集中) {
                设置 Y 的估价值;
                将 Y 插入 OPEN 集中;
            } else if (Y 在 OPEN 集中) {
                if (Y 的估价值小于 OPEN 集的估价值) {
                    更新 OPEN 集中的估价值;
                }
            } else {
                if (Y 的估价值小于 CLOSED 集的估价值) {
                    更新 CLOSED 集中的估价值;
                    将 CLOSED 集中移出节点，插入到 OPEN 集;
                }
            }
        }
        将 X 插入到 CLOSED 集中;
        按估价值递减 OPEN 集中的节点排序;
    }
}

八数码问题

举例：在一个 3×33 \times 3 的九宫中有 1∼81 \sim 8 八个数及一个空格（位置随机）。设计一个算法把九宫状态从一个状态调整到另一个状态 a⇒b\text {a} \Rightarrow b。调整规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。

解析：

评估函数：

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

  • g(n)g(n)：初始状态到当前结点 nn 的空格移动次数
  • h(n)h(n)：结点 nn 中不在正确位置的数码个数

假设 h∗(n)h^*(n)：结点 nn 到目标状态的空格移动次数

易得 h(n)⩽h∗(n)h(n) \leqslant h^*(n)



八数码问题的启发式搜索过程示意图

装载问题

装载问题启发式搜索算法程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#define MaxN 1000

struct node
{
    int id;
    int g;
    int h;
    bool operator<(const node &another) const
    {
        return g + h < another.g + another.h;
    }
};

int num;
int C1, C2;
int weight[MaxN];
int totalWeight = 0;
int maxWeight = 0;

std::priority_queue<node> nodeQueue;

void Heuristic();

void Heuristic()
{
    node headNode, sonNode;
    headNode.id = -1;
    headNode.g = 0;
    headNode.h = totalWeight;
    nodeQueue.push(headNode);
    while (!nodeQueue.empty())
    {
        headNode = nodeQueue.top();
        if (headNode.id == num)
            maxWeight = headNode.g;
        else
        {
            sonNode.id = headNode.id + 1;
            sonNode.g = headNode.g + weight[sonNode.id];
            sonNode.h = headNode.h - weight[sonNode.id];
            if (sonNode.g <= C1)
                nodeQueue.push(sonNode);
            sonNode.g = headNode.g;
            nodeQueue.push(sonNode);
        }
        nodeQueue.pop();
    }
    return;
}

int main()
{
    while (scanf("%d %d %d", &num, &C1, &C2) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%d", &weight[i]);
            totalWeight += weight[i];
        }
        Heuristic();
        if (totalWeight - maxWeight <= C2)
            printf("%d\n", maxWeight);
        else
            printf("No\n");
    }
    return 0;
}