Ibaraki Univ. Dept of Electrical & Electronic Eng.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
人工知能 ( Artificial Intelligence ) 状態空間表現と探索 State Space Representation and Search Lecture 2 田中美栄子.
Ibaraki Univ. Dept of Electrical & Electronic Eng. Keiichi MIYAJIMA
アルゴリズムとデータ構造 2011年7月7日
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
算法数理工学 第9回 定兼 邦彦.
    有限幾何学        第8回.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
2章 データ構造.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
An Algorithm for Enumerating Maximal Matchings of a Graph
Ibaraki Univ. Dept of Electrical & Electronic Eng.
情報科学1(G1) 2016年度.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
原案・解説 : 野田 解答 : 野田・吉田 Problem D Futon ~布団~.
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズム入門.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 2011年7月4日
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
人工知能概論 第2回 探索(1) 状態空間モデル,基本的な探索
WWW上の効率的な ハブ探索法の提案と実装
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
電子計算機工学 Keiichi MIYAJIMA Computer Architecture
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 2011年7月8日課題の復習
Ibaraki Univ. Dept of Electrical & Electronic Eng.
情報知能学科「アルゴリズムとデータ構造」
問題作成、解説担当:中島 副担当:坪坂、松本
Ibaraki Univ. Dept of Electrical & Electronic Eng.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 2013年7月8日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

Ibaraki Univ. Dept of Electrical & Electronic Eng. 2015. 7.15 アルゴリズムとデータ構造 Ibaraki Univ. Dept of Electrical & Electronic Eng. Keiichi MIYAJIMA

深さ優先探索

深さ優先探索 v1 v8 v2 v7 v6 v3 v4 v5 図のような無向グラフをどのように探索するか?

深さ優先探索 1 v1 v8 v2 v7 v6 v3 v4 v5 V1からスタートすると・・・

深さ優先探索 1 v1 2 v8 v2 v7 v6 v3 v4 v5 まずV2を探索

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 v4 v5 次にV3を探索

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 v4 v5 4 次にV4を探索

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 v4 v5 4 V2は既に探索しているので、いったんv3にもどって・・・

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 v4 v5 5 4 V5を探索

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 v4 v5 5 4 V5は行き止まりなので、v3に戻り、さらにv2までもどり・・・

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 6 v4 v5 5 4 V4はすでに探索済みなので、V6を探索

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 6 v4 v5 5 4 V6からv1は既に探索済みなので、いったんv2に戻り、さらにv1へ戻る

深さ優先探索 1 v1 2 v8 v2 3 v7 v6 v3 6 7 v4 v5 5 4 V7を探索

深さ優先探索 1 v1 2 v8 v2 8 3 v7 v6 v3 6 7 v4 v5 5 4 「深さ優先」なのでv1に戻らずに、v8を探索

深さ優先探索 1 v1 2 v8 v2 8 3 v7 v6 v3 6 7 v4 v5 5 4 全ての頂点を探索し終わったら終了

本日のまとめ TCP/IPアプリケーション  深さ優先探索

本日の課題 教科書p.132 図6.7の有向グラフを隣接リストを用いて作成し、深さ優先探索のプログラムを作成せよ。 実行結果は、各頂点vnが何番目に探索されたのかを表示するようにせよ。 注意) 表示法については、教科書には記述がない。自分で考えること。(自力で作成するorいろいろ調べる) ヒントとしては、通過した頂点の番号をそのまま表示させていくという方法がある。

グラフの表現 v2 v1 v5 v3 v4 隣接リスト ポインタ配列で表現する ポインタ配列の宣言 vertex *adjlist[5];

レポートの〆切と提出先 レポート提出先: E2棟(旧システム棟)6F606室(宮島教員室)前 レポートBOX レポート〆切: 7月21日火曜日 PM5:00頃

今後の予定 7月22日 幅優先探索 7月29日 難しい問題とその対応 8月5日 確認試験 レポートは本日分を含めて後3回です。