C/C++の宿題片付けます 145代目
■ このスレッドは過去ログ倉庫に格納されています
0032デフォルトの名無しさん
2011/01/05(水) 16:25:35[2] 問題文(含コード&リンク):
巡回セールスマン問題
いくつかの都市と都市間を結ぶ経路があります。全ての都市を一巡するのに最も短い経路を求めるプログラムを作成せよ。
TSPのデータファイルはgr17.txtで、数字の部分が都市数です。
ファイルの記述の仕方が以下のようになっています。
gr17.txtの例
17 最初の数値は都市数
0 第0都市と第0都市との距離が0
633 0 第1都市と第0都市との距離が633、第1都市と第1都市との距離が0
257 390 0 第2都市と第0、第1、第2都市との距離がそれぞれ257,390,0
91 661 228 0 以下同様
412 227 169 383 0
150 488 112 120 267 0
以下略
補足説明として
・同じ道を通ってもよい
・全ての都市を1回通ればよい(巡回しなくていい)
・全探索はなるべく使用しないで深さ優先探索、分子限定法を用いること
[3] 環境
[3.1] OS:Linux
[3.2] コンパイラ名とバージョン:gcc
[3.3] 言語:C
[4] 期限: 1月12日
不明な点があったら指摘してください。よろしくお願いします。
■ このスレッドは過去ログ倉庫に格納されています