最短経路問題

最短経路問題 (ダイクストラ法とA*アルゴリズム)

趣旨

講義資料

今回のトピックは主に２つです。

優先度キューを使ってみる（復習）
- ヒープソートなどで利用されるヒープデータ構造
最短経路を求めるアルゴリズムについて学ぶ（新ネタ）
- ダイクストラ法（必須）や A* アルゴリズム（オプション）の理解

で、課題を解いてもらいます。

基本データ構造

優先度キューは、Queue （待ち行列）の一種ですが、指定した優先度順に要素を取り出すことができるものです。

要素を全部詰めてからソートして順番に取り出す「わけではなく」、随時、要素を加えたり、取り出したりすることができます。便利です。

とりあえず、優先度キューを使うだけのプログラム例を配置しましたので、利用イメージを理解しましょう。前半がライブラリ部で、後半の main()が利用部です。

このプログラムでソートしているのは、struct myitem というデータ構造です。

typedef struct myitem {
  double priority; /* 優先度、低いほうが優先ってことにします */
  int id;          /* 要素識別用の番号 */
} myitem_t, *myitem_tp;

利用しているのは、とりあえずこの関数群。

ELEM dequeue(): 要素を取り出す
void enqueue(ELEM a): 要素を加える
int compare(ELEM * a, ELEM * b) は、a, b の並び順（大小）を比較する関数です。利用者に定義してもらうつもり。

以下が、利用コードです。

priorityQ_t Q;

int main(void) {
  int i;
  myitem_t items[] = {
    { 100.0, 0 }, /* priority, id */
    {  10.0, 1 },
    {  20.0, 2 },
    {  10.0, 3 },
    { 100.0, 4 },
    {   5.5, 5 },
    {   3.0, 6 },
    {  30.0, 7 }
  };
  for(i=0; i<4; i++) {
    enqueue(&Q, items[i]);
  }
  printQueueInside(&Q);
  for(i=4; i<8; i++) {
    myitem_t r = dequeue(&Q);
    printf("dequeue (2nd stage):"); printItem(&r);printf("\n");
    enqueue(&Q, items[i]);
  }
  while(qSize(&Q)>0) {
    myitem_t r = dequeue(&Q);
    printf("dequeue (3rd stage):"); printItem(&r);printf("\n");
  }
  printf("finish!");
  return 0;
}

Queue 内部実装

内部実装は、ヒープソートで利用するヒープを利用しています。

基本木構造データ構造です。小さい順にソートしている場合、

親は子供のいずれよりも小さい

というルールが守られます。そのうえで、enqueue, dequeue に際して

enqueue: 最後尾に要素を加える。そのうえで、以下の upheap をおこなう。
- 追加要素が、その親より小さい場合は、交換する。
- このような親との比較を、親が追加要素以下になるまで繰り返す。
dequeue: 先頭要素を返す。そのうえで、最後尾要素を、先頭に移動させ、以下のdownheap をおこなう。
- 移動要素が、子供のいずれかより大きい場合、小さいほうの子供と入れ替える。
- このような親との比較を、子供が追加要素以上になるまで繰り返す。

このあたりは、アルゴリズムの授業ですでに習っているはず。

プログラムは、こちらの43-132行目あたりです。興味がある人は読んでみてください。

比較方法

前回のキューと違い、優先度キューでは、比較用関数を利用者が定義する必要があります。というのも、提供しているライブラリは、汎用を目指しているので、要素型は、なにが来ても大丈夫にしたいのですが、だからこそ比較の仕方は 前もって決めておけない わけです。

int compare(ELEM *a, ELEM *b)
- *a, *b の比較結果を返す
- *a, *b の順に並べるべき時は、負の数を返す
- *b, *a の順に並べるべき時は、正の数を返す
- 同じ大きさの場合は、0を返す

例： int を小さい順に並べる場合

int compare(int *a, int *b) {
    if(*a < *b) return -1;
    if(*a > *b) return 1;
    return 0;
    /* 桁あふれが無視できるなら、 return *a-*b; でも OK */
}

qsort の紹介

皆さん、ソートのアルゴリズムを習ってきたかと思いますが、ソートは重要なので、C 言語でも標準ライブラリとしても提供されています。

void qsort(void * base, size_t num, size_t size,
           int (*compar)(const void*, const void*));

base: 配列の先頭アドレス
num: 要素数
size: 要素ひとつあたりのサイズ(byte数, sizeof)
compar: 比較用関数へのポインタ。まあ、関数名だとおもってもらっても OK. アドレス二つを引数に取り、int を返す関数を渡す。

利用例

/* 比較用関数。a, b アドレスにある座標データを比較する。
   x 座標が小さいものが前で、x座標が同じ場合は、y座標で比較 */
int compare0(const void * a, const void * b) {
    /* ポインタ型を、本来の point_tp に変換しよう */
    point_tp ap = (point_tp)a;
    point_tp bp = (point_tp)b;
    int result = ap->x - bp->x;
    if(result==0) return ap->y-bp->y;
    return result;
}
void qtest() {
    int i;
    /* ポイントをソートしよう */
    point_t ps[] = {{1,3}, {12,4}, {5,2}, {7, 8}};
    /* qsort 呼出し */
    qsort(&ps, 4, sizeof(point_t), compare0);
    /* 表示してみる */
    for(i=0; i<4; i++) {
        printf("(%d %d), ", ps[i].x, ps[i].y);
    }
    printf("\n");
}

比較器を定義して、ライブラリに引数として渡しています。

実は、皆さん今まで、ライブラリを呼ぶことはあっても、ライブラリに呼ばれる経験はあまりなかったんじゃないかとおもいます。

今後、ライブラリを駆使したり、他の人と共同プログラミングをおこない始めると、このように規格にあわせてプログラミングをおこなう機会も増えます。また、C++, Java といった、より先進的で、ライブラリの充実した言語をつかう場合も同様です。覚えておいてください。

最短経路探索

問題例

アルゴリズムの紹介の前に、問題設定をしましょう。

問題：
盤面に点が配置されています。
始点から終点まで移動したいのですが、２点間の距離が 10以下の場合だけ移動することができます。
以降で紹介する２種類のアルゴリズムを用いて、最短経路問題を解いてみましょう。

例えば、図0 の例では、始点(0,0) から(6,8) を経由して (12,0) にたどり着くことができ、これが移動経路長を最小にする移動法になります。

もうすこし経路が長いケース。

配置によっては、終点に到達できないケースも存在します。

あるいは、意外と遠回ししなくてはいけないケースも存在します。

さて、これから紹介する２種類のアルゴリズムを用いて、最短経路問題を解いてみましょう。

ダイクストラ法

グラフの探索の場合、探索順序に注意しないと、何度も同じ場所をやり直す羽目になります。計算量も膨大になってしまいます。

幅優先探索は、始点に近いノードから順番に探索をかけていくのですが、もし、枝(edge)に長さがある場合は、幅優先探索では「近い」ノードから探索したことにはなりません。ある点にいくのに複数の経路がある場合、後からしらべた経路の方が安上がりだったりするかもしれませんし、その場合、やり直しの可能性だって出てきます。

ダイクストラ法は、始点ノードから「近い」ノードから順番に、その到達コストを確定させていく方法です。

始点ノードへの経路長を 0, 他のノードへの経路長を無限大とする。
未探索ノードのうち経路長が最小のものを取り出す（nとする）。この時点で n への経路長は確定できる。n の隣接ノードに対し、n 経由で到達する経路長を求め、以前に求めた経路長より短くなる場合は更新する。
未探索ノードがなくなるまで、2 を繰り返す。

int solve() {
   enqueue(queue, start);
   while(qSize(queue) > 0) {
      node_t here = dequeue(queue); /* 最小ノードが選択できればね */
      if(/* ゴール? */) return 答え;
      for(/*here から未訪問の隣接ノード*/) {
          経路長を更新;
      新しい経路候補なら、enqueue;
      }
   }
}

queue として優先度キューを使い、経路長最小のものから取り出すことができれば、アルゴリズムは完成です。

このプログラムでは、ゴールに到達した時点で計算を打ち切っていますが、最後までやれば、始点 からすべての点への最短経路も求まります。

注意: このアルゴリズムは、枝のコストに負の値が含まれる 場合は機能しません。一時的に「遠く」なっても、あとで「相殺」できるってことだと、「近いところから」確定できません。別の言い方をすると、「（中間）解をみつけた」つもりでいても、後から「もっといい（中間）解」がみつかったら、やり直しになります。

プログラム実装

プログラムはdijkstra.cです。前半は優先度キュー部分で、後半にダイクストラ法を実装したdouble solve(int n)関数があります。

注: 今回のプログラムはsqrt()を利用しているので、コンパイル時に -lm option を渡す必要があります。VS code を使っている人は、tasks.jsonのコンパイルオプション設定部に -lm を追加してください。こんな感じ(例)。

{  ...
    "tasks": [
        {
            "args": [
                "-g",
                "${file}",
                "-lm",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}"
            ],
        ...
        }
    ]
}

今回、探索ノードとしてstruct searchNodeというデータ構造を準備しました。

typedef struct searchNode {
    double pathLen; /* 対象ノードまでの経路長 */
    int index;        /* 対象ノード */
} searchNode_t, * searchNode_tp;

入力された点の情報は、点の個数をint n に、点データを points[] に格納しています。
double cost[] は、始点から各点までの最短経路長を記憶しておくための配列です。好きにつかってください。
double solve(int n) がプログラム本体です。
- 始点から終点までたどり着ける場合は、その最短経路長を結果として返しましょう
- たどり着けない場合は、0.0 を返してください。

A* アルゴリズム

ダイクストラ法では、始点から波紋状に探索が進んでいきますが、ゴールが分かっているなら、「そちらの方向」に探索を優先的に進めたいものです。

各点から、ゴール地点への「見積もり値」を準備できる場合、「その地点までの最短経路」＋「その地点からゴールへの見積もり値」が小さい順に処理すれば、「ゴールの方向」に優先して探索をすすめることができます。

こういったアルゴリズムを A* (A-star) アルゴリズムと呼びます。プログラム的には、ダイクストラ法とあまり変化はなく、優先度をどう与えるかの部分だけが変わってきます。

「見積もり値」については、「実際の最短経路より短い」ような、楽観的な見積もり値を使うのがおすすめです。ダイクストラの良さをキープしながら、ゴールに近いところから積極的に探索してくれます。

ちなみに、「見積もり値」をすべて 0 にすると、ダイクストラ法とまったく同じことになります。

一方で、特定のノードに極端に悪い見積もり値をつけると、そのノード抜きでグラフ探索してから、そのノードありのグラフ探索をやり直すような形になってしまいます。

A* のプログラムはこちら。

実は、ダイクストラとプログラム上の差はわずかです。開発環境上でプログラム比較してみるとよいでしょう。

入力データ例

今回のプログラムの入力データも、ファイルsample.in から与えています。フォーマットは以下のような形。（// の右側は、入力データに対するコメントで、本来はありません。）興味がある人は見てみてください。入力の終わりは、0 だけを含む行によって指示されています。

5 // 点の数（始点と終点を含む）
0 0 // 始点の x座標と y座標
6 8 // ２番めの点の x座標と y座標
-2 -2 // ３番めの点の x座標と y座標
11 0 // ４番めの点の x座標と y座標
12 0 // 終点の x座標と y座標

この入力データと、対応する最短経路を図示したのが、最初の図です。

動的計画法連絡先

ページ一覧

ページ内