TSP実験 TAページ

最終更新 2014.07.09

担当TA: 飯塚　洸二郎
izk@syou.cs.tsukuba.ac.jp

お知らせ

4/18(Fri) 授業を開始しました
4/25(Fri) 既に何人かに回答しましたが、質問はメールでも受け付けます

☆最終発表について
日時:7/11(Fri) 13:45~
場所:3F815セミナー室
発表前日までにスライドを作成してTAまで提出してください。
なお当日はPCを持参してください。

日程

5/23(Fri) 中間発表
7/11(Fri) 最終発表

実験概要

巡回セールスマン問題を解かせるヒューリスティクスを実装します．厳密解法一つ,ヒューリスティック解法を二つ実装することが課題です.詳しくはテキスト参照.
実験の最後には各自に作成してもらったヒューリスティクスについて簡単なプレゼンを行なってもらいます．
(ヒューリスティクスの速度や精度だけでなく｢アイデアの面白さ｣，｢プレゼンの上手さ｣なども評価されます．)

実験のヒント

text1
text2

入力フォーマット

入力は、1行目に都市数．2行目に以降にスペース分けで都市のx, y座標を入力します.
例
7
50 0
150 0
0 100
105 95
200 100
50 200
150 200

実装の環境

標準入出力が行える言語に限り、プログラミング言語に制限はありません.
※以下の記述は、旧計算機システムの上で確認した動作に基づいています.
C(C++)言語を使用したプログラム例と、実験ツールを紹介します. こちらで用意したtspShow.cとリンクさせてコンパイルしてください．

コンパイル

enumTsp.cの形式にそったプログラミングソースを用意します．
ヒューリスティクスごとにファイル名を変えるとよいと思います．enumTsp.cは上書きせず残しておくことをおすすめします．
tspShow.cとリンクさせてコンパイルを行います． X11のライブラリを使用しているので，オプションで指定します．

3C113のMacマシンでコンパイルを行う場合は，以下のようにしてください．

例: gcc -O2 -I/usr/X11/include/ -L/usr/lib/ -L/usr/X11R6/lib -lX11 -lm tspShow.c enumTsp.c -o outputFileName

alias や makefile を利用することで入力が楽になるので，各自調べるか，その都度相談してください．
tspShow.cには順回路表示用の機能も入っているので，アルゴリズムのテストやデバッグに活用してください．
C++を使用する場合や環境によっては細かい違いが出てくると思うので，各自対応してください．相談は受付けます．

作成したプログラムの実行

tspShow.cとリンクさせて作成したプログラムは，以下のように実行することができます．（説明の簡易化のため実行ファイルをenumTSPと名付けて，カレントディレクトリ上に置いてあるとします．）

./outputFileName Option FileName

InputFile

"FileName" :

巡回セールスマン問題の都市データを読み込みます．"FileName"も"-r"指定しない時，標準入力からファイルを読み込みます．読み込める都市データのファイルは以下の形式のものです．

TSPLIB にある拡張子.tspのファイルのうち2次元座標のデータ．(./libにある拡張子.tspのファイルがそれです．それぞれの問題の最短距離も確認してみてください．)
1行目に都市数．2行目に以降にスペース分けで都市のx, y座標を入力したデータ．

InputOption

"-r number" :

numberを都市数として，入力する都市データをランダムに作成します． "FileName"が指定されている時は無視されます．

"-s number" :

numberを"-r"で使用するランダムシードとします．

OutputOption

"-c" :

都市データを標準出力に出力します．("FileName"で説明した、2番めの形式)

"-t" :

順回路データを標準出力に出力します．都市番号をスペース区切りで出力．

GraphicsOption

"-n" :

グラフィクス表示を無視します．(実行速度を測定する場合や大規模な問題を解くときにはこのオプションを指定してください．実行が早くなります．)

"-a" :

グラフィクス表示のアスペクト比を無視し，画面全体に広げてしまいます．

"-w number" :

ウェイト時間のパーセンテージをnumberに指定します．