図2 4つの場所間の距離
図2のような距離関係にある4つの場所を順に回って，出発した地点に帰ってきたい．
以下の問いに答えよ．
| (1) | 家から出発し，家→競技場→学校→公園→家と順に回って，家に戻ってきたとする．移動に要した総距離を求めよ． |
図2 4つの場所間の距離 |
| (2) | 家から出発し，3つの場所を順に回り，家に帰ってくる方法は何通りあるか． | |
| (3) | 家から出発し，3つの場所を順に回り，家に帰ってくるルートのうち，総移動距離を最小にするルートを求めよ．その際，どのようにそのルートを導出したのかの過程と，そのルートが最短である 根拠を必ず明記せよ． | |
| (4) | 順に回ってきたい場所の数が家を含めてnヶ所の時，(3)で用いた方法の最悪計算量を評価せよ． | |
| (5) | 小問(3)で用いた方法で最短のルートを導出する．n=16のとき，1秒間に1億回の演算が可能なコンピューターを用いて計算を行った場合，おおよそどの程度の時間で最短ルートを導くのかもとめなさい． 必要ならば，16!=20922789888000，15!=1307674368000として，利用してよい． | |