第2章|人工知能をめぐる動向
DAY 06 ・ 約30分探索で答えへたどり着く
状態空間・幅優先・深さ優先・ヒューリスティックを学ぶ。
探索問題を状態・行動・ゴール・コストへ分解し、幅優先探索、深さ優先探索、A*探索の違いを説明して、目的に合う方法を選べる。
言葉を知る
用語を暗記するだけでなく、似た概念との違いと、何を判断するための言葉かまで整理します。
状態空間
問題の途中経過として取り得る状態の全体です。現在地、持っている物、未完了の作業など、目的に必要な情報だけを状態として表します。
探索木
開始状態から可能な行動を枝として広げ、到達できる状態を木の形で表したものです。同じ状態へ別経路で着く場合もあります。
幅優先探索
開始点に近い状態から順番に調べる方法です。各行動のコストが同じなら、最も手数の少ない解を見つけられますが、記憶量が増えやすくなります。
深さ優先探索
一つの経路を先へ進め、行き止まりで戻る方法です。必要な記憶は比較的少ない一方、深い外れ道へ入り、最短解を保証できないことがあります。
ヒューリスティック
ゴールまでの残りやすさを見積もる経験的な手掛かりです。正解そのものではなく、先に調べる候補を選ぶ案内役です。
A*探索
開始から現在までの実コストと、現在からゴールまでの推定コストを足し、合計が小さい候補を優先する探索方法です。
行動コスト
そのときは行動コストを扱える一様コスト探索などを考えます。
仕組みを理解する
1.問題を、状態・行動・ゴールへ置き換える
探索は、たくさんの候補から目的を満たす道筋を見つける考え方です。最初に開始状態を決めます。経路案内なら現在地、パズルなら最初の配置、作業計画なら未完了の仕事と利用できる人員です。次に、ある状態から実行できる行動と、その結果できる次の状態を決めます。最後に、何を満たせば終了かというゴール判定を置きます。 状態へ何でも入れればよいわけではありません。配送経路に担当者の好きな音楽を加えても、通常は解へ影響せず、状態数だけが増えます。一方、一方通行、積載量、配達期限を外すと、計算上は短くても実行できない経路になります。前章のフレーム問題と同じく、現実を目的に必要な情報へ切り取る設計が先です。探索アルゴリズムは、問題の表し方が間違っていれば正しい答えを出せません。
2.幅優先探索は、近い候補を漏れなく広げる
幅優先探索は、開始状態から一手で行ける場所をすべて調べ、次に二手、三手と層ごとに広げます。迷路で各移動の重さが同じなら、最初にゴールへ着いた経路が最少手数です。問い合わせの会話手順や、リンクを何回たどれば目的ページへ着くかなど、段階数が重要な問題にも使えます。 代わりに、同じ深さの候補を多く保存する必要があります。一つの状態から十通りへ分かれる問題では、深さが増えるごとに候補が急増します。すべてを記憶へ置けない場合、幅優先だけでは進みません。また、道路ごとに距離や時間が違う場合、手数が少ない経路と費用が小さい経路は一致しません。そのときは行動コストを扱える一様コスト探索などを考えます。
3.深さ優先探索は、一つの道を先に確かめる
深さ優先探索は、一つの候補を選んで可能な限り先へ進みます。行き止まりや条件違反になったら直前の分岐へ戻り、別の道を試します。探索中に主に覚えるのは現在の経路と未確認の分岐なので、幅優先より記憶量を抑えやすい方法です。解が深い場所にあり、どこか一つ見つかればよい場合は早く着く可能性があります。 ただし、終わりのない道や非常に深い外れ道へ入ると、近くにある解を長く見つけられません。循環する状態を訪問済みとして管理しなければ、同じ場所を回り続けます。最初に見つけた解が最短とも限りません。深さ上限を決める、上限を少しずつ増やす反復深化を使うなど、問題の深さと利用できる記憶に合わせて調整します。
4.コストを入れると、『近い』の意味が変わる
地図では一回の移動でも、道路によって距離、時間、料金、危険度が違います。そこで各行動へコストを付け、開始から現在までに使った合計をgとします。一様コスト探索は、手数ではなくgが最も小さい候補を先に広げます。すべてのコストが負でなければ、最小コストの解を見つけられます。 何をコストへ含めるかは目的設定です。配送時間だけを小さくすれば高速道路料金が増えるかもしれません。金額だけなら遅配が増えるかもしれません。絶対に守る積載量や法令は制約として候補から外し、時間と費用は比較項目として重みを付ける方法があります。探索の正しさは、計算だけでなく、コストが現実の価値を表しているかで決まります。
5.ヒューリスティックは、先に調べる方向を教える
候補を全部同じように調べる代わりに、ゴールへ近そうな候補を推定します。地図なら現在地から目的地までの直線距離、パズルなら正しい位置から外れた部品数などです。この推定値をhとします。hだけが小さい候補を選ぶ貪欲最良優先探索は、早くゴールへ向かいやすい一方、途中の遠回りや高い費用を軽視します。 ヒューリスティックは未来を完全に知る値ではありません。計算が軽く、候補の良し悪しをある程度区別できることが重要です。推定の作成に本問題と同じ時間がかかれば意味がありません。直線距離は実際の道路距離より小さくなりやすく、安く計算できます。どの推定が役立つかは、問題の構造とゴールの定義に依存します。
6.A*探索は、ここまでと残りの両方を見る
A*探索は、開始から現在までの実コストgと、現在からゴールまでの推定hを足したf=g+hが小さい候補を優先します。hだけを見る貪欲探索と違い、すでに大きな遠回りをした候補を避けられます。hが常にゼロなら、一様コスト探索と同じ動きになります。推定がよければ、最適性を保ちながら調べる候補を大きく減らせます。 hが本当の残りコストを決して過大評価しない性質を許容的と呼びます。さらに隣接状態の間で推定が不自然に減らない整合性があると、同じ状態の再処理を抑えやすくなります。用語だけでは難しく見えますが、「近道だと楽観し過ぎて有望な道を捨てない」「進むたびに見積りが矛盾しない」という意味です。最短経路を保証する条件は、アルゴリズム名だけでなく、コストとhの性質まで含みます。
7.探索の性能は、正解・時間・記憶で評価する
探索方法は、解があれば見つけられる完全性、最小コスト解を得られる最適性、必要な計算時間、必要な記憶量で比較します。すべてに常に優れた方法はありません。幅優先は浅い最短解に強くても記憶を使い、深さ優先は記憶を抑えても外れ道へ入ります。A*も推定が弱ければ多くの候補を保存します。 実務では制限時間内に十分よい解を返すことも必要です。候補数、処理時間、費用へ上限を置き、上限到達時に暫定案を返すか、人へ戻すかを決めます。動的な交通や在庫では、探索中に世界が変わります。一度の最適解へ固執せず、変化を検知して再計算する設計が必要です。探索は万能な思考ではなく、明示した世界の中で候補を比較する仕組みです。
8.DAY 6では、小さな探索木を自分で描く
出発地から目的地まで三つの経路がある例を作ってください。各地点を状態、移動を行動として矢印で結び、距離をコストとして書きます。まず幅優先ならどの順番で調べるか、深さ優先ならどう進むかを番号で示します。次に目的地までの直線距離をhとして、g+hを計算します。 最後に、最短距離以外に守る条件を一つ加えます。通行止め、料金上限、営業時間などです。その条件を状態、制約、コストのどこへ入れるべきか説明します。順番だけでなく、問題の表現と評価の違いを言葉にできれば、探索を暗記ではなく設計として理解できています。
9.重複状態を管理しなければ、同じ場所を何度も調べる
探索木では、別の行動順から同じ状態へ到達することがあります。AからBを経てCへ行く経路と、AからDを経てCへ行く経路があれば、C以降の候補は共通です。訪問済み集合や、その状態へ到達した最小コストを記録すれば、同じ計算の繰り返しを減らせます。このように状態を共有して表すと、木ではなくグラフとして扱います。 ただし「同じ状態」の定義が重要です。現在地が同じでも、荷物、時刻、残り燃料が違えば、その後に可能な行動は変わります。必要な情報を落として同一扱いすると、実行可能な解を捨てることがあります。反対に不要な履歴をすべて含めれば、同じ状況を再利用できません。重複管理も状態設計の一部です。
10.生成AIの計画も、探索として点検できる
生成AIへ複数手順の仕事を頼むと、もっともらしい計画を一つ文章で返します。しかし、候補を比較したのか、制約をすべて確認したのかは文章だけでは分かりません。重要な計画では、可能な選択肢、各案の費用、守る条件、停止条件を明示させ、外部の計算や資料で確かめます。 候補を大量に生成するだけでは探索の品質は上がりません。重複案を除き、評価基準を固定し、上限内で比較します。実行後に状態が変わったら、古い計画を続けず現在状態から再計画します。探索の枠組みを使うと、「考えて」と頼むだけだった処理を、検証可能な候補選択へ変えられます。
実例で理解する
具体例で考える
倉庫で、作業員が入口から商品棚を回り、梱包台へ戻る経路を考えます。状態は現在位置、回収済み商品、台車の積載量です。行動は隣の通路への移動と商品の回収、ゴールは必要商品をすべて回収して梱包台へ着くことです。コストには移動距離だけでなく、混雑通路の待ち時間を加えます。 幅優先では移動回数の少ない経路を見つけられますが、長い通路と短い通路を同じ一手として扱います。一様コスト探索は実距離を比べます。A*では、現在地から未回収棚と梱包台までの直線距離を残りの目安にします。ただし、直線距離には壁や一方通行が入らないため推定です。 危険物は資格者だけが回収する、台車の上限を超えないという条件は、安さと交換できない制約にします。通路閉鎖が発生したら現在状態から再探索します。最短経路という言葉だけで終わらず、状態、コスト、推定、制約、再計算まで決めることで現実に使える計画になります。 さらに、同じ棚へ別の通路から着いた場合は、現在位置だけでなく回収済み商品と残り積載量まで一致するかを確かめます。一致すれば安い方の経路を残し、一致しなければ別状態として探索を続けます。これにより、重複計算を減らしながら必要な選択肢を失わずに済みます。
手を動かして理解する
- 提供ケース「紙に描いた小さな配送経路を、状態・行動・ゴール・規則へ分解する」または自分が説明できる身近な事例を一つ選び、DAY6「探索で答えへたどり着く」の判断観点で整理してください。提出物には、①対象と目的、②本文の用語を使った判断、③判断の根拠、④未確認事項または限界を記します。最後に学習目標「探索問題を状態・行動・ゴール・コストへ分解し、幅優先探索、深さ優先探索、A*探索の違いを説明して、目的に合う方法を選べる。」を満たす説明になっているか自己確認してください。紙または端末の標準メモだけで実施でき、外部サービスへの登録や有料契約は不要です。 実在人物の個人情報、機密情報、未公開資料は使わず、架空または匿名化した情報だけを使ってください。
04|今日の理解度を確認する
今日の理解度を確認する
探索問題を設計するとき、最初に明確にする組合せはどれですか。
正解は「状態・可能な行動・ゴール・コスト」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
状態・可能な行動・ゴール・コスト: 正解は「状態・可能な行動・ゴール・コスト」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
モデル名・会社名・広告文・色: 製品情報だけでは何を候補として調べるか決まりません。
画面サイズ・字体・写真・音量: 表示要素は探索問題の定義ではありません。
回答速度だけ: 速度だけでは正しいゴールや実行可能性を判断できません。
各行動のコストが同じで、最少手数の解を確実に見つけたい場合の基本的な選択はどれですか。
正解は「幅優先探索」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
幅優先探索: 正解は「幅優先探索」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
深さ優先探索: 深さ優先探索は最初に見つけた解が最短とは限りません。
無作為に一つ選ぶ: 無作為選択は最少手数を保証しません。
評価せず最初の案を採用する: 比較を省くと最少手数を判断できません。
深さ優先探索の特徴として適切なものはどれですか。
正解は「現在の経路を中心に保持するため記憶を抑えやすいが、深い外れ道へ入ることがある」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
現在の経路を中心に保持するため記憶を抑えやすいが、深い外れ道へ入ることがある: 正解は「現在の経路を中心に保持するため記憶を抑えやすいが、深い外れ道へ入ることがある」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
必ず最小コスト解を最初に返す: 最短・最小コストの保証は基本形にはありません。
同じ深さの全候補を必ず保存する: これは幅優先探索に近い保存方法です。
ヒューリスティックがなくても未来を完全に予測する: 探索は未来を完全に知る仕組みではありません。
A*探索で候補の優先度に使う値はどれですか。
正解は「開始から現在までの実コストgと残り推定hの合計」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
開始から現在までの実コストgと残り推定hの合計: 正解は「開始から現在までの実コストgと残り推定hの合計」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
残り推定hだけ: hだけなら貪欲最良優先探索の考え方です。
現在までの手数を無視した広告評価: 現実のコストを無視すると最適性を判断できません。
候補を作った時刻だけ: 作成時刻は経路の価値を表しません。
許容的なヒューリスティックの説明として適切なものはどれですか。
正解は「本当の残りコストを過大評価しない推定」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
本当の残りコストを過大評価しない推定: 正解は「本当の残りコストを過大評価しない推定」です。講義で扱った定義と判断条件に一致します。選択肢ごとの違いまで確認すると、似た用語を状況に応じて使い分けられます。
必ず本当の残りコストと完全一致する値: 一致は必須ではなく、推定値です。
実コストを無視して大きく見積もる値: 過大評価は有望な経路を早く捨てる原因になります。
ゴール判定を不要にする規則: 推定があってもゴールへ到達したかの判定は必要です。
04|今日の理解度を確認する
今日の理解度を確認する
今日の整理をする
この3点を持ち帰る
- ✓ 探索問題は、状態・行動・ゴール・コストを定義してから解く
- ✓ 幅優先・深さ優先・A*は、最適性・時間・記憶の性質が異なる
- ✓ ヒューリスティックは正解ではなく、有望な候補を先に調べるための推定である
講義本文 4,127字
PRIMARY SOURCES