巡回セールスマン問題(TSP、トラベリングセールスマン問題)とは、ある都市にいるセールスマンが、ある数(ここではN)の都市を総移動距離（歩いた距離、ガソリン代、交通費など）が最小になるように、訪問する方法を探す問題です。とっても難しい問題なのでこのアプレットでは正しい答えが得られないことが多いです。(ずーーーーーーーっと待っていれば正しい答えが得られますが・・・)
上のアプレットはdがセールスマンの歩く距離(白い線の長さの和)です。この値がより小さくなる方法が見つかる度に図を描きかえるようになっています。いつかは正しい答えにたどりつきますが、それがいつなのかは謎です。
counterは計算時間を測るためにおいてあるだけで、特に意味はありません。点の数が多いほどcounterの進み方は鈍くなります。
上の説明ではわかりにくいし、もっといい答えを速く求める方法もあるので、参考文献を紹介いたします。
●参考文献
・山本芳嗣・久保幹雄著、朝倉書店、巡回セールスマン問題への招待
・Gerhart Reinelt著、Springer-Verlag(出版社)、Traveling Salesman - Comunicational Solutions for TSP Applications - Lecture Notes in Computer Science 840
・E.L.Lawler, J.K.Lenstra, A.H.G.Rinnooy Kan, D.B.Shmoys著、WILEY(出版社)、The Traveling Salesman Problem
●Javaプログラムのダウンロード(notsp.java 15KB)
●VBプログラムのダウンロード(tspa.lzh)
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
までメールを送るか、●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
メールの際には、ウィルスやいたずら、広告のメールと誤解しないように、
”ホームページ見ました:”ではじまるわかりやすい件名でお願いします。
よい件名の例:
ホームページ見ました:ボロノイ図について
ホームページ見ました:シュタイナー問題
悪い件名の例:
こんにちは、はじめまして、お願い、Hello, Hi, I love you, test
また、初めてメールくださる場合は添付ファイルは付けないようにお願いします。
●大山崇のホームページ