ITパスポート試験 ITパスポート 2016年 (平成28年 春期) 問33: 地点Xから出発してA,B,Cの3地点の全てを経由して地点Yまで行きたい。各地点間の経路と所要時間が図及び表のとおりであるとき,地点Xから地点Yまで行く最短の時間

問題本文

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

選択肢

• ア.110
• イ.130
• ウ.140
• エ.150

正解

イ. 130

解説

X→A,B,Cを全て経由→Yへの最短時間問題. 表からX起点はA20,B20,C40分,Y終点はB60,C60分着可,A→Yは不可,A→B40,A→C30,B→A40,B→C20,C→A30,C→B20分. ありうる順列のうち,X→A→C→B→Y: 20+30+20+60=130分,X→A→B→C→Y: 20+40+20+60=140分,X→B→A→C→Y: 20+40+30+60=150分,X→B→C→A→Y: A→Y不可,X→C→A→B→Y: 40+30+40+60=170分,X→C→B→A→Y: A→Y不可. 最短は130分でX→A→C→B→Yとなる. すべての経由必須経路を漏れなく計算する力が問われる典型問題である.

選択肢ごとの解説

• ア.誤り. 110分とするには各区間の合計が110を超えない経路が必要だが,XからAまで20分,AからCまで30分,CからBまで20分,BからYまで60分の合計130分が最短経路となるため,110分を下回る経路は存在しない. 表に基づく計算結果と整合せず,本値は最短時間とはならない.
• イ.正しい. X→A→C→B→Yの順では,20分+30分+20分+60分=130分でA,B,C全てを経由できる. 他の順列も比較すると,X→A→B→C→Yは140分,X→B→A→C→Yは150分などとなり,A→YやC→A→Y側はAから直接Yに行けないため不可. したがって130分が最短となり本選択肢が正しい.
• ウ.誤り. 140分はX→A→B→C→Y(20+40+20+60)など別経路の所要時間であり,本問の最短経路X→A→C→B→Yの130分より長い. AからBへ40分かかる経路よりAからCへ30分→Cから20分でBの順序の方が短くなるため,140分は最短ではない.
• エ.誤り. 150分はX→B→A→C→Y(20+40+30+60)などの所要時間で,本問の最短経路130分より長い. BからAまで40分,AからCまで30分というルートは,X→A→C→Bルートに比べ初手の選択が非効率となり,3地点経由の最短時間としては適切ではない.