什么是计划问题

规划问题具有基于有限资源和特定约束的最优目标。最佳目标可以是任意数量的事物，例如：

• 利润最大化 - 最佳目标会带来尽可能高的利润。

• 最小化生态足迹——最佳目标对环境的影响最小。

• 最大限度地提高员工或客户的满意度——最佳目标优先考虑员工或客户的需求。

实现这些目标的能力取决于可用资源的数量，例如：

• 人的数量。

• 多少时间。

• 预算。

• 实物资产，例如机器、车辆、计算机、建筑物等。

还必须考虑与这些资源相关的特定限制，例如一个人的工作小时数、他们使用某些机器的能力或设备之间的兼容性。

OptaPlanner 帮助 Java TM 程序员有效地解决约束满足问题。在底层，它将优化启发式和元启发式与非常有效的分数计算相结合。

1.规划问题是 NP-complete 或 NP-hard

上面所有的用例可能都是 NP-complete/NP-hard，用外行的话来说就是：

• 在合理的时间内验证给定的问题解决方案很容易。

• 没有灵丹妙药可以在合理的时间内找到问题的最佳解决方案 (*)。

(*) 至少，世界上最聪明的计算机科学家还没有找到这样的灵丹妙药。但是，如果他们找到一个 1 的 NP 完全问题，它将适用于每个 NP 完全问题。事实上，任何能证明这种灵丹妙药是否真的存在的人都会获得 1,000,000 美元的奖励。

这意味着非常可怕：解决您的问题可能比您预期的要难，因为这两种常见的技术是不够的：

• 蛮力算法（甚至更智能的变体）将花费太长时间。

• 一个快速算法，例如在装箱中，首先放入最大的物品，将返回一个远非最优的解决方案。

通过使用先进的优化算法，OptaPlanner 确实在合理的时间内为此类规划问题找到了接近最优的解决方案。

2. 规划问题具有（硬约束和软约束）

通常，规划问题至少有两个级别的约束：

• 不得破坏（*负）硬约束。*例如：1 位老师不能同时教 2 节不同的课程。

• 如果可以避免，则不应破坏*（负）软约束。*例如：A 老师不喜欢在星期五下午上课。

一些问题也有积极的约束：

• 如果可能，应满足*积极的软约束（或奖励） 。*例如：B 老师喜欢在星期一早上上课。

一些基本问题（例如 N 个皇后）只有硬约束。有些问题具有三个或更多级别的约束，例如硬约束、中等约束和软约束。

这些约束定义了规划问题的得分计算（AKA 适应度函数）。规划问题的每个解决方案都可以用分数进行评分。使用 OptaPlanner，分数约束是用面向对象的语言编写的，例如 Java TM 代码。这样的代码简单、灵活且可扩展。

3. 规划问题具有巨大的搜索空间

一个规划问题有许多解决方案。解决方案有几类：

• 一个可能的解决方案是任何解决方案，无论它是否打破任何数量的约束。规划问题往往有大量可能的解决方案。其中许多解决方案毫无价值。

• 可行的解决方案是不破坏任何（负）硬约束的解决方案。可行解的数量往往与可能解的数量相关。有时没有可行的解决方案。每个可行的解决方案都是可能的解决方案。

• 最优解是得分最高的解。规划问题往往有 1 个或几个最优解。始终存在至少 1 个最优解，即使在没有可行解且最优解不可行的情况下也是如此。

• 找到的最佳解决方案是实现在给定时间内找到的得分最高的解决方案。找到的最佳解决方案很可能是可行的，并且只要有足够的时间，它就是一个最佳解决方案。

与直觉相反，可能的解决方案数量巨大（如果计算正确），即使数据集很小。正如您在示例中看到的那样，大多数实例比已知宇宙中的最小原子数 (10^80) 有更多可能的解决方案。因为没有找到最佳解决方案的灵丹妙药，所以任何实施都被迫评估所有这些可能解决方案的至少一个子集。

OptaPlanner 支持多种优化算法，可以有效地处理大量可能的解决方案。根据用例的不同，一些优化算法的性能优于其他算法，但无法提前判断。使用 OptaPlanner，只需几行 XML 或代码更改求解器配置，即可轻松切换优化算法。