1. 概要

この短いチュートリアルでは、ヒューリスティック関数の定義、その長所と短所、およびそのよく知られた例のいくつかについて説明します。

2. ヒューリスティック関数

2.1. 意味

ヒューリスティック関数（アルゴリズム）または単にヒューリスティックは、問題の正確な解決策がない場合、または解決策を取得する時間が長すぎる場合に、問題を解決するためのショートカットです。

2.2. 速度対。 正確さ

定義から、目標は、最適ではない場合でも、より高速なソリューションまたは近似ソリューションを見つけることであると結論付けることができます。 つまり、ヒューリスティックを使用する場合、精度とソリューションの速度を交換します。

たとえば、欲張りアルゴリズムは通常、迅速ですが最適ではないソリューションを生成します。 次のツリーで最大の合計を見つける欲張りアルゴリズムは、赤いパスを使用しますが、最適なパスは緑のパスです。

2.3. 許容されるヒューリスティック

ヒューリスティックは必ずしもコストの削減につながるとは限りません。 ただし、ソリューションの真のコストまたは可能な限り低いコストを過大評価しないものは、許容可能なヒューリスティックと呼ばれます。 この特性により、ソリューションの最適性を保証できます。 許容可能なヒューリスティックは、元の問題を制約の観点から単純化し、制約の少ない問題に減らすことで見つけることができます。 例として、8つのパズルの問題を考えてみましょう。

左側の状態から始めて、右側の目標状態に到達したいと思います。 このパズルのヒューリスティックな解決策として、2つの状態間のハミング距離を考えることができます。これは、緑色で強調表示された置き忘れたタイルの数です。 ここでは、タイルを手に取って適切な場所に配置できると仮定して、問題の制約を緩和しました。

このソリューションは、最適なソリューションがこれよりも少ないステップを持つことができないという点で許容されます（つまり、下限です）。

3. ヒューリスティックの例

解決するヒューリスティックアルゴリズムを考え出すことができる多くの問題があります。

よく知られている3つについて説明しましょう。

3.1. 探す

パスファインディングアルゴリズムは、ヒューリスティックを使用してグラフ内の最短パスを検索します。 各ノードには、として計算されるコストがあります。 この式では、はパスの先頭からのノードの実際のコストであり、は目標に到達するためのヒューリスティックなコストです。 は許容されます。つまり、常に最適な解を見つけます。

3.2. 巡回セールスマン問題（TSP）

都市のリストを前提として、 TSP で、各都市を1回だけ訪問し、開始都市に戻る最短ルートを見つけます。 これはNP困難問題として知られており、最適な解を見つけるのが難しいことを意味します。 したがって、代わりに、最短経路を提供しない可能性があるが、少なくとも迅速な回答を提供する欲張りアルゴリズムを使用します。

欲張りアルゴリズムは、最適ではないソリューションですが、適度に機能するという点でヒューリスティックと見なすことができます。

3.3. グリッドマップ上の距離

グリッドマップでパスを検索する場合、移動方向の制約に応じて、いくつかの距離関数をヒューリスティックと見なすことができます。 次に、このヒューリスティックをアルゴリズムで使用して、最短パスを見つけます。 下の画像では、オレンジ色の四角から紫色の四角に移動したいと考えています。色付きの四角が検索スペースです。 任意の方向が可能な場合は、ユークリッド距離を使用できます。

許可される方向が4つしかない場合は、マンハッタン距離が適切です。

4. 結論

この記事では、ヒューリスティック関数、その利点と落とし穴、およびヒューリスティック関数を使用できるいくつかの例について学習しました。