Red Hat Summit3.2. 計画問題での NP 完全
例に挙げたユースケースは 通常 NP 完全または NP 困難 であり、以下のことが言えます。
- 問題に対する解を実用的な時間内に検証することが容易です。
- 問題に対する最適解を実用的な時間内に見つけ出す確実な方法がない。
この場合、一般的な 2 つの手法では不十分であるため、問題を解くのが予想より困難だと考えられます。
- 力まかせアルゴリズムでは (より高度な類似アルゴリズムであっても)、時間がかかり過ぎる。
- たとえば ビンパッキング問題 のような迅速なアルゴリズムでは、容量の大きい順でアイテムを入力する と、最適とはほど遠い解が返されます。
高度な最適化アルゴリズムを用いる OptaPlanner であれば、このような計画問題に対する適切な解を、妥当な時間内に見つけ出すことができます。
