平成28年度春期 ITパスポート試験問33

この問題の解説と、これまでの解答の記録です。

問33

頻出度★★☆

地点Xから出発してA，B，Cの3地点の全てを経由して地点Yまで行きたい。各地点間の経路と所要時間が図及び表のとおりであるとき，地点Xから地点Yまで行く最短の時間は何分か。ここで，3地点A，B，Cはどのような順番で経由してもよいものとする。単位　分

始点＼終点	A	B	C	Y
X	20	20	40	不可
A	−	40	30	不可
B	40	−	20	60
C	30	20	−	60

出典　平成28年度春期 ITパスポート試験問33

解説

問 33全地点経由の最短経路問題（巡回セールスマン問題の小規模版）

不正解ア
110分。Y に入る最後の辺は必ず60分（B→Y か C→Y）かかり、残る X→A→C→B の3辺で50分以下に収める組合せは存在しない。どの並べ替えでも合計は最短130分を下回らず、110分は過小評価で成立しない。
イ
正解表は「始点→終点」の所要時間（分）を表す。X を出発し A・B・C を全て経由して Y に至る経路を、A・B・C の並べ替え（全6通り）で総当たりして所要時間を比べる。ここで Y へ直接入れる辺は B→Y＝60、C→Y＝60 だけ（X→Y と A→Y は「不可」）なので、最後に経由する点は B か C に限られる。最短は X→A→C→B→Y の順で、20（X→A）＋30（A→C）＋20（C→B）＋60（B→Y）＝130 分。よって正解は「イ」の130分。
不正解ウ
140分。これは X→A→B→C→Y ＝20＋40＋20＋60 の経路の値で、経路自体は有効だが最短ではない。B と C の経由順を入れ替え X→A→C→B→Y にすると A→C＝30、C→B＝20 となり130分で済む。
不正解エ
150分。これは X→B→A→C→Y ＝20＋40＋30＋60 の経路の値で、最初に B を経由し A へ戻る（B→A＝40）ぶん遠回りになっている。有効な経路だが最短ではない。

ここがポイント

全地点経由の最短経路問題（巡回セールスマン問題の小規模版）。経由点 A・B・C の並べ替えを全列挙し、各順序の区間所要時間の合計を比較して最小を選ぶ。
Y へ直接向かえる辺は B→Y と C→Y のみ（X→Y・A→Y は「不可」）なので、最後に経由する点は B か C に絞られる。この制約を使うと調べる並びを減らせる。

用語

解答問33イ