場合の数（最短経路問題）

場合の数（最短経路問題）

最短経路問題をプログラムに解かせてみる。

数学の問題としては以下のような直線でできた経路で
SからGに行く最短経路は何通りあるかという問題。

場合の数の数え上げの方法を使うと以下のように数え上げていくことになる。

Aへ行く道順は　S->A　の１通り
Bへ行く道順はS ->Bへは1通り
Cに行く道順は、A->C、B->Cとあり、Aに行く道順+Bに行く道順　で求めることができる

数学（算数）の解法は「最短経路問題（道順の場合の数）」をご参照下さい。

この解法をBASICプログラムで書いたものが以下。
経路を書いたテキストファイルを読み込んで解析する形になっている。
40～120行が経路を書いたテキストファイルの読み込み
130～210行は解析
220行以降で、結果の出力。

入力するファイルは初期値が0, -1で道を表現している。
0 道がないか、水たまり等で通行できない個所
-1　通行可能な個所

pass(i,j)に各交点までの経路の数を保持
150行　スタート地点のS、すなわちpass(0,0)の時はpass(0,0)=1とする。
160行　pass(i,j)>-1　の時は通行可能でないので200行へ飛ぶ
170行 i=0　つまり右端の道にいる場合の処理。例えばS->Bへはpass(0,0)からの進路数のみ加算
180行　j=0　すなわち上端の道にいる時の処理。例えばS->Aへはpass(0,0)からの進路数のみ加算
190行　それ以外の場所にいるときの処理

10 cls
20 close
30 dim pass(20,20)
40 input "file";f$
50 open f$ for INPUT AS #1
60 input #1,w
70 input #1, h
80 for j=0 to h-1
90 for i=0 to w-1
100 input #1,pass(i,j)
110 next i
120 next j
130 for j=0 to h-1
140 for i=0 to w-1
150 if i=0 and j=0 then pass(i,j)=1: goto 200
160 if pass(i,j)>-1 then goto 200
170 if i=0 then pass(i,j)=pass(i,j-1)
180 if j=0 then pass(i,j)=pass(i-1,j)
190 if i>0 and j>0 then pass(i,j)=pass(i-1,j)+pass(i,j-1)
200 next i
210 next j
220 for j=0 to h-1
230 for i=0 to w-1
240 print pass(i,j);",";
250 next i
255 print
260 next j
270 close #1
280 end

では、具体的な問題として少し応用の必要な問題を解かせてみます。
水色のところは水たまりで通れません。

この経路をデータにしたのが以下のファイルです。
pass4.txt

4
4
-1,-1,-1,0
-1,0,-1,-1
-1,-1,-1,-1
0,0,-1,-1

実行させると、Gの地点が5となっており、
5通りの経路があることがわかります。