(46)【基本情報技術者】最短経路の数を求める。

投稿者: | 2023年10月20日

48 views

1. 力尽くで解いてしまったが…

基本情報技術者試験 平成30年度春期試験 問2
以下のような問題だ。

マス目の数が少ないので、ついつい力尽くで解いてしまった。

でも、もし本番でマス目の数が増えたならば…
力尽くでは試験時間を浪費してしまうだろう。

そこで…
最短経路の数を計算で求められるように訓練しておきたい
と思った。

高校生の頃にやったような気がするのだが

2. やってみる

Step 1 : 区間 P to R

初めに区間 P to R の移動を考えてみる。
最短経路を通る場合、下記のように x 2回、 x 2回の合計 4回の移動の組合せになる。
→ → ↑ ↑
→ ↑ → ↑
→ ↑ ↑ →

 :等々

まずは、→ → ↑ ↑ をそれぞれ異なるものとして、愚直に樹形図を描いてみる。

力尽くで求めた結果は 24通りだ。
上図の通り、これは 4P4の順列なので、以下の式で算出できる。

実際には、2回の横移動 は区別しないので、これを同じものとして重複する組合せを削除する。

重複数が 2の場合、組合せの数が 1/2に減る。

【参考】
重複数が3の場合、組合せの数が 1/3! になる。
 ∵3個の場合の組合せは3!通りだから、この3個を区別しなければ 1/3!に減るのは当然だ。

【参考】
重複数がnの場合、組合せの数が 1/n! になる。
 ∵n個の場合の組合せはn!通りだから、このn個を区別しなければ 1/n!に減るのは当然だ。

同様に、2回の縦移動 も区別しないので、こちらについても重複する組合せを削除する。

この結果、→ → (区別せず) ↑ ↑ (区別せず)の組合せは以下の通りになった。

Step 2 : 区間 R to Q

R to Qも同様に、→ → → ↑ ↑ の5回の移動の組合せとして、以下の通りに算出できる。

Step 3 : 全区間

上記の P to R, R to Qを直列に繋ぐと、組合せの数は以下の通り。

3. 所感

・盲目に公式を覚えるよりも、理屈で覚えてしまった方がスッキリする。
・少し復習すれば思い出せそうなので、今後も公式の暗記に頼らずに理論を確認しながら学習しよう。


コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です


日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)