PythonによるAIプログラミング入門 ―ディープラーニングを始める前に身につけておくべき15の基礎技術

7章ヒューリスティック探索

本章では、解の空間を効率よく探索して正解を得るヒューリスティック探索を説明します。以下の項目について学びます。

• ヒューリスティック探索
• 情報あり探索 vs. 情報なし探索
• 制約充足問題
• 局所探索手法
• 焼きなまし法（シミュレーテッドアニーリング）
• 貪欲法を用いた文字列の構築
• 制約条件のある問題の解法
• 領域の色分け問題の解法
• 8パズルの解法
• 迷路の解法

7.1　ヒューリスティック探索とは？

探索とデータの組織化は、人工知能の重要な課題です。解の空間の中から正解を探索することが必要な問題はたくさんあります。解の可能性が多数あると、どれが正解なのかわかりません。効率よくデータを組織化すれば、解を高速かつ効率的に探索できます。

問題を解く上で選択肢が多すぎるため、正解を見つけるアルゴリズムが存在しないことがよくあります。さらに、すべての解の可能性をしらみつぶしに調べるのは、時間がかかりすぎて非現実的なこともあります。このような場合に、明らかに解でない選択肢を除去することによって、探索範囲を狭めるのに役立つ経験則があります。このような経験則のことを、ヒューリスティックス（heuristic）と呼びます。また、ヒューリスティックスに従って探索を導く手法のことを、ヒューリスティック探索（heuristic search）と言います。

ヒューリスティックスは、処理を高速化するのに役立ちます。ヒューリスティックスによって選択肢を完全には除去できない場合でも、より良い解に早くたどり着けるように選択肢を並べ直すのに役立ちます。

7.1.1　情報あり探索と情報なし探索

計算機科学に詳しければ、深さ優先探索（depth first search：DFS）や幅優先探索（breadth ...