一个三维装箱问题的搜索树算法

作者: 胡拉哥 | 来源:发表于2020-01-12 08:40 被阅读0次

一个三维装箱问题的搜索树算法
世界级难题：把不同物品装进箱子，如何使箱子表面积最小？
一些三维装箱问题
7.9图的应用：最小生成树
装箱问题
MCTS树学习
第一节人工智能的定义
从零开始再造打爆李世石的AlphaGo：使用蒙特卡洛树搜索实现围
图论（六）图的深度优先遍历DFS(非递归方式)
二叉搜索树

三维装箱问题的业务场景可以参考<电商业务中的纸箱推荐问题>. 文中考虑了如下问题.

输入 : 长宽高为 $(L, W, H)$ 的箱子和 $n$ 个物品, 其长宽高为 $(l_i, w_i, h_i)$ , $i=1,2,\ldots,n$ . 假设物品是长方体, 长度不可变(没有弹性). 装箱时可以对商品进行90度旋转, 但不能倾斜.
输出 : 判断所有物品是否能装入箱子.

本文提供一个基于搜索树的精确算法. 基本思想是把三维装箱问题归约(Reduce)到一个有向无环图(Directed Acyclic Graph)上的问题. 算法搜索到一个符合约束条件的有向无环图则返回true, 否则返回false.

物品的位置

如下图所示, 考虑任意一个物品(或者箱子), 我们可以用 $a$ , $b$ 两点的三维坐标描述其位置和大小. 设 $a=(x_a,y_a,z_a)$ , 那么 $b=(x_a+L, y_a+W, z_a+H)$ , 其中 $L, W, H$ 是物品的长宽高. 为了方便描述, 我们用 $a$ 点的坐标表示物品的位置.

有向无环图

假设所有物品能够被装入箱子中. 此时我们考虑一种可行的摆放方式. 对两个物品 $i \neq j$ , 分别考虑 $x, y, z$ 轴方向物品之间的相对位置关系.

首先考虑 $x$ 轴方向, $i$ 和 $j$ 只有两种位置关系

$i$ 在 $j$ 的左边, 即 $x_i \leq x_j$ , 其中 $x_i, x_j$ 为物品在 $x$ 轴的坐标;
$i$ 在 $j$ 的右边, 即 $x_i > x_j$ .

下面我们构造有向图 $D_x = (V, u^x, A_x)$ . 其中

$V=\{1, 2, \ldots, n\}$ 是所有物品的集合.
$u^x$ 为顶点权重的集合, 即 $u^x_i=l_i$ , $\forall i=1, 2, \ldots, n$ .
$A_x$ 为弧(Arc)的集合. 如果 $i$ 在 $j$ 的左边, 则 $(i, j)\in A_x$ , 否则 $(j,i)\in A_x$ (如下图所示).
注意: 如果 $(i, j), (j,k) \in A_x$ , 则 $(i,k)\in A_x$ . 换句话说, $D_x$ 无环.

令 $S_x, T_x$ 分别代表 $D_x$ 中入度(in-degree)为0和出度(out-degree)为0的点集. 以上图为例, $S_x = \{1, 2\}$ (蓝色的点), $T_x=\{4, 6, 7\}$ (红色的点). 对任意的 $s\in S_x$ , $t\in T_x$ , 用 $P^x_{s,t}$ 代表从 $s$ 到 $t$ 的路径. 令 $u(P^x_{s,t})$ 代表 $P^x_{s,t}$ 中顶点的总权重, 即
$u(P^x_{s, t}) = \sum_{i\in P^x_{s,t}}{u^x_i} = \sum_{i\in P^x_{s,t}}{l_i}.$

考虑到装入箱子的物品总长度不能超过箱子的长, 我们要求 $\max_{s\in S_x, t\in T_x} u(P^x_{s, t}) \leq L$ .

用类似的方法考虑 $y$ 轴和 $z$ 轴方向并构造 $D_y=(V, u^y, A_y)$ 和 $D_z=(V,u^z, A_z)$ , 其中

$u^y_i=w_i$ , $u^z_i=h_i$ , $i=1, 2, \ldots, n$ .
$(i, j) \in A_y$ 表示 $i$ 在 $j$ 的后方(反之 $i$ 在 $j$ 的前方).
$(i, j) \in A_z$ 表示 $i$ 在 $j$ 的下方(反之 $i$ 在 $j$ 的上方).

下面我们得到所有物品能装入箱子的充要条件:

$G=(V, E(A_x\cup A_y \cup A_z))$ 是一个团(Clique), 其中记号 $E(A)$ 代表有向边集合 $A$ 对应的无向边集合.
$\max_{s\in S_x, t\in T_x} u(P^x_{s, t}) \leq L$ .
$\max_{s\in S_y, t\in T_y} u(P^y_{s, t}) \leq W$ .
$\max_{s\in S_z, t\in T_z} u(P^z_{s, t}) \leq H$ .

搜索策略

结合前文的讨论, 我们先总结分支的因素:

需要比较任意两个物品之间的相对位置, 共有 $C_n^2$ 种情况.
两个物品之间共有6种相对位置关系: 左右, 后前, 下上.
每种物品最多有6种不同的摆放方式: $(l, w, h), (l, h, w), (w, l, h), (w, h, l), (h, l, w), (h, w, l)$ .

用 $I_k (1\leq k \leq n)$ 表示一个装箱问题的实例, 其中物品集合为 $\{1, 2, \ldots, k\}$ . 我们搜索的策略是用深度优先的方式依次判断 $I_1, I_2, \ldots, I_n$ 的可行性. 设 $I_k$ 可行. 考虑 $I_{k+1}$ 时, 我们需要对比 $(1, k+1), (2, k+1), \ldots, (k, k+1)$ . 此外, 对每个物品对(pair) $(i, k+1)$ , $1\leq i\leq k$ , 我们要考虑 $6\times 6 = 36$ 种相对位置和排放方式. 因此, 对 $I_k$ 的任意一搜索节点, 它的分支数量是 $36k$ (示意图如下).

说明 : 从根节点root开始搜索. 第一层是判断 $I_1$ 是否可行, 由于 $I_1$ 包含1个物品, 因此只需要考虑6种摆放方式, 即 $(1)^1, \ldots, (1)^6$ ; 第二层判断 $I_2$ 是否可行, 需要比较两个物品 $(1, 2)$ , 其中每个节点有36个分支, 对应6种相对位置关系和物品2的六种摆放方式的组合; 第三, 四层判断 $I_3$ 是否可行, 需要比较 $(1,3)$ 和 $(2,3)$ ; 依次类推.

注意 : 分支前必须检查两个物品间是否已经有位置关系, 若有, 则当前节点不需要分支(确保无环). 例如, 如果物品1在物品2的左边, 物品2在物品3的左边, 那么物品1一定在物品3的左边, 因此无需比较物品3在物品1左边的情况.

优化策略

物品的排序比较重要. 直观的做法是把物品按照体积由大到小排序.
物品的摆放方式实际上是1-6种. 如果物品是立方体, 则只需要考虑1种摆放方式. 在实际中应该额外考虑三边相同和两边相同的情况.
判定 $I_2$ 时可以考虑物品的对称性, 因此相对位置只要考虑左, 后, 下.
比较物品间的相对位置时按照"从外到内"的原则, 即右, 前, 上, 左, 后, 下.

可行性判定

考虑三维装箱实例 $I_k$ , $1\leq k\leq n$ . 令 $D^k_x, D^k_y, D^k_z$ 为 $x,y,z$ 轴方向的有向无环图. 令 $D^k=(D^k_x, D^k_y, D^k_z)$ . 如上图所示, 我们的搜索过程需要判断 $D^1, D^2, \ldots, D^n$ 的可行性. 考虑 $D^k$ : 顶点个数是 $3k$ , 边的个数是 $O(k^2)$ , 因此 最长路(顶点权重之和最大) 的计算可以在 $O(k^2)$ 的时间内完成. 具体来说, 以 $D^k_x$ 为例, 我们可以维护每个顶点 $i(1\leq i\leq k)$ 的最长路程. 当考虑 $D^{k+1}_x$ 时, 例如增加弧 $(i, k+1)$ 或 $(k+1, i)$ , 我们只需要更新 $k+1$ 所有子节点的最长路程即可.

时间复杂度

搜索树第 $k$ 层(root是第0层)对应的节点数量是 $36^{k-1}$ . 如上图所示, 实例 $I_k(\geq 2)$ 包含了 $k-1$ 层. 因此, 从第二层到叶子节点一共有 $n(n-1)/2$ 层. 因此, 搜索树的节点总数 $N$ 为:
$N = \sum_{k=1}^{n(n-1)/2} 36^{k-1} + 7 = O(6^{n^2}).$
每个节点判断可行性的时间为 $O(n^2)$ . 因此算法的时间复杂度为 $O(6^{n^2}\cdot n^2)$ .

一个三维装箱问题的搜索树算法
三维装箱问题的业务场景可以参考<电商业务中的纸箱推荐问题>. 文中考虑了如下问题. 输入 : 长宽高为的箱子和个...
世界级难题：把不同物品装进箱子，如何使箱子表面积最小？
导读：三维装箱问题是一类经典的组合优化问题，具有巨大的学习研究和实际应用价值。传统的三维装箱问题都是给定了箱子的...
一些三维装箱问题
三维装箱问题在电商业务中有重要应用, 例如订单打包和商品装车. 下面我们列举一些电商业务中可能用到的三维装箱问题....
7.9图的应用：最小生成树
最小生成树：Prim算法 ❖解决最小生成树问题的Prim算法，属于“贪心算法”，即每步都沿着最小权重的边向前搜索。...
装箱问题
贪心算法装箱问题问题描述：求解思路：代码实现：
MCTS树学习
MCTS，即蒙特卡罗树搜索，是一类搜索算法树的统称，可以较为有效地解决一些搜索空间巨大的问题。如一个8*8的棋盘...
第一节人工智能的定义
一、主要内容智能体的概念树搜索算法无信息搜索策略启发式搜索策略约束满足问题求解博弈算法不确定性推理 ...
从零开始再造打爆李世石的AlphaGo：使用蒙特卡洛树搜索实现围
上一节我们完成了最大最小搜索树，加上alhpa-beta剪枝算法实现了围棋落子走法。它存在一个问题是，树搜索的层次...
图论（六）图的深度优先遍历DFS(非递归方式)
一、深度优先搜索深度优先搜索是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。对于下面的树而言，D...
二叉搜索树
二叉搜索树图解二叉树搜索算法图解：二叉搜索树算法二叉查找树（Binary Search Tree），（又：二叉搜...