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

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

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2013年7月16日

2 最短路の問題 （２６０ページ） 最短路問題 対象は辺に重みのついた有向グラフ 問題は大きく２種類ある
グラフの２頂点間を結ぶ道のうちで辺の重みの和が最小のものを求める問題。 対象は辺に重みのついた有向グラフ 問題は大きく２種類ある 出発点を１つに固定して、そこから他のすべての頂点への最短路を求める。 すべての２頂点の組み合わせに対して、最短路を求める。 １の方法をすべての頂点に適用するのが最善。

3 単一出発点の問題 （２６１ページ） Ｄｉｊｋｓｔｒａのアルゴリズム 各頂点への最短路を出発点に近いところからひとつづつ確定する。 Ｃ Ｄ Ｆ
確定した頂点から行くことのできる 頂点への距離を計算。 図４.５.１　アルゴリズムの動き Ｃ Ｄ Ｆ Ｅ Ａ Ｂ ６ ３ ４ ２ １ ６ ６ ８ ９ ８ 出発点 Ａ ７ ７ 最小の距離を持つ頂点は確定。 他から来るにしても重みが負の 経路がなければ、距離は減らない。 ４ ４ １０ １０

4 本日使う頂点のデータ構造 辺に重みを持たせるため、Ｍａｐを使う。 出発点からの距離 辺の重み
public class WeightedNode<E> { private E value; // 頂点の値 private Map<WeightedNode<E>, Integer> edges; //　有向辺 private boolean visited; private int distance; public WeightedNode(E value, Map<WeightedNode<E>, Integer> edges) { this.value = value; this.edges = edges; reset(); } public void reset(){ this.visited = false; this.distance = Integer.MAX_VALUE; this.edges.clear(); public E getValue() { // 頂点の値を得る。 return value; public Map<WeightedNode<E>, Integer> getEdges(){ return this.edges; // アクセッサは、このスライドでは省略した。実際には存在する。 public void connectTo(WeightedNode<E> to, int weight){ this.edges.put(to, weight); // 有向辺を追加 辺に重みを持たせるため、Ｍａｐを使う。 出発点からの距離 辺の重み 本日使う頂点のデータ構造

5 教科書２６３ページの擬似プログラムをＪａｖａで実装
public class Dijkstra { public static <E> void search(Collection<WeightedNode<E>> graph, WeightedNode<E> start){ Set<WeightedNode<E>> visited = new HashSet<WeightedNode<E>>(); Set<WeightedNode<E>> unreached = new HashSet<WeightedNode<E>>(graph); start.setDistance(0); while( !unreached.isEmpty() ){ int min_distance = Integer.MAX_VALUE; WeightedNode<E> min_node = null; for(WeightedNode<E> node: unreached){ if(node.getDistance() < min_distance){ min_distance = node.getDistance(); min_node = node; } unreached.remove(min_node); visited.add(min_node); for(Map.Entry<WeightedNode<E>,Integer> edge: min_node.getEdges().entrySet()){ if(unreached.contains(edge.getKey())){ edge.getKey().setDistance( Math.min(edge.getKey().getDistance(), min_node.getDistance() + edge.getValue())); 集合Ｖ 集合Ｕ 集合Ｕから最小の距離をもつ頂点を探索 Ｊａｖａだと楽勝。 教科書２６３ページの擬似プログラムをＪａｖａで実装

6 ひとつずつ確定する作戦の前提として、 辺の重みは正の値である。 図4.5.1 頂点Aからの距離 頂点A: 0 頂点B: 6 頂点C: 4
private static WeightedNode<Character> nodeA = new WeightedNode<Character>('A', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodeB = new WeightedNode<Character>('B', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodeC = new WeightedNode<Character>('C', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodeD = new WeightedNode<Character>('D', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodeE = new WeightedNode<Character>('E', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodeF = new WeightedNode<Character>('F', new HashMap<WeightedNode<Character>, Integer>()); private static Collection<WeightedNode<Character>> test_data = new LinkedList<WeightedNode<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); } public static void main(String[] args) { System.out.println("図4.5.1"); for(WeightedNode<Character> node: test_data){ node.reset(); nodeA.connectTo(nodeB, 6); nodeA.connectTo(nodeC, 4); nodeB.connectTo(nodeD, 3); nodeC.connectTo(nodeE, 3); nodeC.connectTo(nodeF, 6); nodeE.connectTo(nodeB, 2); nodeE.connectTo(nodeD, 1); search(test_data, nodeA); System.out.println("頂点" + nodeA.getValue() + "からの距離"); System.out.println("頂点" + node.getValue() + ": " + node.getDistance()); ひとつずつ確定する作戦の前提として、 辺の重みは正の値である。 図4.5.1 頂点Aからの距離 頂点A: 0 頂点B: 6 頂点C: 4 頂点D: 8 頂点E: 7 頂点F: 10

7 ２６３ページの実装では、集合Ｕから最小の距離をもつ 頂点を線形探索し、集合Ｕから移動していた。 そもそも、線形探索は時間計算量が多い。
２６３ページの実装では、集合Ｕから最小の距離をもつ 　頂点を線形探索し、集合Ｕから移動していた。 そもそも、線形探索は時間計算量が多い。 そこで、集合Ｕの替わりにヒープを使うことを考える。 ただし、リストのようなデータ構造でヒープを実装するのは、 　データ操作に必要な時間計算量の多さから不適切である。 ヒープとしては頂点への参照を入れた配列を使うことにする。 最小の距離を持つ頂点をヒープから移動し、ヒープを再構成する。 実装は省略しますが、２６３ページの擬似プログラムが単純なので、 それを理解してみるといいだろう。それから２６７ページを理解する。 というか、集合の実装にＨａｓｈＳｅｔは不適切だとしても、ヒープを自前で実装するのもアレなので、もっと便利なクラスを使うべきです。何を使えばいいでしょうか？ ヒープの復習のために自前で実装するのはアリですが、すでに学習済みならＤｉｊｋｓｔｒａアルゴリズムの学習のために楽してもいいでしょう。

8 ２６５ページのプログラムのＪａｖａ実装 頂点の配列と、頂点同士の接続行列 public class DijkstraArray {
public static <E> void search(WeightedNode<E>[] nodes, int start, int[][] weights){ nodes[start].setDistance(0); for(int step = 0; step < nodes.length; step++){ int min = Integer.MAX_VALUE; int p = 0; for(int x = 0; x < nodes.length; x++){ if( !nodes[x].isVisited() && (nodes[x].getDistance() < min)){ p = x; min = nodes[x].getDistance(); } if(min == Integer.MAX_VALUE){ throw new IllegalArgumentException("グラフが連結でない。"); nodes[p].setVisited(true); if(weights[p][x] == Integer.MAX_VALUE){ continue; nodes[x].setDistance( Math.min(nodes[x].getDistance(), nodes[p].getDistance() + weights[p][x])); 頂点の配列と、頂点同士の接続行列 ２６５ページのプログラムのＪａｖａ実装

9 これもＤｉｊｋｓｔｒａのアルゴリズムなので、 ひとつずつ確定する作戦の前提として、 辺の重みは正の値である。
private static WeightedNode<Character> nodeA = new WeightedNode<Character>('A'); private static WeightedNode<Character> nodeB = new WeightedNode<Character>('B'); private static WeightedNode<Character> nodeC = new WeightedNode<Character>('C'); private static WeightedNode<Character> nodeD = new WeightedNode<Character>('D'); private static WeightedNode<Character> nodeE = new WeightedNode<Character>('E'); private static WeightedNode<Character> nodeF = new WeightedNode<Character>('F'); @SuppressWarnings("unchecked") private static WeightedNode<Character>[] test_data = new WeightedNode[] { nodeA, nodeB, nodeC, nodeD, nodeE, nodeF }; public static void main(String[] args) { System.out.println("図4.5.1"); for(WeightedNode<Character> node: test_data){ node.reset(); } int[][] weights = new int[test_data.length][test_data.length]; for(int[] from: weights){ for(int i = 0; i < from.length; i++){ from[i] = Integer.MAX_VALUE; weights[0][1] = 6; weights[0][2] = 4; weights[1][3] = 3; weights[2][4] = 3; weights[2][5] = 6; weights[4][1] = 2; weights[4][3] = 1; search(test_data, 0, weights); System.out.println("頂点" + nodeA.getValue() + "からの距離"); System.out.println("頂点" + node.getValue() + ": " + node.getDistance()); 図4.5.1 頂点Aからの距離 頂点A: 0 頂点B: 6 頂点C: 4 頂点D: 8 頂点E: 7 頂点F: 10 これもＤｉｊｋｓｔｒａのアルゴリズムなので、 ひとつずつ確定する作戦の前提として、 辺の重みは正の値である。

10 全頂点間の問題 （２７０ページ） 単一の出発点のアルゴリズムを、全頂点に 順に適用する方法がひとつ。
重み行列が与えられるとき、Ｆｌｏｙｄの アルゴリズムを使って全頂点間の距離を 求める方法もがある。

11 頂点ｋを経由して、頂点ｉから頂点ｊに至る道があれば、 距離をあらわす行列にその距離を計算し格納する。
public class Floyd { public static <E> void search(int[][] weights, int[][] distances){ for(int i = 0; i < weights.length; i++){ distances[i] = weights[i].clone(); } for(int k = 0; k < weights.length; k++){ if(distances[i][k] == Integer.MAX_VALUE){ continue; // 未接続 or 未計算 for(int j = 0; j < weights[i].length; j++){ if(distances[k][j] == Integer.MAX_VALUE){ int w = distances[i][k] + distances[k][j]; if(w < distances[i][j]){ distances[i][j] = w; 頂点ｋを経由して、頂点ｉから頂点ｊに至る道があれば、 距離をあらわす行列にその距離を計算し格納する。 ２７０ページのプログラム　Ｆｌｏｙｄのアルゴリズム

12 public static void main(String[] args) {
System.out.println("図4.5.1"); int[][] weights = new int[6][6]; for(int i = 0; i < weights.length; i++){ for(int j = 0; j < weights[i].length; j++){ weights[i][j] = Integer.MAX_VALUE; } weights[i][i] = 0; weights[0][1] = 6; weights[0][2] = 4; weights[1][3] = 3; weights[2][4] = 3; weights[2][5] = 6; weights[4][1] = 2; weights[4][3] = 1; int[][] distances = new int[weights.length][]; search(weights, distances); System.out.println("頂点間の距離"); for(int i = 0; i < distances.length; i++){ for(int j = 0; j < distances[i].length; j++){ if(distances[i][j] == Integer.MAX_VALUE){ System.out.print("- "); } else { System.out.print(distances[i][j] + " "); System.out.println(); 図4.5.1 頂点間の距離

13 グラフの推移的閉包とは、次のような行列ａのことである。
（２７５ページ） グラフの推移的閉包とは、次のような行列ａのことである。 （頂点ｉからｊへの道が存在する場合） （頂点ｉからｊへの道が存在しない場合） Ｆｌｏｙｄのアルゴリズムとほぼ同じで、 相違点は２頂点間の距離を求めるのではなく、 単に道があるかないかだけを調べる。 そのアルゴリズムをＷａｒｓｈａｌｌのアルゴリズムと呼ぶ。

14 入力は隣接行列 出力は推移的閉包 public class Warshall {
public static <E> void search(boolean[][] adjacency, boolean[][] reachable){ for(int i = 0; i < adjacency.length; i++){ reachable[i] = adjacency[i].clone(); } for(int k = 0; k < adjacency.length; k++){ if( !reachable[i][k] ){ continue; for(int j = 0; j < adjacency[i].length; j++){ reachable[i][j] = reachable[i][j] || reachable[k][j]; 入力は隣接行列 出力は推移的閉包

15 図4.5.1 推移的閉包 + + + + + + - + - + - - - + + + + + - - - + - -
public static void main(String[] args) { System.out.println("図4.5.1"); boolean[][] adjacency = new boolean[6][6]; for(int i = 0; i < adjacency.length; i++){ for(int j = 0; j < adjacency[i].length; j++){ adjacency[i][j] = false; } adjacency[i][i] = true; adjacency[0][1] = true; adjacency[0][2] = true; adjacency[1][3] = true; adjacency[2][4] = true; adjacency[2][5] = true; adjacency[4][1] = true; adjacency[4][3] = true; boolean[][] reachable = new boolean[adjacency.length][]; search(adjacency, reachable); System.out.println("推移的閉包"); for(int i = 0; i < reachable.length; i++){ for(int j = 0; j < reachable[i].length; j++){ if(reachable[i][j]){ System.out.print("+ "); } else { System.out.print("- "); System.out.println(); 図4.5.1 推移的閉包