まえがき

プログラミングの練習として、 碁盤目状に道路が引かれた街の、 ある交差点から別の交差点までの最短経路の数を求めてみます。 いくつか実装例を考えたので、 同じようなことをしている誰かの参考になれば幸いです。 使用するプログラミング言語はC言語です。

やりたいこと

京都や札幌のような、 碁盤目状に道路が引かれた街を考えます。

具体的には、 東西と南北の2方向に道路が並行して走っており、 交差点で道路は直交します。 また、 碁盤目のマスの幅はどこを見ても等しいものとします。

入力

以下の2つの整数が与えられます。 どちらの値も碁番目のマスの幅を1とします。 また、 必ず0以上の値をとります。

• 2つの交差点間の東西方向の距離
• 2つの交差点間の南北方向の距離

出力

与えられた入力から次の1つの整数を出力します。

• 2つの交差点間の最短経路数

例

図中の交差点Aと交差点Bの間の最短経路数を考えます。

  |  |  |  |  |
--+--A--+--+--+--
  |  |  |  |  |
--+--+--+--B--+--
  |  |  |  |  |    ↑北

入力は次の2つの整数です。

• AB間の東西方向の距離：2
• AB間の南北方向の距離：1

出力は次の1つの整数になります。

• AB間の最短経路数：3

組み合わせによる実装例

実装例では、 変数名・仮引数名を次のように命名しています。

• h ：2つの交差点間の東西方向の距離
• v ：2つの交差点間の南北方向の距離
• n ：組み合わせで、 選ぶもとの集合の元の個数
• r ：組み合わせで、 選ぶ個数

このとき、 求めたい最短経路数は、 $h$ と $v$ を用いて ${}_{h+v} \mathrm{C}_v$ で表されます。

for ループによる実装

次の式で ${}_n \mathrm{C}_r$ を計算することできます。

$${}_n \mathrm{C}_r = \frac{(n-r+1)(n-r+2)(n-r+3) \cdots (n-1)n} { 1 \cdot2 \cdot3 \cdots (r-1)r}$$

これをそのまま for ループで実装したのが、 次のコードです。 分母と分子を分けて求め、 最後に分子を分母で割っています。

#include <stdio.h>

int combination(int n, int r) {
    int a = 1, b = 1;
    int i;

    for (i = 1; i <= r; i ++) {
        a *= n - r + i;
        b *= i;
    }

    return a / b;
}

int main(void) {
    int h, v;

    printf("2つの交差点間の東西方向の距離："); fflush(stdout); scanf("%d", &h);
    printf("2つの交差点間の南北方向の距離："); fflush(stdout); scanf("%d", &v);

    printf("2つの交差点間の最短経路数：%d\n", combination(h + v, v));
    
    return 0;
}

この実装は、 入力の値が少しでも大きくなると、 すぐに combination 関数内の変数 a, b が桁溢れしてしまうという問題があります。

再帰による実装

for ループによる実装の桁溢れ問題を解決するため、 ${}_n \mathrm{C}_r$ の再帰的定義に基づいて組み合わせを計算してみます。 ${}_n \mathrm{C}_r$ は次のように再帰的に定義されます。

$$\begin{split} {}_n \mathrm{C}_0 & = 1\\ {}_n \mathrm{C}_r & = {}_{n-1} \mathrm{C}_{r-1} \times \frac{n}{r} \end{split}$$

この定義を使って再帰関数で実装したのが、 次のコードです。

#include <stdio.h>

int combination(int n, int r) {
    if (r == 0) return 1;
    return combination(n - 1, r - 1) * n / r;
}

int main(void) {
    int h, v;

    printf("2つの交差点間の東西方向の距離："); fflush(stdout); scanf("%d", &h);
    printf("2つの交差点間の南北方向の距離："); fflush(stdout); scanf("%d", &v);

    printf("2つの交差点間の最短経路数：%d\n", combination(h + v, v));

    return 0;
}

for ループを使った実装では対応しきれなかった大きな入力にも対応するようになりました。 コードの見通しも良くなったのではないでしょうか。

「書き込み方式」による実装例

「書き込み方式」で最短経路数を求められる原理は、 下記ウェブページに書かれています。

• 道順の場合の数を求めるテクニック | 高校数学の美しい物語

「書き込み方式」を今回の問題に当てはめる上で重要なポイントは次の2つです。

• スタート地点から見て、 東西方向または南北方向の距離が0であれば、 その交差点にたどり着く最短経路数は1である。
• スタート地点から見て、 東西方向・南北方向の距離がどちらも0でなければ、 その交差点にたどり着く最短経路数は、 その直前に通り過ぎうる2つの交差点それぞれにたどり着く最短経路数の和である。

これをそのまま再帰関数で実装したのが、 次のコードです。

#include <stdio.h>

int route(int h, int v) {
    if (h == 0 || v == 0) return 1;
    return route(h - 1, v) + route(h, v - 1);
}

int main(void) {
    int h, v;

    printf("2つの交差点間の東西方向の距離："); fflush(stdout); scanf("%d", &h);
    printf("2つの交差点間の南北方向の距離："); fflush(stdout); scanf("%d", &v);

    printf("2つの交差点間の最短経路数：%d\n", route(h, v));

    return 0;
}

個人的には、 この実装が一番直感的で分かりやすいと思います。 ただ、 効率は悪いです。

あとがき

いろいろな方法で碁盤目状の道路の最短経路数を求めてみました。 再帰を使うと、 簡単に問題を解決できたので、 再帰は便利だなと思いました。