第 16 回最短経路問題、まとめ

本日の内容

16-1. 最短経路問題
16-2. まとめ

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

16-1. 最短経路問題

鉄道や道路の所要時間がわかっている時、ある都市から別の都市への最短の経路を求める問題を考えましょう。これはカーナビゲーションシステムや鉄道の乗り換え案内などに応用できる問題です。例えば次のような状況を考えましょう。東京電機大学東京千住キャンパスから新宿に行くのに複数の経路が考えられます。ここでは次の経路を考えてみましょう。

常磐線を使う場合: 日暮里で山手線に乗り換えます。上野品川ライン直通であれば、東京駅から中央線を使う手もありますが、省略します。
千代田線を使う場合: 西日暮里で山手線に乗り換えるか、新御茶ノ水で中央線か都営新宿線に乗り換えるか、明治神宮前で山手線に乗り換える方法があります
日比谷線を使う場合: 上野で山手線に乗り換えるか、秋葉原で中央線各駅に乗り換えるか、銀座で丸ノ内線に乗り換える方法があります。
筑波エキスプレスを使う場合: 新御徒町で大江戸線に乗り換えるか、秋葉原で中央線各駅に乗り換える方法があります。新御徒町からは大江戸線で、新宿西口に出て徒歩で新宿に行く方法と、逆まわりで森下から都営新宿線に行く方法があります。
京成線は省略します

これらの関係を行列で表すことを考えます。行と列をそれぞれの地点に対応させ、各成分にはおおよその所要時間を入れます。また直接行けない地点間は∞（無限大）で表します。但し、C言語で直接は∞無限大を扱えませんので、十分に大きな数を使います。ここでは、H に大きな値を define しておいて使うことにします。また、路線図などからこの行列を作ることもそこそこ複雑なので、各路線の停車駅と駅間の所要時間から、この行列を求めることを考えます。

入力はつぎのように配列の塊で与えます。乗り換えの移動や待ち時間は考慮してませんし、駅間の時間は多少実際と異なっているかも知れません。

kitasenhu.h


#define NUM 16
char *eki[NUM]={"電機大","北千住","西日暮里","日暮里",
"上野","新御徒町","秋葉原",
"お茶の水","新御茶ノ水","小川町","森下","銀座","原宿",
"明治神宮前","新宿西口","新宿"
};
int length[NUM][NUM]={
{0,3,H,H,H,H,H,H,H,H,H,H,H,H,H,H},//電機大
{3,0,6,8,9,8,H,H,H,H,H,H,H,H,H,H},//北千住
{H,6,0,2,H,H,H,H,8,H,H,H,H,H,H,H},//西日暮里
{H,8,2,0,4,H,H,H,H,H,H,H,H,H,H,H},//日暮里
{H,9,H,4,0,H,H,H,H,H,H,13,H,H,H,H},//上野
{H,8,H,H,H,0,2,H,H,H,6,H,H,H,19,H},//新御徒町
{H,H,H,H,4,2,0,2,H,H,H,13,30,H,H,H},//秋葉原
{H,H,H,H,H,H,2,0,5,5,H,H,H,H,H,16},//お茶の水
{H,H,8,H,H,H,H,5,0,5,H,H,H,17,H,H},//新御茶ノ水
{H,H,H,H,H,H,H,5,5,0,6,H,H,H,H,17},//小川町
{H,H,H,H,H,6,H,H,H,5,0,H,H,H,H,H},//森下
{H,H,H,H,H,H,13,H,H,H,H,0,H,H,H,17},//銀座
{H,H,H,H,H,H,H,H,H,H,H,H,0,5,H,4},//原宿
{H,H,H,H,H,H,H,H,17,H,H,H,5,0,H,H},//明治神宮前
{H,H,H,H,H,18,H,H,H,H,H,H,H,H,0,5}//新宿西口
{H,H,16,H,H,H,H,16,H,11,H,17,4,H,5,0}//新宿
};

なお、簡単のために直接行けても H で表しているところもあります。一方、実際の運用では乗換え時間は重要ですが、簡単のためにお茶の水周辺以外は無視します。

	電機大	北千住	西日暮里	日暮里	上野	新御徒町	秋葉原	お茶の水	新御茶ノ水	小川町	森下	銀座	原宿	明治神宮前	新宿西口	新宿
電機大	-	3	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
北千住	3	-	6	8	9	8	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
西日暮里	∞	6	-	2	∞	∞	∞	∞	8	∞	∞	∞	∞	∞	∞	16
日暮里	∞	8	2	-	4	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
上野	∞	9	∞	4	-	∞	4	∞	∞	∞	∞	∞	∞	∞	∞	∞
新御徒町	∞	8	∞	∞	∞	-	2	∞	∞	∞	∞	∞	∞	∞	18	∞
秋葉原	∞	∞	∞	∞	4	2	-	2	∞	∞	∞	13	30	∞	∞	∞
お茶の水	∞	∞	∞	∞	∞	∞	2	-	5	5	∞	∞	∞	∞	∞	16
新御茶ノ水	∞	∞	8	∞	∞	∞	∞	5	-	5	∞	∞	∞	17	∞	∞
小川町	∞	∞	∞	∞	∞	∞	∞	5	5	-	6	∞	∞	∞	∞	17
森下	∞	∞	∞	∞	∞	6	∞	∞	∞	6	-	∞	∞	∞	∞	∞
銀座	∞	∞	∞	∞	∞	∞	13	∞	∞	∞	∞	-	∞	∞	∞	17
原宿	∞	∞	∞	∞	∞	∞	30	∞	∞	∞	∞	∞	-	5	∞	4
明治神宮前	∞	∞	∞	∞	∞	∞	∞	∞	17	∞	∞	∞	5	-	∞	∞
新宿西口	∞	∞	∞	∞	∞	18	∞	∞	∞	∞	∞	∞	∞	∞	-	5
新宿	∞	∞	16	∞	∞	∞	∞	16	∞	17	∞	17	4	∞	5	-

このような状況でどの経路が最短かを計算させるプログラムを作りましょう。ここで紹介する方法はダイクストラ法と呼ばれるものです。この方法では電機大からすべての駅への所要時間が求まります。

ダイクストラ法のアイディアは次のようなものです。駅の集合のうち、最短経路が求まっているような部分集合を考えます。この部分集合に含まれる駅は、将来この部分集合の要素が増えても経路が更新されたりしません。この前提で、部分集合に入っていない駅のうち一番近い駅を新たに部分集合の駅として加えます。

さて、このアイディアにおいて、出発地点は最初から部分集合に入っているものとします。また、部分集合に入っていない駅までの距離の計算は、出発駅からの距離で、部分集合からたどり着ける頂点の距離を計算します。なお、ここで、距離のもつ重要な性質の三角不等式の性質を次の様に利用します。

アルゴリズムの初期状態では、出発駅のみを最短経路の求まっている部分集合の要素とします。この時の出発点以外の駅のうち最短な駅については、その後に他の経由地を追加しても最短なままです。なぜなら、もし、その経由地を通過したときに最短で無くなるのであれば、その経由地の方が近いことになるから、もともと最短であるという仮定と矛盾するからです。したがって、最初のステップでは、出発駅から直接行ける最も近い駅を部分集合に加えれば良いです。
アルゴリズムの途中では、一駅追加する毎に出発点からの距離の再計算をする必要がありますが、この場合、追加した駅から直接行ける駅への距離だけを考えれば良いです。これは、追加した駅から行ける、部分集合に属していない最短の駅が次のステップで部分集合に追加される場合を考えると、その後で別経由で別の近い駅が見つかることを仮定すると、出発地点の時と同じ論理で矛盾します。

したがって、ダイクストラのアルゴリズムをまとめると、次のようになります。

出発点から各駅までの距離のベクトルを出発地点のみ0、他の駅までの距離を∞とする
部分集合に入っていない駅が無くなるまで以下を繰り返す
1. 距離ベクトルのうちの最短の駅を取り出す
2. 部分集合に取り出した駅を入れる
3. 部分集合に含まれていない各駅に対して
  1. 取り出した駅を経由した経路の距離を計算し、
  2. 近くなるのであれば、距離を更新する

これをC言語で実現するため、次の様にします。

集合を表現するのに、各駅に対する flag 変数が 0 であるものを要素とし、 j 番目の駅が集合に入っていないことを判断するのに if(flag[j]) で判断できるようにした
無限大は扱えないので、全ての距離の合計よりも十分大きな値として 9999 を define により H に関連付け使用する

作成したプログラムは以下のようになります。

ダイクストラ法による最短経路のプログラム


#include <stdio.h>
#define H 9999
#include "kitasenju.h"
int dist[NUM],flag[NUM],path[NUM];
void initArray(){
  int i;
  for(i=0;i<NUM;i++){
    dist[i]=H;
    flag[i]=1;
  }
}
int argmin(void){
  int index=-1;
  int j;
  int min=H;
  for(j=0;j<NUM;j++){
    if(flag[j] && dist[j]<min){
      index=j;
      min=dist[j];
    }
  }
  return index;
}
void recalc(int index){
  int j;
  for(j=0;j<NUM;j++){
    if((dist[index]+length[index][j])<dist[j]){
      dist[j]=dist[index]+length[index][j];
      path[j]=index;
    }
  }
}
void printEki(void){
  int j;
  int index;
  for(j=0;j<NUM;j++){
    printf("%s %d: ",eki[j],dist[j]);
    index=j;
    do{
      printf("-%d- %s ",length[index][path[index]],eki[path[index]]);
      index=path[index];
    }while(index!=0);
    printf("\n");
  }
}
int main(void){
  int i;
  int index;
  initArray();
  dist[0]=0;
  for(i=0;i<NUM;i++){
    index = argmin();
    if(index <0) {
      fprintf(stderr,"The graph is disconnected.\n");
      return -1;
    }
    flag[index]=0;
    recalc(index);
  }
  printEki();
  return 0;
}

ここで、 path[] 変数には、電機大から来る場合に直前に経由した駅を入れています。そうすると、最短路が見つかった場合、目的地から順に電機大まで最短経路をたどることができます。

演習16-1

上のプログラムを動かし、電機大から新宿までの最短経路を求め、どの路線をどのように乗り換えれば良いか説明しなさい。
指定した駅(例えば駅の番号を入れるなど)までの経路だけ表示するように改造しなさい。
乗換時間を考慮するにはどうすれば良いか考えなさい。

付録1

旧電機大から渋谷までの経路を求めるためのヘッダファイルを示します

kanda.h


#define NUM 10
char *eki[NUM]={"電機大","新お茶の水","大手町","神保町","お茶の水",
		"神田","表参道","代々木","原宿","渋谷"};
int length[NUM][NUM]={{0,5,13,15,10,10,H,H,H,H},
		      {5,0,3,H,H,H,H,H,H,H},
		      {13,3,0,3,H,H,12,H,H,H},
		      {15,H,3,0,H,H,11,H,H,H},
		      {10,H,H,H,0,3,H,13,H,H},
		      {10,H,H,H,3,0,H,H,H,25},
		      {H,H,12,11,H,H,0,H,3,3},
		      {H,H,H,H,13,H,H,0,3,H},
		      {H,H,H,H,H,H,3,3,0,2},
		      {H,H,H,H,H,25,3,H,2,0}
};

付録2

経路配列のヘッダファイルをチェックするプログラムを示します。


#include <stdio.h>
#define H 9999
#include "kitasenju.h"
int main(void){
  int i,j;
  for(i=0;i<NUM; i++){
    for(j=0; j<NUM; j++){
      if(length[i][j]!=length[j][i]){
	printf("%s -%d-> %s, but %s -%d-> %s\n",
	       eki[i],length[i][j],eki[j],
	       eki[j],length[j][i],eki[i]);
      }
    }
  }
  return 0;
}

16-2. まとめ

この講義の主な目的は、情報処理の基礎であるデータの数え上げや整列を制限なく行えるようになることと、汎用のプログラミングテクニックとしての状態遷移図の取り扱いです。そのために、以下のことを学びました。

線形リスト

大量のデータを扱うには、あらかじめ容量を決めなければいけない配列は使えません。そこで使用したのが線形リストというデータ構造です。これはメモリをあらかじめ確保するのではなく、必要に応じて必要な量だけメモリを取得し、データを順に格納するものです。

C 言語で実現するには次のような、データとポインタを格納するような構造体を作り、 malloc 関数でメモリ上に生成してはひとつひとつつなげて使いました。


struct node {
   int data;
   struct node *next;
};

線形リストは大量のデータを取り扱う仕組みのうち、もっとも簡単な構造をしてます。従って、検索などはデータ量に比例した時間かかります。一方で、データの追加や削除は容易にできます。

なお、C++ では STL(Standard Template Library)に deque や list というテンプレートが存在し、また、 Java では java.util.ArrayList が存在します。どちらも C 言語のようにポインタの操作やメモリの操作無しに、頂点を付け加えたり削除したりできます。

順序木

数の決まっているものを順序に従って整列させるには、配列のソートを行います。しかし、数の決まってないものを整列させるには、順序木を使います。順序木は、二分木において、頂点のデータが左の子よりも大きく、右の子より小さいものを言います。このような木に対して、データを格納する場合、根の頂点から順にデータを比較していくとデータを格納すべき場所を捜し出すことができます。一方、木の左から順にデータを取り出すことで、いつでも整列した状態でデータを取り出すことができます。 C 言語ではこの順序木を使うのに、自らの構造を指すことができるポインタを二つ持つ構造体を使用しました。


struct node {
   int data;
   struct node *left,*right;
};

なお、値の整列は情報処理の基礎であり、多くのプログラミング言語で簡単に利用できるようになっています(但し、内部では順序木を利用している)。 C++ では STL にある map や multimap で利用できます。また、Java 言語では java.util.TreeMap を使います。しかし、大量のデータの入出力が発生する場合、効率良くデータをやりとりするために、外部データベースの利用を考えた方が良い場合があります。

再帰

プログラム開発において、与えられた問題を分解し、元の問題と同じ構造を発見できれば、再帰という手法を用いてプログラムを書くことができます。

例えば、与えられたデータを整列する場合、整列された列はどの部分列を見ても整列されています。よってデータ列を半分にすれば、大きい列と小さい列に分割できます。従って、データ列を大きいものと小さいものとに半分に分割するような関数を設計し、半分になった列それぞれに対して、同様な処理を繰り返すようにすると最終的にデータを整列できます(Quick Sort)。

このように、データの列に何らかの規則がありデータを分割しても成り立つ場合、関数の中でデータを分割しながら同じ関数を呼び出すようにすると、シンプルなプログラムで複雑なデータを取り扱うことができます。再帰は、このほか線形リストや順序木の処理などにも活用できます。

状態遷移図

プログラム開発において、状態の解析は重要です。状態遷移図を書くことで、状態の移り変わりに応じたプログラムの作成が容易になります。

一般のフローチャートと似ていますが内容は大きく異なります。フローチャートでは一つの図形がプログラム一行を表すことがあり、また、入出力の仕様や、変数の値、関数呼び出しなど、プログラムを作成する上で必要な情報のほとんど全て(さすがにファイルレイアウトまでは記入できませんが)を詰め込めます。これはある意味一つのプログラム言語となっていて、別のプログラム言語で記述するための共通言語としての役割を担うことになります。但し、フローチャートはプログラミングスタイルを強要することができないので、読み易く保守し易くプログラムを開発すると言う近年のプログラム開発からは使いづらいツールになっています。

一方、状態遷移図に記入できるのは入力と状態と状態の移り変わり、それに加えて出力や開始、終了状態だけです。このような限定条件のもとで図を書くことにより、一つの状態は必ずしもプログラム一行に対応するわけではなく、プログラム内のまとまった一ブロックを指すようになります。

まとめの演習

入力したファイルの文字を全て逆順に出力するプログラムを作りなさい。
フィボナッチ数列 a_n は次のようにして定義される数列です。 a₀=1, a₁=1, a_n=a_n-1+a_n-2 。実際の列は 1, 1, 2, 3, 5, 8, 13, 21, ... となります。そこで、 a₂₀ を求めなさい。
入力されたファイルの中で一番長い単語を出力するプログラムを作りなさい(各単語は空白、または改行で区切られているとします)。

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 16 回 最短経路問題、まとめ