2004　京都大学　後期電気電子論述問題MathJax

【１】　図１のような$\mathrm{A}\text{〜}\mathrm{P}$の各地点を結ぶ正方格子状の道路網がある．各道路は，それにつけられた矢印の向きにしか通行できない．また，各道路の通行に要する時間は道路ごとに決まっており，その値は図１に記されたとおりである．出発地点$\mathrm{A}$から目的地点$\mathrm{P}$に最短時間で到達するにはどの経路を通ればよいか，という問題を考える．なお，この道路網の任意の$2$地点$X\text{，}\mathrm{Y}$について，$X$から$Y$への経路が存在する場合，$X$から$Y$へ最短時間で到達する経路を$X$から$Y$への最適な経路とよぶことにする．

　以下の設問に答えよ．

設問１　図１で$\mathrm{A}$から$\mathrm{P}$への経路は全部で何通りあるか．また，一辺の道路の数が$n$（図１では$n=3$）の正方格子状の道路網に，図１と同様に矢印をつける．このとき，左端の出発点から右端の目的地点への経路は全部で何通りあるか．

設問２　$\mathrm{A}$から$\mathrm{P}$への最適な経路上の$\mathrm{P}$以外の任意の地点$\mathrm{Z}$を考える．$\mathrm{A}$から$\mathrm{P}$への最適な経路のうちの$\mathrm{Z}$から$\mathrm{P}$への経路は，$\mathrm{Z}$から$\mathrm{P}$への最適な経路であることを説明せよ．

設問３　設問２で示された事実を利用して，道路網上の$2$地点間の$2$つの経路の所要時間の大小比較を繰り返すことで，出発地点$\mathrm{A}$から目的地点$\mathrm{P}$への最適な経路を求める方法を示せ．$2$つの経路の所要時間の大小比較の回数がなるべく少ない方法を示すこと．また，$\mathrm{A}$から$\mathrm{P}$への最適な経路を示せ．

設問４　設問３の方法以外に，出発地点から目的地点への最適な経路を求める方法として，出発地点から目的地点へのすべての経路の所要時間を計算して，それらの大小比較を行うことにより最適な経路を求めるという方法が考えられる．この方法では，出発地点から目的地点への$1$つの経路の所用時間の大小比較を繰り返すことで，出発地点から目的地点への最適な経路を得ることができる．いま，この方法を方法１とよび，設問３の方法を方法２とよぶことにする．

　設問１と同様の，一辺の道路の数が$n$の正方格子状の道路網を考える．方法１と方法２のそれぞれについて，出発地点から目的地点への最適な経路を求めるために，$2$つの経路の所要時間の大小比較が何回行われるかを$n$の式で表せ．さらに，$n=10$としたとき，方法１と方法２のそれぞれについて，経路の所要時間の大小比較に要する総時間を計算せよ．ただし，$1$回の大小比較には${10}^{-3}$秒要するものとせよ．