打分函数中如何计算当前堆的填充间隙的体素个数取决于不同的打印机类型。对于粉末打印机,粉末会在整个水平面上填充至整个堆的最大高度,所以其间隙量等于从底部到堆顶的所有空余体素数量。
体素块的切割和对接。对于一个待排列块集合和当前排列堆P,我们将会对每一个中的块进行对接测试。对于每一个以中的块q及其六个轴对齐的朝向(在三维空间中),在每一个朝向下,对q和P进行对接测试。当执行对接测试时,P和g的两个相向面可以看作成两个深度图,对接测试就好似俄罗斯方块游戏,q在打??印空间上方的水平面窗口进行移动,在每一个离散的位置都会“掉落”进容器与堆进行对接测试。在对接测试中,CAP操作需要对待排列块进行切割,对此,我们只允许使用轴对齐的切割,并且当必要时会约束切割操作使之仅产生两个子块。
候选操作集。对于对接测试中生成的所有操作,我们使用前述的优先级打分函数来对每个操作进行优先级打分,然后选择并保留最好的厂个操作作为候选操作集合。
深度剪枝。在搜索树中使用限定的集束宽度P进行搜索对应于搜索树的I度。通过比较一个节点处所对应的部分解所计算出来的目标函数值和当前最优目标函数值,我们还可以对搜索树进行采度剪沒,剪枝掉该节点的整个子搜索树。具体来说,令P为一个节点d所对应的一个部分解,为当前搜索到的一个最优完整解,如果那么d处的子树将会被剪枝掉。这个剪枝搜索的有效性在于,在当上述假设成立时,d处的进一步扩展搜索将不再是必须的,即d处的扩展搜索无法进一步提升目标函数值。
事实上,上述深度剪枝之所以有效的原因在于,目标函数在模型的分解与排列的过程进行中,不会递增。故,当在d处的目标函数值小于当前的最优解的情况下,d的子树下所包含的所有可能解的目标函数值也都小于当前最优解,故我们可以在此处进行深度剪枝,停止其子树的搜索。