2012年5月5日星期六

大学の研究で、巡回セールスマン問題(Traveling Selesman Problem:TSP)について研...

大学の研究で、巡回セールスマン問題(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さん

没有评论:

发表评论