[HOME] → [発明]

巡回セールスマン問題(TSP)

TSP ( Traveling Salesman Problem 巡回セールスマン問題)

減色ソフトpag1tetoと同じアルゴリズムを、使って高速にＴＳＰ問題を解きます。

1994/7頃に作ったもので、当時、世界最速と言われていたものに対抗して、より高精度、高速 なプログラムにしました。しかし、

『巡回セールスマン問題への招待』朝倉書店

の著者の1人久保幹雄さんによれば、世界最高速というのが、誤報だったようです。

いろんなバージョンのプログラムが入っていますが、最初に作った、ver1.0のプログラムが、最近隣法より精度が高いので意味があると思います。でも、最近隣法がO(n log n)で済むというのは、意外でした。

なお、これは、ユークリッド空間でのTSPです。例えば、「計算幾何学入門」(F.P.プレパラータ+M.I.シェーモス著)で扱われている様に、ユークリッド空間でのTSPは、 計算幾何学 の分野の問題であり、GAやニューロを使わずに、普通に解く方が速いと思います。

Sunのマシンからのアクセスが多いみたいなので、javaアプレットでも作ろうかと思っています。(99/7/24)　

javaで書き始めたら、1.1になって使えない関数とか出てきていて、とまどっています。また、アルゴリズムの面で改良を思いついてしまったので、とりあえず、新しいアルゴリズムをCでコーディングしてからとか思ったのですが、でも、その改良は、精度は上げても速度的には不利だったので、プロファイラーが無いと困るなと思っています。VTuneを買っていないままで最近のバージョンは78000円に値上がりしていました。昔は、Borland Cにプロファイラーが付いていたのですが。あと、最近隣法がn*lognだと知らなかったみたいなのと同じように、最悪の場合はともかく、平均的にはnに比例する手間でTSPを解くアルゴリズムも存在するかも知れないという気がして来ていて、そんなことを考えたりしています。(99/7/31)

結局何もしていません。検索エンジンの検索力比較のために検索していたら、面白い問題が提案されているのを見つけました。セールスマンが複数いた場合の最適化問題です。

n地点の巡回経路は、(n-1)!/2通りなのに対して、m人で分担して巡回する場合には、m人にn地点を分割する手間が増えます。実際にどれくらい難しくなるかはまた後で考えることにします。(2000/3/23)

リンク

TSPは、1,300円のシェアウェアです。

関連ページ

発明ディレクトリ