2015/01/01

道順の場合の数を求めるテクニック

分野: 場合の数  レベル: 入試対策

定期試験や入試で頻出の「道順の場合の数を求める問題(最短経路問題)」について。有名なテクニックである書き込み方式について解説します。漸化式を使って場合の数を求める,動的計画法の入り口。

問題と模範解答

まずは最短経路問題の最も基本的なタイプです。

道順の場合の数

例題

図のような格子状の道路がある。点 $A$ から点 $B$ まで行くときの最短経路の数を求めよ。

まずは教科書的に解きます。→と↑の列を考えることになります。

解答

「→四つと↑三つを一列に並べたもの」と「最短経路」は一対一に対応する。
よって「→四つと↑三つを一列に並べたもの」の数を数えればよい。そのような場合の数は同じものを含む順列の公式より
$\dfrac{7!}{4!3!}=35$ 通りである。

書き込み方式

道順の場合の数を求める別解を解説します。「書き込み方式」などと呼ばれるものです。

点 $A$ から頂点 $P$ にたどりつくための最短の道順の数を $N(P)$ と書きます。目標は $N(B)$ を求めることです。

書き込み方式

書き込み方式では $A$ の近くの頂点から順々に,各頂点 $P$ に $N(P)$ を書いていきます。

具体的には $N(P)$ は,$P$ の左の頂点を通る最短経路の数と,$P$ の下の頂点を通る最短経路の数の和です。よって,左の頂点の数字と下の頂点の数字を足したものを $P$ に書いていきます。例えば青い点に行くには赤い点か緑の点のどちらか一方のみを通るので $4+6=10$ を青い点に書きます。

ただし,一番下の行と左の列の頂点に関しては最短経路は一通りです。

(別解)
書き込み方式を用いて順々に最短経路の数を求めていく。すると,答えは $35$ 通りとなる。

書き込み方式の応用

与えられた問題設定が複雑になればなるほど書き込み方式は威力を発揮します!

書き込み方式の応用

例えば以下のような場合,矢印の列との対応を考えるのはかなり大変になりますが,書き込み方式は使えます。

  • 全体が長方形でない
  • 通ってはいけない点が指定されている(穴がある,池がある,工事中など)

図の $A$ から $B$ に行く最短の道順の場合の数は書き込み方式により10通りと分かる。

動的計画法

書き込み方式は簡単な漸化式を使って場合の数の問題を解いた,とみなすことができます。
このように「漸化式を利用して次々に途中までの解を記録していき最終的に解を求める方法」を計算機科学の専門用語で動的計画法と言います。

動的計画法の(大学入試に出そうな)他の応用としては「階段を上る場合の数」があります。

例題

1歩で1段か2段を上るとき,9段の階段を上る上り方は全部で何通りあるか。

解答

題意の方法で $n$ 段の階段を上る方法を $a_n$ 通りとする。
$a_1=1,\:a_2=2$,$a_{n+2}=a_{n+1}+a_n\:(n\geq 1)$ を使って順々に $a_n$ を求めていく。
$a_3=3,\:a_4=5,\:a_5=8,\:a_6=13,\:$ $a_7=21,\:a_8=34,\:a_9=55$
よって $55$ 通り。

ちなみに各 $a_n$ はフィボナッチ数になります。→フィボナッチ数列の一般項と数学的帰納法

動的計画法はプログラミングコンテストでは相当いろいろな問題に使えます。情報オリンピックを目指す人は必須です。
分野: 場合の数  レベル: 入試対策