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

本日の内容

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

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

16-1. 最短経路問題

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

千代田線を使う場合

新お茶の水駅、大手町のどちらかから乗ることができま す。そして、直接渋谷には行かず、表参道で半蔵門線か銀座線に乗り換えるか、原宿(明治神宮前) で山手線に乗り換えるかしなければなりません。

半蔵門線を使う場合

大手町か神保町で乗ることができます。そして、表参道を通過して、直接 渋谷に行くことができます。

山手線を使う場合

神田に出れば直接渋谷に行けます。一方、お茶の水から中央線で代々木や 新宿に出れば原宿経由で渋谷に着けます。

これらの関係を行列で表すことを考えます。 行と列をそれぞれの地点に対応させ、各成分にはおおよその所要時間を入れま す。また直接行けない地点関は∞で表します。 簡単のために直接行けても∞で表しているところもあります。 一方、乗換え時間は重要ですが、簡単のためにここでは無視します。

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

1. 各駅までの距離を最大値に、確定フラグをクリアしておきます。
2. 電機大は距離 0 とします。
3. 以下をすべての駅が確定するまで繰り返します。
   1. 確定していない駅のうち、もっとも電機大と近い駅を選びます。
   2. その駅までの距離を確定するため確定フラグをセットします。
   3. その駅から隣の駅までの時間を計算し、その駅を経由した方が電機大に近 ければ距離を計算しなおします。
4. 結果を表示します。

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

main(){
  int i,j;
  int index,min;
  for(i=0;i<NUM;i++){
    dist[i]=HI_VALUE; flag[i]=1;
  }
  dist[0]=0;path[0]=0;index=0;
  for(i=0;i<NUM;i++){
    min=HI_VALUE;
    for(j=0;j<NUM;j++){
      if(flag[j] && dist[j]<min){
	index=j; min=dist[j];
      }
    }
    flag[index]=0;
    if(min==HI_VALUE){
      fprintf(stderr,"The graph is disconnected.\n");
      return;
    }
    for(j=0;j<NUM;j++){
      if((dist[index]+length[index][j])<dist[j]){
	dist[j]=dist[index]+length[index][j];
	path[j]=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");
  }
}

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

演習16-1

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

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)。

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

状態遷移図

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

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

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

まとめの演習

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