酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2012年7月9日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html.

Slides:



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

アルゴリズムとデータ構造 2011年7月7日
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
算法数理工学 第9回 定兼 邦彦.
2章 データ構造.
アルゴリズムとデータ構造 2012年7月19日
アルゴリズムとデータ構造 2012年7月23日
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2011年7月14日
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
最短経路.
アルゴリズム入門.
アルゴリズムとデータ構造 2013年7月18日
アルゴリズムとデータ構造 2012年7月12日
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
離散数学 08. グラフの探索 五島.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造1 2006年6月16日
オブジェクト指向 プログラミング 第七回 知能情報学部 新田直也.
アルゴリズム入門.
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造 2011年7月12日
アルゴリズムとデータ構造 2012年7月17日
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
離散数学 07. 木 五島.
アルゴリズムとデータ構造1 2005年7月5日
復習+α JBuilderの使い方を思い出す。 配列とGUI 再帰とマージソート 木と二分木の探索
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2011年7月8日課題の復習
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
アルゴリズムからプログラムへ GRAPH-SEARCH
離散数学 06. グラフ 序論 五島.
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
データ構造と アルゴリズムI 第三回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
Presentation transcript:

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2012年7月9日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

グラフの定義(225ページ) グラフは頂点の集合と辺の集合からなる。 グラフには有向グラフと無向グラフがある。 グラフに対する、教科書4章の仮定。 (v, v)の形の辺(NDAのε遷移みたいなの)はない。 頂点uからvへ結ぶ辺は高々1つ。 辺の属性として数値を持つ場合、重みという。 いくつかの辺をつないでできる経路は道。 有向グラフでは辺はすべて同じ向きをたどる。 頂点からその頂点自身への道は閉路。 木はグラフの一種。

グラフの定義(つづき) 木が複数集まったグラフは森という。 頂点につながる辺の数を次数という。 正則グラフでは全頂点の次数が同じ。 木と木がつながっていなくてもいい。 頂点につながる辺の数を次数という。 有向グラフでは、入次数・出次数と区別する。 正則グラフでは全頂点の次数が同じ。 このときの次数をグラフの次数とする場合がある。 ハイパーキューブなど グラフ全体を組織的に調べることを探索という。 ただし、単に頂点を訪問するだけ、かもしれない。

グラフアルゴリズムの計算量 頂点数をnとしたときの最大の辺の数mは、 無向グラフでは 有向グラフでは 辺の数が最大のものを完全グラフという。 辺の数が0でもグラフである。 密なグラフか、疎なグラフか。 次数がある程度以下なら疎と考える。 「ある程度」とは、問題に依存する。 CCC(Cude Connected Cycle)なら次数は3。疎? 人工的なネットワークか、自然なネットワークか。

グラフの表現法(230ページ) 隣接行列 配列やListやSetやMapによる表現 計算で求める 頂点から頂点への接続の有無や辺の重みを持つ 密なグラフにはいい 配列やListやSetやMapによる表現 正則グラフなら配列 二分探索木のような順序木のグラフならList 無向グラフならListでもSetでもMapでもいい MapならKeyを接続先の頂点、Valueを重みにするなど 計算で求める 配列上のヒープソートの、部分順序つき二分木 スパコン内部ネットワークなど

4-dimentional binary hyper cube 0100 0101 1100 1101 0110 0111 1110 1111 0000 0001 1000 1001 0010 0011 1010 1011 4-dimentional binary hyper cube

深さ優先探索 A B C A D B E C F A D B G E C F D G E F G (234ページ) 1 7 2 1 6 5 図4.3.2 a 3 2 5 4 4 図4.3.2 b 6 3 木の辺(実線で表示) 逆辺(点線で表示) 連結グラフなら木が得られ、  そうでなければ森が得られる 7 図4.3.3

グラフの頂点を表すクラス (4.3と4.4で使う) public class Node<E> { private E value; // 頂点の値 private Collection<Node<E>> edges; // 有向辺 private boolean visited; private int sequence; private boolean searching; public Node(E value, Collection<Node<E>> edges) { this.value = value; this.edges = edges; reset(); } public void reset(){ this.visited = false; this.sequence = 0; this.edges.clear(); this.searching = false; public E getValue() { // 頂点の値を得る。 return value; public Collection<Node<E>> getEdges(){ return this.edges; public boolean isVisited() { return visited; } public void setVisited(boolean v) { this.visited = v; public int getSequence() { return sequence; public void setSequence(int s) { this.sequence = s; public boolean isSearching() { return searching; public void setSearching(boolean s) { this.searching = s; public void connect(Node<E> to){ this.edges.add(to); //無向辺を追加 if( !to.getEdges().contains(this) ){ to.getEdges().add(this); public void connectTo(Node<E> to){ this.edges.add(to); //有向辺を追加 グラフの頂点を表すクラス (4.3と4.4で使う)

テストデータのうち、 グラフの頂点とその集合 深さ優先探索のプログラム public class DepthFirstSearch { private static Node<Character> nodeA = new Node<Character>('A', new LinkedList<Node<Character>>()); private static Node<Character> nodeB = new Node<Character>('B', new LinkedList<Node<Character>>()); private static Node<Character> nodeC = new Node<Character>('C', new LinkedList<Node<Character>>()); private static Node<Character> nodeD = new Node<Character>('D', new LinkedList<Node<Character>>()); private static Node<Character> nodeE = new Node<Character>('E', new LinkedList<Node<Character>>()); private static Node<Character> nodeF = new Node<Character>('F', new LinkedList<Node<Character>>()); private static Node<Character> nodeG = new Node<Character>('G', new LinkedList<Node<Character>>()); private static Collection<Node<Character>> test_data = new LinkedList<Node<Character>>(); static { test_data.add(nodeA); test_data.add(nodeB); test_data.add(nodeC); test_data.add(nodeD); test_data.add(nodeE); test_data.add(nodeF); test_data.add(nodeG); } public class DepthFirstSearch { private static <E> void visit(Node<E> node){ node.setVisited(true); System.out.print(node.getValue()); for(Node<E> neighbor: node.getEdges()){ if(neighbor.isVisited()) continue; // 訪問済み System.out.print(" -> "); visit(neighbor); } public static <E> void search(Collection<Node<E>> graph){ for(Node<E> node: graph){ if(node.isVisited()) continue; // 訪問済み System.out.println(node.getValue() + "から探索します。"); visit(node); System.out.println(); テストデータのうち、 グラフの頂点とその集合 深さ優先探索のプログラム

A -> C -> E -> G -> F -> D -> B 図4.3.4 Aから探索します。 public static void main(String[] args) { System.out.println("図4.3.2"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); nodeA.connect(nodeB); nodeC.connect(nodeE); nodeC.connect(nodeF); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); search(test_data); public static void main(String[] args) { System.out.println("図4.3.3"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); nodeA.connect(nodeB); nodeC.connect(nodeF); nodeC.connect(nodeE); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); search(test_data); public static void main(String[] args) { System.out.println("図4.3.4"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connectTo(nodeC); nodeA.connectTo(nodeD); nodeA.connectTo(nodeE); nodeC.connectTo(nodeB); nodeB.connectTo(nodeA); nodeD.connectTo(nodeC); nodeD.connectTo(nodeE); nodeF.connectTo(nodeA); nodeF.connectTo(nodeG); search(test_data); 図4.3.2 Aから探索します。 A -> C -> E -> G -> F -> D -> B 図4.3.4 Aから探索します。 A -> C -> B -> D -> E Fから探索します。 F -> G 図4.3.3 Aから探索します。 A -> C -> F -> D -> B -> E -> G

B C E D F G A B C E D F G A 上昇辺 子孫から祖先へ向かう辺 無向グラフでは逆辺 上昇辺  子孫から祖先へ向かう辺  無向グラフでは逆辺 下降辺  祖先から子孫へ向かう辺  無向グラフでは逆辺 交差辺  上昇辺でも下降辺でもない辺 図4.3.4 a 交差辺 1 連結グラフとは、グラフ全体が つながっていること。無向グラフ では、深さ優先探索で全ての 頂点をたどる事ができれば連結 グラフである。 しかし、有向グラフでは必ずしも そうとはならない。 上昇辺 6 B C E D F G A 3 下降辺 7 5 2 4 図4.3.4 b 交差辺

有向グラフの深さ優先探索 (240ページ) public class DirectedDepthFirstSearch<E> { private int sequence; private void visit(Node<E> node){ node.setVisited(true); node.setSequence(++this.sequence); node.setSearching(true); System.out.print(node.getValue()); for(Node<E> neighbor: node.getEdges()){ if(neighbor.getSequence() == 0){ System.out.print(" -> "); visit(neighbor); // 木の辺 } else if (neighbor.getSequence() > node.getSequence()) { System.out.print(" 下降辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); } else if (neighbor.isSearching()){ System.out.print(" 上昇辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); } else { System.out.print(" 交差辺(" + node.getValue() + ", " + neighbor.getValue() + ")"); }} node.setSearching(false); } public void search(Collection<Node<E>> graph){ this.sequence = 0; for(Node<E> node: graph){ if(node.getSequence() == 0){ System.out.println(node.getValue() + "から探索します。"); visit(node); System.out.println(); }}}} 有向グラフの深さ優先探索 (240ページ)

A -> C -> B 上昇辺(B, A) -> D 交差辺(D, C) -> E 下降辺(A, E) public static void main(String[] args) { System.out.println("図4.3.4"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connectTo(nodeC); nodeA.connectTo(nodeD); nodeA.connectTo(nodeE); nodeC.connectTo(nodeB); nodeB.connectTo(nodeA); nodeD.connectTo(nodeC); nodeD.connectTo(nodeE); nodeF.connectTo(nodeA); nodeF.connectTo(nodeG); new DirectedDepthFirstSearch<Character>().search(test_data); 図4.3.4 Aから探索します。 A -> C -> B 上昇辺(B, A) -> D 交差辺(D, C) -> E 下降辺(A, E) Fから探索します。 F 交差辺(F, A) -> G

(Directed Acyclic Graph) トポロジカルソート (242ページ) Topology は「位相」のこと。トポロジカルソートのときはこちら。 Phase も「位相」と訳せます。ベクタの位相はこちら。 たとえば、ベクターがあったとします。 大きさ0 大きさを比較することは できますが、大きさが同じ だからといって同じベクター であるとは限りませんよね? 大きさ2 大きさ5    全要素間で順序がつけられる → 全順序関係 一部の要素間に順序がつけられる → 半順序関係 同じだけど同じじゃない、というのは順序がつけられて ません。そういうデータは、DAGで保持することができる。 簡単に説明しすぎ? 図4.3.6 DAG (Directed Acyclic Graph)

幅優先探索 A B C D A B E F C G D E F G (244ページ) 1 4 2 図4.3.2 a 3 5 6 7 図4.3.7

public class BreadthFirstSearch { public static <E> void search(Collection<Node<E>> graph){ Queue<Node<E>> queue = new LinkedList<Node<E>>(); // FIFO for(Node<E> node: graph){ if(node.isVisited()){ continue; // 訪問済み } queue.add(node); // enqueue node.setVisited(true); while( !queue.isEmpty() ){ Node<E> next = queue.remove(); // dequeue System.out.print("頂点" + next.getValue()); for(Node<E> neighbor: next.getEdges()){ if( neighbor.isVisited() ){ continue; queue.add(neighbor); // enqueue neighbor.setVisited(true); System.out.print(" 辺(" + next.getValue() + ", " + neighbor.getValue() + ")"); System.out.print(" -> "); System.out.println();

頂点A 辺(A, C) 辺(A, D) 辺(A, B) -> 頂点C 辺(C, E) 辺(C, F) -> 頂点D -> public static void main(String[] args) { System.out.println("図4.3.7"); for(Node<Character> node: test_data){ node.reset(); } nodeA.connect(nodeC); nodeA.connect(nodeD); nodeA.connect(nodeB); nodeC.connect(nodeE); nodeC.connect(nodeF); nodeD.connect(nodeB); nodeD.connect(nodeF); nodeE.connect(nodeG); nodeE.connect(nodeF); search(test_data); 図4.3.7 頂点A 辺(A, C) 辺(A, D) 辺(A, B) -> 頂点C 辺(C, E) 辺(C, F) -> 頂点D -> 頂点B -> 頂点E 辺(E, G) -> 頂点F -> 頂点G ->

BreadthFirstSearchのFIFO(リスト)を LIFO(スタック)に変えたもの。 この変更により、幅優先探索だったプログラムが public class DepthFirstSearchStack { public static <E> void search(Collection<Node<E>> graph){ Stack<Node<E>> stack = new Stack<Node<E>>(); // LIFO for(Node<E> node: graph){ if(node.isVisited()){ continue; // 訪問済み } stack.push(node); // push node.setVisited(true); while( !stack.empty() ){ Node<E> next = stack.pop(); // pop System.out.print("頂点" + next.getValue()); for(Node<E> neighbor: next.getEdges()){ if( neighbor.isVisited() ){ continue; stack.add(neighbor); // push neighbor.setVisited(true); System.out.print(" -> "); System.out.println(); BreadthFirstSearchのFIFO(リスト)を LIFO(スタック)に変えたもの。 この変更により、幅優先探索だったプログラムが 深さ優先探索プログラムになる。 (247ページ)