Views
Document
Event
File
Folder
Image
Link
News Item
Photo
Photo Album
Topic
Weblog
Wiki Page
演習4
Document Actions
いつものように
- ~/da/ex4 でやる
Dijkstra のアルゴリズム
- dijkstra.py を実行してみる
- 最初のプログラムにバグがありました。修正しましたので、各自のプログラムを確認してください。
解の探索
- 教科書 7.2 (p135〜) 基本探索アルゴリズム (1〜3)
- 木の探索 ... search_tree.py をやってみる
- グラフの探索 ... search_graph.py やってみる（ここでは、図6.2のグラフ でなく、図7.2の木をグラフとみなしてデータを作成している）
- 親を登録 ... search_parent.py やってみる（同上）
問題
- q4-1.py ... 教科書図6.1の迷路(図6.11コスト付き迷路グラフ)に Dijkstra のアルゴリズムを適用して S から各点への最短経路を調べなさい。
- q4-2.py ... 木の探索を search_tree.py の「縦型検索」から「横型探索」に変更しなさい。
- q4-3.py ... 基本アルゴリズム３（親を登録）を教科書 図6.2 の迷路グラフに適用して、ゴールへの経路を求めなさい。
