3.3. 规划问题中的 NP-completeness

提供的用例 可能是 NP-complete 或 NP-hard,这意味着适用以下语句:

  • 可轻松验证特定解决方案以合理时间的问题。
  • 在合理时间查找问题的最佳解决方案没有简单的方法。

含义是解决您的问题可能比您预计的难度更高,因为这两种常见技术并不易受:

  • 静默的强制算法(即使是更高级的变体)用时过长。
  • 例如,一个快速算法(例如在 bin packing 问题 中),首先考虑最大的项目 会返回最佳解决方案。

通过使用高级优化算法,OptaPlanner 在合理时间内找到适合此类规划问题的良好解决方案。