大学の研究で、巡回セールスマン問題(Traveling Selesman Problem:TSP)について研究しています。
現在、C言語でTSPを解くためのプログラムを作成しています。
TSPを解くための練習問題として、TSPLIBというものを発見
したのですが、
どのように使えばよいのでしょうか？
ためしにファイルを一つダウンロードしてみたのですが、使い方がよくわからず
困っています。
うまく説明できていないので分かりづらいと思いますが、分かる方、よろしくお願いします。
練習問題だと書いているので、buynnnmmm1さん がホームページだと言っている場所からたどれるファイル(例えば a280.tsp.gz の中身のa280.tsp)のことだと思いますが、ファイルのフォーマットはこのページの
> Description
> A complete description of the library is given here
のDOC.PSに書かれています。
例としてあげたa280.tspの場合だと、ファイルのヘッダー部の内容、
> TYPE : TSP
> DIMENSION: 280
> EDGE_WEIGHT_TYPE : EUC_2D
から、ノードが280個の2次元のユークリッド距離データであるTSP問題用のファイルであることが分かります。
必要ならば、このヘッダー部の記述内容をチェックしても良いけれど、
> NODE_COORD_SECTION
以降が、各ノードの
[ノード番号] [X座標] [Y座標]
なので、このデータでノード i とノード j 間の距離を、作成したTSPプログラム自身で計算しても良いし、TSPプログラムで扱いやすい形式へ変換するプログラムを、別に作成するのもひとつの方法です。
--------
registration form に記入することで、「Bob Bixby & Gerd Reinelt 」がDevelopersだというTSPLIBのPackageをダウンロードができる(かも知れない、未確認な)Webページが存在するけれど、そこには
> TSPLIB - A library of travelling salesman and related problem instances
=> 巡回セールスマンおよび関連問題の事例ライブラリ
と書いてあるし、そのページの説明(Abstract)やらPlatforms指定がなくBuild/Instalationも書かれていないし、上記のDOC.PSの内容からも、TSPおよび関連問題(例えばハミルトン閉路問題)での解くべき例題データであり、registration form記入で取得できるPackageも、
http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
から取得できる例題と同じような気がしますけど？ ＞ buynnnmmm1さん
没有评论:
发表评论