C復習９ 迷路の経路探索
Embedded Files
迷路のスタートとゴールを設定し、スタートからゴールを目指すゲームにします。そこで、スタートとゴールは、できるだけ遠い位置に設定します。この時役立つアルゴリズムとして、経路探索法があります。ここでは比較的ロジックが単純な深さ優先探索法と幅優先探索法を説明します。
経路探索のプログラムでは、Ｃ言語応用編で勉強したリスト構造を使います。Ｃ応用編では詳しく説明していなかったスタック構造やキュー構造を使ったプログラムになります。
ここで紹介するプログラムは、前章の「Ｃ復習 迷路の自動生成」でダウンロードしたプログラムに、右記のYoutube動画の説明の所に記載のURLからダウンロードしたプログラムを上書きして作成します。
本章のプログラムはWindowsターミナルでは旨く動作しません。Windowsコンソールホストで実行してください。
Windows11(2022Update)では既定のコンソールウィンドウがWindowsターミナルになっているため、Windowsコンソールホストに切替える必要があります。Windowsコンソールホストへの切替え方法が分からない人は、下記の動画を参照ください。
１．深さ優先探索と幅優先探索の迷路探索イメージ
１．深さ優先探索と幅優先探索の迷路探索イメージ
２．経路探索で使うプログラミング技術
２．経路探索で使うプログラミング技術
過去にリスト構造を説明していた動画「C言語応用8.4 リスト構造 」
３．深さ優先探索におけるプッシュとポップの動き
３．深さ優先探索におけるプッシュとポップの動き
４．幅優先探索におけるエンキューとデキューの動き
４．幅優先探索におけるエンキューとデキューの動き
５．main.cppの変更箇所の説明
５．main.cppの変更箇所の説明
６．深さ優先と幅優先のプログラムの違い(リスト操作)
６．深さ優先と幅優先のプログラムの違い(リスト操作)
７．深さ優先と幅優先のプログラムの違い(最長距離検索)
７．深さ優先と幅優先のプログラムの違い(最長距離検索)
Page updated
Google Sites
Report abuse