3.3. 规划问题的解决方案
规划问题有很多解决方案。
几种解决方案类别:
- 可能的解决方案
- 可能的解决方案是任何解决方案,无论它是否会破坏任意数量的限制。规划问题通常具有大量可能的解决方案。其中许多解决方案都并不有用。
- 可行的解决方案
- 可行的解决方案是不会破坏任何(负)硬限制的解决方案。可行的解决方案数量相对于可能的解决方案数量。有时没有可行的解决方案。每个可行的解决方案都是可能的解决方案。
- 最佳解决方案
- 最佳解决方案是具有最高分数的解决方案。规划问题通常有几个最佳解决方案。它们始终至少有一个最佳解决方案,即使没有可行的解决方案,并且最佳解决方案不可行。
- 找到最佳解决方案
- 最佳解决方案是在指定时间内实现的最高分数的解决方案。最佳解决方案可能很可行,给定有足够的时间,它是一个最佳解决方案。
因此,可能的解决方案数量较大(如果正确计算),即使设置了小的数据也是如此。
在 optaplanner-examples/src
distribution 文件夹中提供的示例中,大多数实例都有大量可能的解决方案。因为无法保证查找最佳解决方案,因此任何实施都被强制评估所有可能的解决方案的子集。
OptaPlanner 支持多种优化算法,以便有效地利用这一大量可能的解决方案。
根据用例,一些优化算法性能比其他算法更好,但无法提前知道。使用 OptaPlanner,您可以通过在几个 XML 或代码中更改 solver 配置来切换优化算法。