図中の矢印に記した数値は、各区間の運賃を表す。
出発地から目的地までの経路のうち、最も安い総運賃は幾らか。
| ア | 19 | イ | 20 | ウ | 21 | エ | 23 |
答え イ
【解説】
この問題のときかたは、出発地からの各中継地の最も安い運賃を計算しながら進めていく方法(1)と、目的地からの各中継地の最も安い運賃を計算しながら進めていく方法(2)があります。
(1)出発地から計算
まず、出発地から中継地4〜7までの経路の最も安い運賃を求めます。
出発地→中継地4は、中継地1と通る経路、中継地2を通る経路、中継地3を通る経路があり、それぞれの運賃は、
“出発地(6)→中継地1(8)→中継地4”の運賃は、14
“出発地(5)→中継地2(6)→中継地4”の運賃は、11
“出発地(2)→中継地3(6)→中継地4”の運賃は、8
になり、出発地→中継地4の最も安い運賃は、“出発地→中継地3→中継地4”の経路の8になります。(C)
同様に中継地5と中継地6の運賃も求めると
出発地→中継地5の運賃は、“出発地→中継地3→中継地5”の10(D)
出発地→中継地6の運賃は、“出発地→中継地2→中継地6”の10(E)
になります。
次に、出発地から中継地7と中継地8の運賃を計算します。上で求めたCDEを利用して
出発地→中継地7の運賃は、“出発地…→中継地5→中継地7”の17(F)
出発地→中継地8の運賃は、“出発地…→中継地5→中継地8”の13(G)
になります。
最後に出発地から目的地の運賃を計算します。上で求めたFGを利用して
出発地→目的地の運賃は、“出発地…→中継地8→目的地”の20
(イ)になります。
(2)目的地から計算
まず、中継地4〜7から目的地まで経路の最も安い運賃を求めます。
中継地4→目的地は、中継地7を通る経路と、中継地8を通る経路があり、それぞれの運賃は、
“中継地4(10)→中継地7(4)→目的地”の運賃は14
“中継地4(11)→中継地8(7)→目的地”の運賃は17
になり、中継地4→目的地の最も安い運賃は“中継地4→中継地7→目的地”の経路の14になります。(C)
同様に中継地5と中継地6の運賃も求めると、
中継地5→目的地の運賃は、“中継地5→中継地7→目的地”の11(D)
中継地6→目的地の運賃は、“中継地6→中継地8→目的地”の10(E)
になります。
次に、中継地1、中継地2、中継地3から目的地の運賃を計算します。上で求めたCDEを利用して
中継地1→目的地の運賃は、“中継地1→中継地6…→目的地”の17(@)
中継地2→目的地の運賃は、“中継地2→中継地6…→目的地”の15(A)
中継地3→目的地の運賃は、“中継地3→中継地6…→目的地”の20(B)
になります。
最後に出発地から目的地の運賃を計算します。上で求めた@ABを利用して
出発地→目的地の運賃は、“出発地→中継地2…→目的地の20
(イ)になります。
【キーワード】
・経路探索
- 経路探索
出発地から目的地まで、複数の経路や中継地点がある場合は、どの経路を通れば最も運賃(輸送費)を少なくすることができるかが問題になります。(最近は、駅すぱあとのようなソフトのおかげで自分で計算することは少ないですが…)
この問題の解き方は、中継地点ごとに最も安い運賃を求めながら、出発地から目的地の運賃を求めます。
似たような問題に線形計画法がありますが、線形計画法のように連立方程式は用いません。
もっと、「経路探索」について調べてみよう。
戻る
一覧へ
次へ