アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2013年7月16日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html
最短路の問題
（２６０ページ）
• 最短路問題
– グラフの２頂点間を結ぶ道のうちで辺の重みの和が
最小のものを求める問題。
• 対象は辺に重みのついた有向グラフ
• 問題は大きく２種類ある
1. 出発点を１つに固定して、そこから他のすべての頂
点への最短路を求める。
2.すべての２頂点の組み合わせに対して、最短路を
求める。
• １の方法をすべての頂点に適用するのが最善。
2
単一出発点の問題
（２６１ページ）
• Ｄｉｊｋｓｔｒａのアルゴリズム
– 各頂点への最短路を出発点に近いところから
ひとつづつ確定する。
確定した頂点から行くことのできる
頂点への距離を計算。
３
Ｂ
６
Ｄ
９
８
６
出発点
２
Ａ
１
４
Ｅ
７
３
最小の距離を持つ頂点は確定。
他から来るにしても重みが負の
経路がなければ、距離は減らない。
Ｃ
４
６
１０
Ｆ
図４.５.１アルゴリズムの動き
3
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); // 有向辺を追加
}
本日使う頂点のデータ構造
}
4
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()));
}
}
}
}
教科書２６３ページの擬似プログラムをＪａｖａで実装
}
5
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() + "からの距離");
for(WeightedNode<Character> node: test_data){
System.out.println("頂点" + node.getValue() + ": " + node.getDistance());
}
}
ひとつずつ確定する作戦の前提として、
辺の重みは正の値である。
図4.5.1
頂点Aからの距離
頂点A: 0
頂点B: 6
頂点C: 4
頂点D: 8
頂点E: 7
頂点F: 10
6
２６３ページの実装では、集合Ｕから最小の距離をもつ
頂点を線形探索し、集合Ｕから移動していた。
そもそも、線形探索は時間計算量が多い。
そこで、集合Ｕの替わりにヒープを使うことを考える。
ただし、リストのようなデータ構造でヒープを実装するのは、
データ操作に必要な時間計算量の多さから不適切である。
ヒープとしては頂点への参照を入れた配列を使うことにする。
最小の距離を持つ頂点をヒープから移動し、ヒープを再構成する。
実装は省略しますが、２６３ページの擬似プログラムが単純なので、
それを理解してみるといいだろう。それから２６７ページを理解する。
7
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);
for(int x = 0; x < nodes.length; x++){
if(weights[p][x] == Integer.MAX_VALUE){
continue;
}
nodes[x].setDistance(
Math.min(nodes[x].getDistance(),
nodes[p].getDistance() + weights[p][x]));
}
}
２６５ページのプログラムのＪａｖａ実装
}
8
}
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() + "からの距離");
for(WeightedNode<Character> node: test_data){
System.out.println("頂点" + node.getValue() + ": " + node.getDistance());
}
}
図4.5.1
頂点Aからの距離
頂点A: 0
頂点B: 6
頂点C: 4
頂点D: 8
頂点E: 7
頂点F: 10
9
全頂点間の問題
（２７０ページ）
• 単一の出発点のアルゴリズムを、全頂点に
順に適用する方法がひとつ。
• 重み行列が与えられるとき、Ｆｌｏｙｄの
アルゴリズムを使って全頂点間の距離を
求める方法もがある。
10
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++){
for(int i = 0; i < weights.length; i++){
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){
continue; // 未接続 or 未計算
}
int w = distances[i][k] + distances[k][j];
if(w < distances[i][j]){
distances[i][j] = w;
}
}
頂点ｋを経由して、頂点ｉから頂点ｊに至る道があれば、
}
距離をあらわす行列にその距離を計算し格納する。
}
}
}
２７０ページのプログラムＦｌｏｙｄのアルゴリズム
11
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
頂点間の距離
0 6 4 8 7 10
- 0 - 3 - - 5 0 4 3 6
- - - 0 - - 2 - 1 0 - - - - - 0
12
グラフの推移的閉包
（２７５ページ）
グラフの推移的閉包とは、次のような行列ａのことである。
 true （頂点ｉからｊへの道が存在する場合）
a[i, j ]  
 false （頂点ｉからｊへの道が存在しない場合）
Ｆｌｏｙｄのアルゴリズムとほぼ同じで、
相違点は２頂点間の距離を求めるのではなく、
単に道があるかないかだけを調べる。
そのアルゴリズムをＷａｒｓｈａｌｌのアルゴリズムと呼ぶ。
13
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++){
入力は隣接行列
for(int i = 0; i < adjacency.length; i++){
if( !reachable[i][k] ){
continue;
}
for(int j = 0; j < adjacency[i].length; j++){
出力は推移的閉包
reachable[i][j] = reachable[i][j] || reachable[k][j];
}
}
}
}
}
14
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
推移的閉包
+ + + + + +
- + - + - - + + + + +
- - - + - - + - + + - - - - - +
15

Download Report