1. 概要

このチュートリアルでは、コンピュータサイエンスと数学の問題を解決するための2つの一般的なアプローチ、貪欲でヒューリスティックなアルゴリズムについて説明します。

両方のアプローチの基本的な理論的アイデアについて説明し、それらのコアの違いを示します。

2. 欲張りアルゴリズムの理論的アイデア

欲張りアルゴリズムは主に数理最適化問題を解くために使用されます。最適化で与えられた問題に対応するコスト関数を最小化または最大化します。

最適化問題を解く方法にはさまざまな種類があります。 欲張りアルゴリズムは、最適化問題を解決するために最も使用され、最も簡単な方法です。

欲張りアルゴリズムは、特定の問題をいくつかの段階に分割します。主なアイデアは、ヒューリスティックを使用して各段階で最適な結果を取得することです。 各ステージのソリューションを次のステージの入力として使用し、グローバルに最適なソリューションを見つけます。

各段階でのヒューリスティックは、グローバルに最適なソリューションにつながるローカルに最適なソリューションを選択することです。

欲張りアルゴリズムは、常に最適な解を生成することを保証するものではありませんが、効率的な時間で特定の問題のグローバルに近似した解を提供することができます。

実際の例を見てみましょう。

ジャックが避暑地への旅行を計画していて、目的地に到達するための（お金に関して）最も安く（時間的に）最短の方法を望んでいるとします。したがって、彼はそこに到達するための最良の方法を選択する必要があります。 それを行うために、彼は目標の目的地に到達するためのすべての可能な方法のグラフを描きます。

図が示すように、目的地に到達するためのさまざまな方法があります。 ここで、ジャックは欲張りアルゴリズムを使用できます。 最適なパスを選択するヒューリスティック戦略は、各ルートの時間あたり（1時間あたり）の運賃を計算することです。 その結果に基づいて、彼は複数の実行可能なソリューションとして最適なソリューションを決定できます。

しかし、彼はそれ以上の側面を考慮せずに現在利用可能なデータを決定したばかりであるため、現在のソリューションが最良であるとは言えません。

彼が選んだ道が最も安くて最も短い道であるかもしれませんが、それは強制的に最良の道ではありません。 おそらく、彼が選んだ道は危険であるか、状態が良くない可能性があります。 したがって、欲張りアルゴリズムによって最適性が保証されるわけではありません。

多くのプログラミング問題は欲張りアルゴリズムを使用します。 人気のあるアルゴリズムは、ダイクストラアルゴリズム、プリムの最小スパニングツリーアルゴリズム、ナップザック、および配列の最小-最大です。

3. 失敗の場合

欲張りアルゴリズムは最適なソリューションを提供することを保証しません。欲張りアプローチによって提供されるソリューションが最適なソリューションとはほど遠い場合があります。 欲張り解が最適解からかけ離れている状況を示すために、コインカウントの例について説明しましょう。

私たちの通貨システムで仮定しましょう。 価値のあるコインがあります。 私たちの目的は、可能な限り少ないコインを使用して、特定の値を数えることです。 最適な解決策は、希望する価値に一致させるために、コインの価値とコインの価値を選択します。 したがって、最適なアルゴリズムは合計でコインを選択します。

ただし、欲張りアルゴリズムは、最初に利用可能なコインから最大値のコインを選択します。 したがって、コインの価値とコインの価値を選択します。 したがって、欲張りアルゴリズムは、指定された値をカウントするためにコインを使用します。

4. ヒューリスティックアルゴリズムの基礎

これは、問題の解決策を可能な限り迅速に設計するために使用されます。 最適なソリューションが得られない場合がありますが、短時間でほぼ最適なソリューションが得られます。

ヒューリスティックアルゴリズムは、 NP問題を解決し、迅速な解決策を提供することで問題の時間計算量を減らすために使用されます。 人工知能の問題で広く利用されています。 一例として、情報に基づく検索があります。ここでは、解決策を見つけるための次のステップを決定するための追加情報を利用できます。

ヒューリスティックアルゴリズムでは、ヒューリスティック関数がヒューリスティック値を与えて最適なソリューションを見つけます。 各ノードには、最適なパスを見つけるために使用されるヒューリスティック値があります。

ヒューリスティック関数には、許可されるものと許可されないものの2種類があります。

許容されるヒューリスティック関数では、目標を達成するためのコストを過大評価することはありません。 一方、許容されないヒューリスティック関数は、目標を達成するためのコストを過大評価します。 2つの関数の違いを示す例を見てみましょう。

ここで、からへの実際のコストはです。 ヒューリスティック関数を使用してすべてのノードのヒューリスティック値を計算しました。これを図に示します。 ノード、ノード、ノードのヒューリスティック値を確認できます。

ヒューリスティック値は、各ノードの実際のコストよりも小さくなります。 これは、許容されるヒューリスティック関数の例です。 許容されないヒューリスティック関数の場合、各ノードのヒューリスティック値は実際のコストよりも高くなります。

A *アルゴリズム、巡回セールスマン問題、シミュレーテッドアニーリング、山登り問題など、いくつかの問題がヒューリスティック手法を使用しています。 。

5. トレードオフ条件

すでに説明したように、ヒューリスティックアルゴリズムが最適なソリューションを提供することは保証されておらず、特定の問題にヒューリスティックアルゴリズムを適用することはお勧めできません。 ヒューリスティックアルゴリズムは、 NP-Hard クラスに属する問題に適している可能性があり、既知の解決策はありません。

ヒューリスティックアルゴリズムが特定の問題に適しているかどうかの事前のアイデアを与えるいくつかのトレードオフ条件が存在します。 最初の条件は問題の完全性です。特定の問題に対して複数の解決策が存在する場合は、ヒューリスティックアルゴリズムを適用しない方がよいでしょう。 一般に、ヒューリスティックアルゴリズムは、利用可能なすべてのソリューションの中で最善ではない可能性がある1つのソリューションを提供します。

ヒューリスティックアルゴリズムを使用するかどうかも、問題の最適性に依存します。 最適なソリューションのみを見つけることを決定したい場合、ヒューリスティックはそれを生成できない可能性があります。

ヒューリスティックアルゴリズムを選択するときは、実行時間を考慮し、ヒューリスティックアルゴリズムにかかる時間が従来のアルゴリズムよりも優れているかどうかを確認する必要があります。 既存の方法よりもわずかに速いと仮定します。 その場合、ヒューリスティックのオーバーヘッドがより大きな入力の時間計算量を増加させる可能性があるため、既存の従来の方法を選択することをお勧めします。

6. 貪欲なアルゴリズムとヒューリスティックアルゴリズムの違い

貪欲なアルゴリズムとヒューリスティックなアルゴリズムの違いについて話しましょう。

7. 結論

このチュートリアルでは、貪欲でヒューリスティックなアルゴリズムの一般的な考え方について説明しました。 また、両方のアプローチの主な違いを示す表も示しました。