平成20年 秋期 基本情報技術者 午前 問76

A社の営業員がA社から出発して、取引先のB社、C社、D社を1社ずつ訪問してA社に戻りたい。
各社間(FromからTo)の所要時間を表のとおりとするとき、最短の巡回時間は何分か。

【キーワード】
・経路探索

• 経路探索
  出発地から目的地まで、複数の経路や中継地点がある場合は、どの経路を通れば最も運賃(輸送費)を少なくすることができるかが問題になります。(最近は、駅すぱあとのようなソフトのおかげで自分で計算することは少ないですが…)
  この問題の解き方は、中継地点ごとに最も安い運賃を求めながら、出発地から目的地の運賃を求めます。
  似たような問題に線形計画法がありますが、線形計画法のように連立方程式は用いません。

戻る 一覧へ 次へ