1.2. 計画問題での NP 完全

例に挙げたユースケースは 通常 NP 完全または NP 困難 であり、以下のことが言えます。

  • 問題に対する解を実用的な時間内に検証することが容易である。
  • 問題に対する最適解を実用的な時間内に見つけ出す確実な方法がない。

この場合、一般的な 2 つの手法では不十分であるため、問題を解くのが予想より困難だと考えられます。

  • 力まかせアルゴリズムでは (より高度な類似アルゴリズムであっても)、時間がかかり過ぎる。
  • (「ビンパッキング問題」において) 容量が一番大きいビンから順に詰めてゆく クイックアルゴリズムでは、最適解からは程遠い解しか得られない。

高度な最適化アルゴリズムを用いる Business Optimizer であれば、このような計画問題に対する適切な解を、妥当な時間内に見つけ出すことができます。