[HOME][発明]

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

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

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

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.3 巡回セールスマン問題を高速に解く MS-DOS tsp13.lzh 94/8/

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

関連ページ

特許
中央値分割
TSPの応用
計算幾何学
アルゴリズム帝国主義
応用分野の穴を探す
4分木の問題点
バケット法の時の計算量
開発のフェーズ
最小木

04/05/25 17:52 更新

発明ディレクトリ

Google
Web www.PAG1U.net

関連ディレクトリ

画質

計画

ダウンロード

通信

関連サイト

乱雑な本棚:計算幾何学

乱雑な本棚:画像圧縮

乱雑な本棚:発明

乱雑な本棚:最適化

 
 
 
 
 
seo

ホーム 発明 掲示板 (C)松岡肇、メール