ヒューリスティクス

背景

ヒューリスティックスとは、限られた知識と時間の中で、問題に対する適切な解決策を見つける技術です。より正式には、ヒューリスティックスは経験に基づいており、簡単なルールを使って解決策の検索を高速化することができます。完全な探索には時間がかかりすぎたり、難しすぎたりすることがあります。

より正確に言えば、ヒューリスティックスとは、人間や機械の問題解決をコントロールするために、簡単にアクセスできる、しかし適用範囲の狭い情報を用いた戦略である。

ヒューリスティックは、科学の分野では使えるが、そうでない分野もある。経済学の分野では、1％の誤差があっても問題ないことが多い。1度の誤差がある望遠鏡は、遠くの物体に向ければおそらく使えませんが、同じ望遠鏡を通りの向こう側の窓に向ければ、おそらくこの誤差を許容できるでしょう。1度の誤差は、短い距離では大きな影響を与えません。

例えば、橋の重量をヒューリスティックに推測することで、橋の材質を木、石、鉄のいずれにすべきかを判断し、必要な材料を適切な量だけ購入して、橋の正確な設計を完成させることができます。

しかし、コンピュータサイエンスのように、非常に技術的な分野でヒューリスティックスを使用することは、有害な場合があります。コンピュータサイエンスがその一例です。コンピュータが多かれ少なかれ望む動作をするようにプログラムすると、深刻な不具合が生じる可能性があります。そのため、コンピュータの作業は一般的にかなり厳密でなければなりません。しかし、コンピュータがヒューリスティックな解決策を安全に計算できる分野もあります。例えば、Googleの検索技術はヒューリスティックな手法に大きく依存しており、検索クエリに完全に一致するものが見つからない場合には「ニアミス」マッチを生成します。これにより、ユーザーは検索結果の間違いを修正することができます。例ピーター・スミス」という名前を検索し、その名前が見つからなかった場合、検索エンジンは代わりに「ピート・スミス」とヒューリスティックに一致させ、検索エンジンを使用する人は、ピートとピーターが同一人物であるかどうかを判断しなければならない。

例

ポリア

ここでは、ポリアの1945年の著書『How to Solve It』から、その他のよく使われるヒューリスティクスを紹介します。

• 問題を理解するのが難しい場合は、絵を描いてみましょう。
• 解決策が見つからない場合は、解決策があると仮定して、そこから何を導き出すかを考えてみる（「逆算」）。
• 問題が抽象的であれば、具体的な例を検討してみる。
• より一般的な問題を先に解決してみる。「発明家のパラドックス」：より野心的な計画の方が成功の可能性が高いかもしれない。

梱包の問題

ヒューリスティックスが有効な例として、梱包問題があります。この問題は、いくつかのアイテムを梱包することで構成されています。この問題には、守らなければならないルールがあります。例えば、各アイテムには価値と重さがあります。問題は、最も価値のあるアイテムを、可能な限り少ない重さで手に入れることです。他の例としては、車のトランクのような限られたスペースに、サイズの異なるいくつかのアイテムを収めることが挙げられます。

問題の完璧な解決策を得るためには、すべての可能性を試す必要があります。しかし、すべての可能性を試すには長い時間がかかり、平均して半分の可能性は解決策が見つかるまで試さなければならないため、これは良い選択肢ではありません。そこで多くの人は、一番大きなアイテムから始めて、それをはめ込み、その周りに他のアイテムを並べるようにします。これでほとんどの場合、良い解決策が得られます。しかし、そのような解決策が非常に悪く、別のテクニックを使用しなければならない場合もあります。

したがって、これはヒューリスティックな解決策です。

梱包問題の例。これは一次元（制約）のナップザック問題で，金額を最大にして全体の重量を15kg以下にするためには，どの箱を選べばよいか？多次元の問題では，箱の密度や寸法を考慮することができ，後者は典型的な梱包問題である． (この場合の解答は、緑の箱以外のすべての箱を選ぶことになります)