修了試験 2013-06-23実施分 基本情報技術者試験 問74

解説

正解は2です。 A社を出発してB社、C社、D社を1回ずつ回り、A社に戻る経路の所要時間を全て比べます。 表の所要時間は往路と復路で同じなので、逆回りの経路は同じ時間になり、実質3通りを調べればよいです。 【計算】 A、B、C、D、Aの順では、20＋50＋30＋40＝140分です。 A、B、D、C、Aの順では、20＋25＋30＋35＝110分です。 A、C、B、D、Aの順では、35＋50＋25＋40＝150分です。 残りの3通りは、これらの逆回りなので同じ時間です。 最短はA、B、D、C、A（または逆回り）の110分です。 【選択肢別解説】 1：× 95分になる巡回経路はありません。 どの順で回っても、最短は110分です。 2：○ A、B、D、C、Aの順で回ると110分となり、全経路の中で最短です。 3：× 140分はA、B、C、D、Aの順の所要時間です。 最短ではありません。 4：× 150分はA、C、B、D、Aの順の所要時間で、最も長い経路です。 【ポイント】 訪問先が少ない巡回問題は、全ての経路を書き出して比べるのが確実です。 往復の時間が同じ表なら、逆回りを省いて調べる数を半分にできます。