こんにちは。horyです。
「組み合わせ」の問題で「最短経路」についての問題があります。
今回はこの「最短経路」の問題について簡単にまとめました。
必要なら、「順列・組合わせ_押さえるべきポイント」の記事・「同じモノを含む順列の攻略」の記事を読んでおいてください。
最短経路の問題
最短経路の問題とは以下のような問題です。
下図のような経路を考える。
地点AからBに行くための最短経路の総数を求めろ
AからBまで行くための「最短経路」とは・・・
AからBまで「最小の移動回数」で向かうにはどうすればよいかということを考えます。
右に進むことを「→」、上に進むことを「↑」と表すと、「→」×6・「↑」×6が最小の移動回数(最短距離)になります。
最短経路の数は6個の「→」と６個の「↑」の計12個を一列に並べる場合の数と置き換えても差し支えないです。
つまり、「同じものを含む順列」と置き換えても差し支えないです。
また、「同じものを含む順列」は「組み合わせ」と密接な関係があるため・・・
「12個の場所から6個の→の場所を選ぶ場合の数」と考えてもokです。
なので本問の解答は・・・
通行止めがある「最短経路」
初めに出した問題の応用で、通行止めで通れない道があるときを考えます。
以下は問題です。
下図のような経路でAからBへの最短経路を考える。
最短経路の中でCもDも通らないものの総数を求めろ
本問の解説を行います。
問題を解く前に
まず、以下のようなカテゴリーに分けて考えます。
- Cを通るもの
- Dを通るもの
- CとDの両方を通るもの
そして、ベン図を用います。以下は本問のベン図です。
上記のベン図の青い斜線部が求める部分です。
つまり、求めたい場合の数は以下の式で表せます。
問題を解くときのポイント
問題を解くとき、通行止めになっている直前の四辻にチェックポイントを置いてください。
今回私はEとFのチェックポイントを考えました。
このチェックポイントを起点にしてn(C), n(D), n(C∧D)を求めるとき、以下の図を用いて最短経路を考えます。
・n(C)について
A→E→Bとして最短経路を考えます。
・n(D)について
A→F→Bとして最短経路を考えます。
・n(C∧D)について
A→E→F→Bとして最短経路を考えます。
問題を解く
実際に通行止めがある問題の最短経路を求めてみます。
手順ごとに紹介します。
Cを通る最短経路
「A→E」の最短経路は3個の→、２個の↑、計5個の並べ替えです。そのため・・・
「E→B」の最短経路は3個の→、3個の↑、計6個の並べ替えです。そのため・・・
Dを通る最短経路
「A→F」の最短経路は4個の→、3個の↑、計7個の並べ替えです。そのため・・・
「F→B」の最短経路は1個の→、3個の↑、計4個の並べ替えです。そのため・・・
CとDを通る最短経路
「A→E」の最短経路は3個の→、２個の↑、計5個の並べ替えです。そのため・・・
「E→B」の最短経路は1個の→、3個の↑、計4個の並べ替えです。そのため・・・
解答
求めた数を以下の式にあてはめます。
「最短経路」の応用
最短経路の考え方は次のような問題でも応用できます。
上の問題を例に解説します。
(1)の解答・解説
「玉の取り出し方」が「最短経路」とどういう関係があるの？
と思うかもしれませんが・・・
「赤玉をとる」ことを「→」、「青玉をとる」ことを「↑」と考えると、以下の図の地点AからＢに行くための最短経路の総数と置き換えることができます。
最短経路は4個の「→」と4個の「↑」の計8個を一列に並べる場合の数なので・・・
(2)の解答・解説
(2)は(1)のように一筋縄には行きません。
ただ、(x,y)の座標平面を導入して「x座標」を「取り出した赤玉の数」、「y座標」を「取り出した青玉の数」に対応させ、「x座標」が「y座標」より常に多くなるような最短経路を考えます。
以下のような図を導入します。
このような図の最短経路を考えれば「常に赤玉が青玉より多い」です。
以上から計5通りです。
まとめ
今回は「最短経路」の問題について簡単にまとめました。
今回のポイントをまとめると以下の通りです。
- 「最短経路」の問題は「同じものを含む順列」にできる
- 「通行止め」なら「チェックポイント」考える
- 「最短経路」は「玉の取り出し方」に応用できる
それでは、また次回の記事でお会いしましょう。
