Loading article…
コンピュータサイエンスでは、問題の最適解が部分問題の最適解から構築できる場合、その問題は最適部分構造を持つと言われます。この性質は、問題に対する貪欲アルゴリズムの有用性を判断するために使用されます。[ 1 ]
一般的に、貪欲アルゴリズムは、帰納法によって各ステップで最適であることが証明できる場合、最適部分構造を持つ問題を解決するために使用されます。[ 1 ]それ以外の場合、問題が重複する部分問題も示す場合は、 分割統治法または動的計画法が使用されることがあります。適切な貪欲アルゴリズムがなく、問題が重複する部分問題を示さない場合は、多くの場合、解空間の長いが直接的な探索が最良の代替手段となります。
動的計画法を数理最適化に応用する場合、リチャード・ベルマンの最適性原理は、ある開始期間tからある終了期間 T までの動的最適化問題を解くには、暗黙のうちに、 t<s<Tである後の日付sから始まる部分問題を解かなければならないという考えに基づいています。これは最適部分構造の一例です。最適性原理は、tから始まる問題の値とsから始まる問題の値の関係を示すベルマン方程式を導出するために使用されます。
図1に示すように、車で2つの都市間を移動する最短経路を見つけることを考えてみましょう。このような例では、最適な部分構造が見られる可能性が高いです。つまり、シアトルからロサンゼルスへの最短経路がポートランドを経由してサクラメントを通る場合、ポートランドからロサンゼルスへの最短経路もサクラメントを経由しなければなりません。つまり、ポートランドからロサンゼルスへの移動方法は、シアトルからロサンゼルスへの移動方法という問題の中に包含されているのです。（グラフの波線は、部分問題の解を表しています。）
最適な部分構造を示す可能性が低い問題の例として、ブエノスアイレスからモスクワへの最も安い航空券を探す問題を考えてみましょう。たとえその航空券がマイアミとロンドンを経由するものであっても、マイアミからモスクワへの最も安い航空券がロンドン経由であるとは断言できません。なぜなら、航空会社が複数便の旅行を販売する際の価格は、通常、その旅行を構成する個々のフライトを販売する際の価格の合計ではないからです。
最適部分構造のもう少し厳密な定義を与えることができます。「問題」を「選択肢」の集合とし、各選択肢にコストc ( a ) が関連付けられているとします。タスクは、 c ( a ) を最小化する選択肢の集合を見つけることです。選択肢は部分集合に分割できるとします。つまり、各選択肢は 1 つの部分集合にのみ属します。各部分集合には独自のコスト関数があるとします。これらのコスト関数の最小値は、同じ部分集合に限定された全体コスト関数の最小値と同様に見つけることができます。これらの最小値が各部分集合で一致する場合、全体最小値は選択肢の集合全体からではなく、定義したより小さな局所コスト関数の最小値からなる集合からのみ選択できることはほぼ明らかです。局所関数の最小化が「低次の」問題であり、（特に）これらの削減を有限回行った後に問題が自明になる場合、その問題は最適部分構造を持ちます。