分枝限定アルゴリズム - 開発者ドキュメント

1. 概要

コンピュータサイエンスでは、実行可能な解決策が有限であるが膨大な数の最適化問題が多数あります。これらの中で、グラフ内の最短経路の検索や最小スパニングツリーなどのいくつかの問題は、多項式時間で解決できます。

生産計画、乗組員スケジューリングのようなかなりの数の最適化問題は、多項式時間で解決できず、NP困難クラスに属します。これらの問題は、NP困難組み合わせ最適化問題の例です。

分枝限定法（B＆B）は、このような問題を解決するために広く使用されているアルゴリズムパラダイムです。

このチュートリアルでは、分枝限定法について詳しく説明します。

2. 基本的な考え方

分枝限定アルゴリズムは、組み合わせ、離散、および一般的な数学的最適化問題の最適解を見つけるために使用されます。一般に、NP困難問題が与えられると、分枝限定アルゴリズムは検索全体を探索します。可能な解決策のスペースと最適な解決策を提供します。

分枝限定アルゴリズムは、探索空間全体を探索することにより、可能な候補解を段階的に列挙することで構成されます。考えられるすべての解決策を使用して、最初にルート化された決定木を構築します。ルートノードは、検索空間全体を表します。

ここで、各子ノードは部分的なソリューションであり、ソリューションセットの一部です。ルート決定木を構築する前に、最適なソリューションに基づいて、特定の問題に対して上限と下限を設定します。各レベルで、ソリューションセットに含めるノードを決定する必要があります。各レベルで、最適な境界を持つノードを探索します。このようにして、最適で最適なソリューションをすばやく見つけることができます。

このような場合、適切な上限と下限を見つけることが重要です。局所最適化法を使用するか、検索空間内の任意の点を選択することにより、上限を見つけることができます。一方、凸緩和または二重性から下限を得ることができます。

一般に、ソリューションセットをソリューションのより小さなサブセットに分割する必要があります。次に、ルート化された決定木を構築し、最後に、各レベルで可能な限り最良のサブセット（ノード）を選択して、可能な限り最良のソリューションセットを見つけます。

3. 分枝限定法が良い選択であるのはいつですか？

分枝限定法が他のアルゴリズムよりも効率的な選択になる可能性があるいくつかの問題については、すでに説明しました。このセクションでは、分枝限定アルゴリズムが適切な場合をすべてリストします。

与えられた問題が離散最適化問題である場合、分枝限定法が適切な選択です。離散最適化は、問題の変数が離散セットに属する必要がある最適化のサブセクションです。このような問題の例は、0-1整数計画法またはネットワークフロー問題です。

分枝限定法は組み合わせ最適化問題で効率的に機能します。最適化問題の目的関数が与えられた場合、組み合わせ最適化は目的関数の最大値または最小値を見つけるプロセスです。目的関数の定義域は離散的で大きくなければなりません。ブール充足可能性、整数線形計画法は、組み合わせ最適化問題の例です。

4. 分枝限定アルゴリズムの例

このセクションでは、分枝限定アルゴリズムを使用してジョブ割り当ての問題を解決する方法について説明します。

4.1. 問題文

まず、ジョブ割り当ての問題を定義しましょう。仕事の割り当ての問題の標準バージョンでは、仕事と労働者が存在する可能性があります。簡単にするために、この例では仕事と労働者を取り上げています。

ジョブがワーカーに割り当てられている場合、他のワーカーがその特定のジョブを引き受けることができないという条件で、使用可能なジョブを任意のワーカーに割り当てることができます。また、各ジョブにはそれに関連するコストがあり、ワーカーごとに異なることに注意する必要があります。

ここでの主な目的は、すべてのジョブのコストの合計が最小になるように、各ワーカーに1つのジョブを割り当てることによって、すべてのジョブを完了することです。

4.2. 分枝限定アルゴリズムの擬似コード

次に、分枝限定アルゴリズムを使用してジョブ割り当ての問題を解決する方法について説明します。

最初に擬似コードを見てみましょう。

ここに、利用可能なジョブの数、利用可能なワーカーのリスト、各ジョブに関連するコストなどの情報を含む入力コストマトリックスがあります。この関数は、アクティブなノードのリストを維持します。この関数は、ツリーの各レベルでアクティブノードの最小コストを計算します。最小コストのノードを見つけたら、アクティブノードのリストからノードを削除して返します。

特定のノードのコストを計算し、それをアクティブノードのリストに追加する擬似コードの関数を使用しています。

サーチスペースツリーでは、各ノードに、コスト、ジョブの総数、ワーカーの総数などの情報が含まれています。

次に、作成したサンプル例でアルゴリズムを実行してみましょう。

最初は、利用可能な仕事があります。労働者は、利用可能な仕事のいずれかを取るオプションがあります。そのため、レベルでは、利用可能なすべてのジョブをワーカーに割り当て、コストを計算しました。ワーカーにジョブを割り当てた場合、検索スペースツリーのレベルで最も低いコストが得られることがわかります。 だから私たちは仕事を割り当てます作業してアルゴリズムを続行します。「はい」は、これが現在最適なコストであることを示します。

ジョブをワーカーに割り当てた後も、まだ2つの開いているジョブがあります。さて、労働者について考えてみましょう。最適なコストを得るために、仕事または労働者のいずれかに割り当てようとしています。

ジョブまたはワーカーのいずれかに割り当てることができます。 再度、コストを確認し、ジョブ がレベルで最も低いため、ワーカーに割り当てます。

ついに、 私たちは仕事を割り当てます 労働者に、そして最適なコストはです。