ヒューリスティック（コンピュータサイエンス）

数理最適化とコンピュータサイエンスにおいて、ヒューリスティック（ギリシャ語のεὑρίσκω eurísko「私は見つける、発見する」^{[ 1 ]}に由来）とは、従来の手法では正確な解や近似解を見つけるのに時間がかかりすぎる場合、あるいは従来の手法では探索空間内で正確な解を見つけられない場合に、より迅速に問題を解くために設計された手法である。これは、最適性、完全性、正確性、あるいは精度を犠牲にして速度を得ることで実現される。ある意味では、近道とも言える。

ヒューリスティック関数（単にヒューリスティックとも呼ばれる）とは、探索アルゴリズムの各分岐ステップにおいて、利用可能な情報に基づいて選択肢をランク付けし、どの分岐に従うかを決定する関数である。例えば、正確な解を近似することもある。^{[ 2 ]}

定義と動機

ヒューリスティックの目的は、妥当な時間枠内で、目の前の問題を解決するのに十分な解決策を生み出すことです。この解決策は、必ずしもその問題に対するすべての解決策の中で最善の解決策ではないかもしれませんし、正確な解決策に近似しているだけかもしれません。しかし、その解決策を見つけるのに法外な時間を要さないため、ヒューリスティックは依然として価値があります。

ヒューリスティックは、それ自体で結果を生成する場合もあれば、効率を向上させるために最適化アルゴリズムと組み合わせて使用​​される場合もあります (たとえば、適切なシード値を生成するために使用される場合があります)。

理論計算機科学におけるNP 困難性に関する結果により、現実世界のアプリケーションで日常的に解決する必要があるさまざまな複雑な最適化問題に対して、ヒューリスティックが唯一の実行可能な選択肢となっています。

ヒューリスティックスは、人工知能や思考のコンピュータシミュレーションの分野全体に根ざしており、既知のアルゴリズムが存在しない状況でも使用できる。^{[ 3 ]}

例

より単純な問題

ヒューリスティックに期待される計算パフォーマンスの向上を達成する 1 つの方法は、その解決策が最初の問題の解決策でもある、より単純な問題を解決することです。

巡回セールスマン問題

巡回セールスマン問題(TSP) を解くための近似の例は、Jon Bentleyによって説明されています。

• 「都市のリストと各都市間の距離が与えられた場合、各都市を 1 回ずつ訪れて元の都市に戻る最短ルートは何でしょうか。」

ペンプロッタを使用して描画する順序を選択する。TSPはNP困難であることが知られているため、中規模問題であっても最適解を解くことは困難である。代わりに、貪欲アルゴリズムを使用すると、適度に短い時間で、最適ではないが良好な解（最適な答えへの近似値）を与えることができる。貪欲アルゴリズムのヒューリスティックとは、後で良好なステップを妨げる（または不可能にする）かどうかに関係なく、現時点で最良の次のステップを選択するというものである。これは、実践では十分に良好な解であることが示され、理論ではより良い解が存在することが示されている（場合によってはどの程度優れているかを示す）という意味でヒューリスティックである。^{[ 4 ]}

検索

ヒューリスティックによってアルゴリズムが高速化される別の例として、特定の探索問題が挙げられます。ヒューリスティックは、全空間探索アルゴリズムと同様に、まず各ステップであらゆる可能性を試します。しかし、現在の可能性が既に見つかった最善の解よりも悪い場合は、いつでも探索を停止できます。このような探索問題では、ヒューリスティックを使用してまず良い選択肢を試し、悪い経路を早期に排除することができます（アルファ-ベータ・プルーニングを参照）。A *探索などの最良優先探索アルゴリズムの場合、ヒューリスティックが許容される限り、ヒューリスティックによってアルゴリズムの収束性が向上し、正確性も維持されます。

ニューウェルとサイモン：ヒューリスティック探索仮説

チューリング賞受賞スピーチにおいて、アレン・ニューウェルとハーバート・A・サイモンはヒューリスティック探索仮説について論じています。物理的な記号システムは、既知の記号構造を生成・修正し、最終的に解の構造と一致するまで繰り返します。次のステップはそれぞれ前のステップに依存しており、ヒューリスティック探索は、現在のステップが解にどれだけ近いかを測定することで、どの経路を追求し、どの経路を無視するかを学習します。したがって、解を完成させる可能性が低いと測定されたいくつかの可能性は、決して生成されません。

ヒューリスティックな手法は、探索木を用いることでその目的を達成することができます。しかし、ヒューリスティックは、すべての可能な解決策の分岐を生成するのではなく、他の分岐よりも結果をもたらす可能性の高い分岐を選択します。各決定点において選択的であり、解決策をもたらす可能性の高い分岐を選択します。^{[ 5 ]}

AIにおける一般的なヒューリスティックアルゴリズム

ヒューリスティックスは、AIの多くの情報探索アルゴリズムや最適化技術の中心となっている。^{[ 6 ]}

• A*探索アルゴリズムA*探索アルゴリズムは、最適解を効率的に見つけることができるため、最も人気のあるヒューリスティック探索手法の一つです。A*は、実際の経路コストと、目標到達までの残存コストのヒューリスティック推定値を組み合わせます。

• 貪欲最良優先探索：このアルゴリズムは、それまでの経路コストを考慮せず、ヒューリスティック関数（h(n)）のみに基づいて、目標に最も近いノードを拡張します。高速ですが、最適な解を保証するものではありません。
• ヒルクライミング：現在の状態からより良い近傍状態へと反復的に移動する局所探索アルゴリズム。実装はシンプルですが、局所最適解（近傍解よりも優れているものの、全体としては最適ではない準最適解）に陥ることがあります。方向を決定するための目的関数（連続空間における勾配のような）が必要です。
• シミュレーテッドアニーリング：シミュレーテッドアニーリングは、局所的最大値に陥るのを避けるために、時折、より悪い解を受け入れることで探索空間を探索するヒューリスティックな探索手法です。冶金学におけるアニーリング過程に着想を得たこのアルゴリズムは、探索が進むにつれて、より悪い解を受け入れる確率を徐々に低減させます。最適ではない解の探索を可能にすることで、シミュレーテッドアニーリングは局所的最大値を回避し、より良い全体的な解を見つけることができます。これは、探索空間が広範かつ複雑な最適化問題でよく用いられます。
• 遺伝的アルゴリズム:自然選択からヒントを得て、選択、交差、突然変異などのプロセスを使用して、世代を超えて候補ソリューションの集団を進化させます。
• アリコロニー最適化:アリが食物源への道を見つける方法にヒントを得た群知能手法で、人工の「フェロモン」を使用して探索を誘導します。

ウイルス対策ソフトウェア

ウイルス対策ソフトウェアは、多くの場合、ウイルスやその他の形式のマルウェアを検出するためにヒューリスティック ルールを使用します。ヒューリスティック スキャンは、ウイルスのクラスまたはファミリーに共通するコードや動作パターンを検索し、ウイルスごとに異なるルール セットを使用します。ファイルまたは実行中のプロセスに一致するコード パターンが含まれている、またはその一連のアクティビティを実行していることが判明した場合、スキャナーはファイルが感染していると推測します。動作ベースのヒューリスティック スキャンの最も高度な部分は、単純な文字列スキャン方法では簡単に検出できない、高度にランダム化された自己変更/変異 (ポリモーフィック) ウイルスに対抗できることです。ヒューリスティック スキャンは、最初にどこか別の場所でウイルスが検出され、ウイルス スキャナーの開発者に送信され、分析され、スキャナーの検出更新がスキャナーのユーザーに提供されることなく、将来のウイルスを検出できる可能性があります。

落とし穴

ヒューリスティックの中には、確固とした理論に基づいたものがあります。それらは、理論からトップダウン的に導き出されるか、実験データや実世界のデータに基づいて導き出されます。一方、理論を全く考慮せず、実世界の観察や経験に基づいた単なる経験則に過ぎないものもあります。後者は、より多くの落とし穴に陥りやすい傾向があります。

あるヒューリスティックが、特定の要件セットを満たすことが数学的に証明されていないにもかかわらず、あるコンテキストで「機能する」ことがわかっているという理由で、さまざまなコンテキストで再利用される場合、現在のデータ セットが必ずしも将来のデータ セットを表すとは限らず (過剰適合を参照)、「解決策」とされるものがノイズに似たものになる可能性があります。

ヒューリスティックを用いて誤った結果の確率を推定する際には、統計分析を実施することができます。探索問題やナップサック問題を解くためにヒューリスティックを用いるには、そのヒューリスティックが許容可能かどうかを確認する必要があります。とラベル付けされたノードまたは頂点を合計した有向グラフにおいて、目標ノードまでの真の最適距離を近似することを目的としたヒューリスティック関数が与えられた場合、「許容可能」とは、おおよそヒューリスティックが目標までのコストを過小評価していること、あるいは正式には、 となるすべての場合においてとなることを意味します。 ${\displaystyle h(v_{i},v_{g})}$ ${\displaystyle d^{\star }(v_{i},v_{g})}$ ${\displaystyle v_{g}}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle v_{0},v_{1},\cdots ,v_{n}}$ ${\displaystyle h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})}$ ${\displaystyle (v_{i},v_{g})}$ ${\displaystyle {i,g}\in [0,1,...,n]}$

ヒューリスティックが許容されない場合は、グラフの行き止まりになったり、2 つのノードとの間を行ったり来たりして、目標を見つけられない可能性があります。 ${\displaystyle G}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle {i,j}\neq g}$

語源

「ヒューリスティック」という言葉は19世紀初頭に使われるようになりました。これはギリシャ語の「見つける」を意味するheuriskeinから不規則に派生したものです。 ^{[ 7 ]}

参照

• 建設的ヒューリスティック
• メタヒューリスティック: 通常はメモリと学習を使用して、基本的なヒューリスティック アルゴリズムを制御および調整する方法。
• 数学的戦略: メタヒューリスティックスと数学的計画法 (MP) 技術の相互運用によって作成された最適化アルゴリズム。
• 反応型検索最適化:ヒューリスティックスの自己調整にオンライン機械学習の原理を使用する方法。

参考文献

1. 「ヒューリスティック」 2025年4月7日。
2. パール・ジュデア (1984). 『ヒューリスティックス：コンピュータ問題解決のための知的探索戦略』 米国：Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3. OSTI 5127296 . 
3. アプター、マイケル・J. (1970). 『行動のコンピュータシミュレーション』 ロンドン: ハッチンソン社 p. 83. ISBN 9781351021005。
4. Jon Louis Bentley (1982). 『効率的なプログラムを書く』 Prentice Hall. p.  11 .
5. Allen NewellとHerbert A. Simon (1976). 「実証的探究としてのコンピュータサイエンス：記号と探索」(PDF) . Comm. ACM . 19 (3​​): 113– 126. doi : 10.1145/360018.360022 . S2CID 5581562 . 
6. 「局所探索」 . CS 188: 人工知能入門. カリフォルニア大学バークレー校. 2026年1月19日閲覧。
7. 英語におけるヒューリスティックの定義」オックスフォード大学出版局。2016年10月23日時点のオリジナルよりアーカイブ。 2016年10月22日閲覧。