巡回セールスマン問題

ってなに

2

あー、休憩中だからマジレス。
1よ、がんばれ。
＜問題＞
ある会社のセールスマンがいます。
このセールスマンは受け持ちの都市をすべて訪問して、仕事が終ったら戻ってこなければいけません。
同じ都市を２度訪問せずに、 最短距離ですべての都市をまわる経路を求めなさい。

問1
このセールスマンの受け持ちの都市をA,B,C,D,Eとし、出発点をAとすると、道順はいくつあるか？

問2は次の方の出題。

問2
　　　問1を解け．

>>4
よくわからないけど、24通り？
最短距離とか意味不明

>>5
俺も24通りだと思うが，最短経路という条件があるという問題だけに，答えに困るな．
つか，>>4は>>3の最後の行に突っ込んでるネタなんで，マジレスされても困る．
困ってばかりの俺に乾杯！

ここで一旦，困っちゃう．

アニーリング法だっけか，懐かしいな

最短経路作る暇がなかったので、スマソ。

で、問2を出す人が、経路図作ってくれたらなぁ、と密かな期待
数学パズル本には必ず出てくるね、巡回セールスと、一筆書きと、4色問題

★楽してお小遣い★
簡単・安心・在宅ワーク可能
興味のある方は下記をクリック！！
http://members.aol.com/hnworld/

エネルギー関数ってどうやって求めるの？

遺伝的アルゴリズム使えよ、お前ら。

セールスマンなら，考える前に足を使え．基本を忘れるな！

ねえ重みとかの計算はわかったんだけどエネルギー関数ってどうやって求めるの？

>>14
魚屋で売ってるから，買ってこい．
生で食うなよ，腹壊すから．

昨日、近所の吉野家行ったんです。吉野家。
そしたらなんか人がめちゃくちゃいっぱいで座れないんです。
で、よく見たらなんか垂れ幕下がってて、１５０円引き、とか書いてあるんです。
もうね、アホかと。馬鹿かと。
お前らな、１５０円引き如きで普段来てない吉野家に来てんじゃねーよ、ボケが。
１５０円だよ、１５０円。
なんか親子連れとかもいるし。一家４人で吉野家か。おめでてーな。
よーしパパ特盛頼んじゃうぞー、とか言ってるの。もう見てらんない。
お前らな、１５０円やるからその席空けろと。
吉野家ってのはな、もっと殺伐としてるべきなんだよ。
Ｕの字テーブルの向かいに座った奴といつ喧嘩が始まってもおかしくない、
刺すか刺されるか、そんな雰囲気がいいんじゃねーか。女子供は、すっこんでろ。
で、やっと座れたかと思ったら、隣の奴が、大盛つゆだくで、とか言ってるんです。
そこでまたぶち切れですよ。
あのな、つゆだくなんてきょうび流行んねーんだよ。ボケが。
得意げな顔して何が、つゆだくで、だ。
お前は本当につゆだくを食いたいのかと問いたい。問い詰めたい。小１時間問い詰めたい。
お前、つゆだくって言いたいだけちゃうんかと。
吉野家通の俺から言わせてもらえば今、吉野家通の間での最新流行はやっぱり、
ねぎだく、これだね。
大盛りねぎだくギョク。これが通の頼み方。
ねぎだくってのはねぎが多めに入ってる。そん代わり肉が少なめ。これ。
で、それに大盛りギョク（玉子）。これ最強。
しかしこれを頼むと次から店員にマークされるという危険も伴う、諸刃の剣。
素人にはお薦め出来ない。
まあお前らド素人は、牛鮭定食でも食ってなさいってこった。

今ごろになって得意気コピペされるシミュ板の悲しさよ。

>>17
ねえエネルギー関数の求め方教えろ

>>16
まんまじゃねぇかよ！

imadoki ORIGINAL toha...

なんでこのすれまがじそに載ってるの？>>16神？

なこたーないか
＼(｀Д´ )ノｴｰｲ ｼﾈｼﾈ

吉野家で>>1が刃物振り回し３人死亡
東京都新宿区新宿三丁目の飲食店「吉野家」で２４日午後５時ごろ、「客が刺された」と
男性従業員から１１９番通報があった。４０歳代の男性とその家族とみられる女性や子供
がテーブル脇で倒れており、警視庁はその場に居合わせた無職>>1（23）を殺人の疑い
で逮捕し、取り調べている。
調べによると>>1は２４日午後４時ごろ同飲食店に一人で立ち寄り、「大盛りね
ぎだくギョク」と叫んだのち、突然テーブルの反対側に座っていた家族連れの男性に因縁
をつけたうえ、突然持参したナイフで刺したという。警視庁の調べに対して>>1
は、「向かいのテーブルの家族連れが楽しそうに特盛(つゆだく)を注文したのが許せなく、小一時間
問い詰めたかった。殺伐とした雰囲気が欲しかった。」などと意味不明の内容を話してい
るといい、警視庁でさらに詳しい事情を調べている

ほっぷふぃーるどでとけ！

解決？

おいおい、正統派はちゃんとDPで解けYO
時間かかり過ぎるけど （w

巡回セールスマン問題についての質問です。
ネットで検索したのですが載っていませんでした。
Att532で距離を測る場合
long int length(int i, int j, int *x)
/* p[x[i%n]]とp[x[j%n]]のユークリッド距離 */
/* データatt532の定義に従って計算 */
{
int l;
float ax, ay, a, b;
a=(p[x[i%n]].x-p[x[j%n]].x)*(p[x[i%n]].x-p[x[j%n]].x)
+(p[x[i%n]].y-p[x[j%n]].y)*(p[x[i%n]].y-p[x[j%n]].y);
a=a/10.0;
b=sqrt(a);
l=b;
if(l<b-0.001) l=l+1;
return(l);
}
となっており、このa=a/10.0はお約束のようですが
lin318やlin105,kroA200ではどのような値をとれば
よろしいのでしょうか。またそれはネット上のどこで見てるのでしょうか？

http://www.nanoelectronics.jp/kaitai/dnacom/3.htm

>>26の質問
よろしくお願いします。
Att532では10で割っているので
lin318で6,lin105で2で割ってみましたが、
どうも解が良すぎたり悪すぎたりします。
どなたか巡回セールスマン問題を研究テーマ
にしている方いらっしゃいませんか？

★電話料金を請求しない優良なサイトのみをご紹介しています★
◆http://yahooo.s2.x-beat.com/linkvp/linkvp.html◆

b -> cの通路は、夕食の材料を買い集めている主婦で込み合ってます。
a -> bの通路は、検問中です。
b -> fの通路は、自動車専用道です。

グラフ理論でＴＳＰはやったな〜
巡回サンタクロースとかwebで考察されているのは
サンタが複数いたらとかいう本質でない問題を書いててばからしい
これの本質はどういうアルゴリズムで最短距離を求めるかなのに・・・

学部時代の研究テーマだったなぁ。
懐かしい・・・。
今はどのような手法で解くのが流行っているのかな？？
ニューラルネット？GA?

経路探索の模様をｸﾞﾗﾌｨｯｸ化したら、
うねうねするアレ好き。ﾆｭｰﾗﾙなのか。よーわからん。

>32
GAとSAとかをぶち込んだﾊｲﾌﾞﾘｯﾄﾞな探索ｱﾙｱﾙでない？

これって応用数学とかでやるんですか？

？

（＾＾）

>34
情報数学やアルゴリズムの授業で出てくるねえ．
グラフ理論の話の一環で出てこない事もないので，応用数学でも話がでるかも．

>32
厳密解法ならBranch and Cutと呼ばれる方法で15000都市の例題が解かれて
いるはず（数十台のコンピュータで並列計算して何週間も回したらしいが）
近似解法なら1970年頃にLK法と言うアルゴリズムが提案されており，多くの例題で
最適解から1-2%以内の誤差の精度を出している．
近年の研究はそれの改良もしくは亜流もしくはアルゴリズムの比較解析が主．


分かり易くて有名な問題なので，様々なベンチマーク問題として使われてはいるけど，
効率の良いアルゴリズムと言う意味では研究はすでに収束してる．

（＾＾）

>37最適解から1-2%以内の誤差の精度を出している．
この表現はあまり意味がない。
ＴＳＰの面白みは、最適解と近似解がパターンではまったく違うことであるからだ。
問題の作りようによってはいかようにでも解（近時）は手に入る。
遊びのテーマにしたほうがいいぜ

量子コンピューターに期待

ＴＳＰに対するアプローチについては
（多くの組合せ最適化問題についてもそうだけど）
・最適解を求める解法
・精度保証がある近似解を求める解法
・解の精度の保証はないけど，実用上良い解が得られる解法
が主なところで，研究者によって興味の視点が異なる．

>最適解から1-2%以内の誤差の精度を出している．

と言うのは３番目のアプローチで，理論家（数学者）にとってはどうでも
良い話だが，実務家（工学者）にとっては大事な話なので，それを意識
して議論をしないと話がかみ合わないですよ．


ちなみに

>問題の作りようによってはいかようにでも解（近時）は手に入る。

最適解が容易に得られる例題も簡単に作れるわけで，最適だから近似
だからと言うのは話がちょっと違うんでは？

多分>39さんは理論的なアプローチで考えていると思うのですが，

>最適解と近似解がパターンではまったく違う

そう言う例題が多く存在するだろうとは思いますが，


>問題の作りようによってはいかようにでも解（近時）は手に入る。

これは表現がまずいような気が・・・

任意の例題に対して最適解を求める解法，もしくは精度保証を持つ近似解法
を作るのが難しいから，それらが簡単に求まる例題のクラスを考えてみましょう
と言うのが元々の動機ですよね？

それを例題はユーザーの好きな様に与えていいんですよ，みたいな書き方を
したら何がなんだかわけがわからなくなるかなあと・・・

まあ，ここじゃあ十分な話ができないから，お互い突っ込み入れてもあまり
意味無いから，そう言う意味では>39さんスイマセン(汗)

ＴＳＰは勉強するにはすごく面白い題材だけど，長年多くの人々によって
精力的に研究されて掘り尽くされてきたテーマでもあるので，これから
手をつけるには余り適さないですね．

これからやるなら，発展版のＶＲＰ(Vehicle Routing Problem)とかが，
良いんじゃあないでしょうか．

>43
TSPは、キャバレーでも話題にできるポピュラーなものですね。
最初はやさしいが、さいごはむつかしい。
ときどき流行する。　またさめる。
VRPなんかは、ドライブのとき役に立つとおもうけど！
実際ノートPCでつかったりするけど、迷子になって逆効果！？？
期待しているぜ！
＞４２そう言う例題が多く存在するだろうとは思いますが，
ひとつでもとければ。。。。。

中国人郵便配達問題っていうのとは別物でつか？

>44
>ひとつでもとければ。。。。。

巡回セールスマン問題が（多項式時間で）解けたと言うのは，
任意の例題（都市の配置）に対して（多項式時間で）最適解を与える
アルゴリズムを提示すると言うことです．

なので，ある特定の例題（都市の配置）に対して（多項式時間で）最適解を
与える事ができても，それは巡回セールスマン問題が解けたとはならない
のです．これはある特定の例題集合であっても同じ事です．

ただし，任意の例題に（多項式時間で）変換できるような例題集合があって，
それに対して（多項式時間で）最適解を与えるようなアルゴリズムができれば，
巡回セールスマン問題が（多項式時間で）解けたといえます．

>45
巡回セールスマン問題は全部の都市を巡って初めの都市に戻って
来るのですが，中国人郵便配達問題は全部の「道」を通って（当然
，全ての都市も巡る）初めの都市に戻ってくる問題です．
ここで道とは全都市間の辺を指します．

グラフ理論で言うと，最短のハミルトン閉路を求める問題が
巡回セールスマン問題で，最短のオイラー閉路を求める問題が
中国人郵便配達問題になります．

ネーミングの理由とか問題の難しさは・・・どうだったっけなあ？
マッチングを上手く使うと解ける，と言う話をどこかの本で読んだような
気もするのですが記憶が定かでないです(汗)

>46
ありがとうございます。　あなたの言われる意味で書いたつもりでしたが
わたしの表現はたしかにあまりにも貧弱で、内容がありませんでした。
もちろんあなたのいわれているほうがはるかにすぐれています。
またあなたのいわれていることまでEXPLICITに理解していませんでした。
ありがとうございます。

いつかおあいしたですな、　あるいはすでにあっているかな

http://218.44.246.37/~2ch/

確か、パーセプトロンの次のニューラルネットが出てきたときに、
相互結合型ＮＮで巡回セールスマン問題が解けましたよ。

相互結合型は、その時注目集めたけど、
明確な学習方法が提案されずに今は影の時代・・・・。

すげ〜よ
http://homepage3.nifty.com/digikei/

（＾＾）

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

Job-shop Scheduling Problemsって何？

入場無料！

http://ime.nu/www.net-de-dvd.com/

オススメ！カワイイ娘厳選の無料Hサイト☆！　〜良心的です〜
http://www.yahoo2003.com/moe/linkvp.html

　／:＼.＿＿＿_＼
　|:￣＼(∩´∀｀)　＼　　＜先生！こんなのがありました！
　|:在　 |:￣￣ U￣:|
http://www.japan.pinkserver.com/kaorin/moe/jaz09.html
http://japan.pinkserver.com/kaorin/mona/index.html
http://www.japan.pinkserver.com/kaorin/moe/jaz10.html
http://japan.pinkserver.com/kaorin/moe/jaz08.html
http://www.japan.pinkserver.com/kaorin/moe/jaz07.html
http://japan.pinkserver.com/kaorin/moe/jaz03.html
http://www.japan.pinkserver.com/kaorin/moe/jaz05.html
http://japan.pinkserver.com/kaorin/moe/jaz01.html
http://www.japan.pinkserver.com/kaorin/moe/jaz06.html
http://japan.pinkserver.com/kaorin/moe/jaz04.html
http://www.japan.pinkserver.com/kaorin/moe/jaz02.html

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉

俺の卒論、NNを使ったTSPの解放だった・・・。
いったい何の役に立つのかいまだにわからん。

もちろん、プリント基板などの応用、
ほかに基礎研究として重要なのはしっている。
ただ、実社会において役に立っているのか？？

>>61
どこからどこまでを「実社会」だと思っているのかがわからん。
「プリント基板」は実社会じゃないのだろうか。

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

　　　 　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ

☆　☆　☆　http://www.gals-cafe.com　☆　☆　☆

まみでっす！みんな元気ぃ？夏だねーーー！

あたしね、今どこにいると思う？えへっ、実はアメリカなんだぁ。

でもアナタに逢いたくて、こーんなバイト始めちゃった♪

まみに逢いに来てくれたら、なんと7日間会費無料サービスだし、

しかもしかも10分間も無料なんだよ〜〜！すごいでしょ！

見てくれたアナタにだけの特別サービス！今すぐきて！

二人っきりで楽しいことしようよ！まってるね！

☆　☆　☆　http://www.gals-cafe.com　☆　☆　☆

http://homepage.mac.com/hiroyuki45

http://homepage.mac.com/hiroyuki45/hankaku05.html

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

age

http://www.ro-ch.net/bijou/source/20030908060239_a.jpg

【不幸のレス】
　　 このレスを見た人間は七日以内に死にます。

　　　　　　　※あなたに訪れる死を回避する方法が一つだけあります。
　　　　　それはこのコピペを一時間以内に７つ、別のスレに貼り付ける事です。

>>1
どういうルートを回るのが最短かっての。
でも、実際は、会う順番がある。
最短ルートを取らないケースが多々。

EAX：催促計算手法

SOM 使えばかなり高速に近似解得られるよ

シミュテーティッドアニーリング法で、解決できると聞いたので、
もう終わっていないの?

それより新シャア板言ってみな、糞スレ乱立でかなりすごいことになっている。
糞スレ祭りですよ！！マジ凄い！他板からも糞スレ立てに大勢来ているもよう！
マジ凄いからすぐにこい！！板が閉鎖される前に早く早く！！！！

巡回距離は最小に近いのに、経路の様子が全然違うパスがたくさんあるね。

TSP・・・それは幾人もの偉人達が挑み続け、誰一人勝つことの出来なかった壁

この前、別分野の学生からの話で、ant colony optimizationっての
きいたんだけど、TSPにつかってるみたい。
これが、経路探索でうねうねするっていってたやつ？

>>81
大勢のアリたちがうねうねするやつ。

巡回セールスマン問題に限らず、NP困難問題をDNAコンピュータで解く手法があるよね。
理屈はわかるんだけど、なんかしっくりこないんだよなぁ…。

ユークリッド平面の巡回セールスマン問題は
多項式時間で最適解にいくらでも近づけることができる
アルゴリズムが存在する

アナログコンピュータならNP問題が簡単に解けるなどという妄説をはくひとが
いるが、それはまったくの間違い。連続体は物理的な実在ではないし、熱的ゆらぎ
に相当するノイズが常に伴うことを理解していない。精度無限大のアナログ
的実在は妄想に過ぎない。液体のようなものも、どこかで分子性が姿をあらわす
ときがある。
NP困難な問題をアナログ方式ガジェット(計算機)で高速に解けるという
ことが間違っていることと、物理の非可逆の起源とは相通じるものが
ある。量子コンピュータも、巨視的量子現象を用いない限りは、
アナログ性から来る、確率分布の拡散によりコヒーレンスを急速に
失って、その高速な計算は夢物語になる公算が大きい。

　　ド―――――――――――――――――――――――ン！

最近は中国人郵便配達問題といったほうがいいのかな？

中国人郵便配達問題とは違うはずです。

セールスマン：全ての点を通過する
中国人：全ての道を通過する

セールスマン：全ての点を通過する
中国人：全ての道を通過する

文化大革命中大学から追放された教授がハケーン。
実際の郵便屋がどうやって経路を決めるかついて歩いた。

たとえばこれって中央出版とかモデル？

>>83
DNAコンピュータってのは要するに並列度が極端に高い並列計算機だと
思えばよく、問題の探索空間のサイズ＜＜プロセッサ数ならば非決定性
アルゴリズムが適用できてるのと同じ。
非決定性アルゴリズムが適用できれば、定義によりNP困難問題が線形時間で
解けて当然。

・・・という解釈はどう？ちょっと強引？

「巡回セールス」で検索したら
２ちゃんねるの、しかも、こんな辺境の、糞スレに迷い込んでしまった。

pu

TSPLIBにある例題ってどう読むの？？対称TSPで書かれている数字は
都市の座標と距離なんですか？？マジわからないのでお願いします。

>>94
単純に左から「都市番号」「都市のx座標」「都市のy座標」では。
ちなみに都市間距離の計算には気をつけるべし。小数点以下の扱いを
注意しないと最適解が違ってくる可能性がある。

カオスニューロを使えば楽勝でとけるよ

>>94
英語嫁

難しい話してんねぇ〜

シミュ板ってこーゆー2３年前のスレがたくさん残っているから、



















好きだよ♥

>>88
＞セールスマン：全ての点を通過する
＞中国人：全ての道を通過する
それって双対グラフに過ぎないのでは？

「ハミルトンとオイラー」「セールスマンと中国人郵便配達」は
おおむね相対関係にある。

ハミルトン回路：すべての点を一度ずつ通れるか？

オイラー回路：すべての道を一度ずつ通れるか？

セールスマン：すべての点を一度ずつ通る最短経路は？

中国人郵便配達：すべての道を通る最短経路は？
(ただし、同じ道を何度通ってもよい)

>100
そりゃ平面グラフで考えるからだろ
これらの問題は，一般の有向・無向グラフで定義されており，
平面上で定義されているわけではない．

双対グラフは点⇔領域または辺⇔辺の双対であって、点⇔辺の双対ではないにゃ。

Lee-Kernighan法って、現時点でのTSPチャンピオンプログラムでしょ？
1970年頃に考えられたアルゴリズムなんだ・・・

こりゃー、敷居が高い罠

>104
LeeじゃなくてLinだぞ･･･

Annals of operations research

or-optだよ

その前に
　P=NP
が成り立つか証明してくれ

全く理解ができない件

笑ゥせぇる済まん

>>104
これ本当なんでしょうか？
本当としたらこれ研究している人ってずっと何もやってないということか。
いろんな知見が得られたというかもしれないけど、
それは1970年代にすでに気づかれていたことなんじゃないかな。

解ではなく、手法

気合いが足りないのは完全なセールスマンが巡回するのですか？
数学が問題の理解が足りませんか？1。

お〜れのチンポのマッスルが〜♪

巡回セールスマン問題についての感想を書く問題があるのですが、どのように書いたらいいんですか？

４ヶ月前の話しだがマンション売りの奴を一度断ったはずなのにその後毎日同じ奴が来たｗ

うぜえから、迷惑だから来ないで下さいと言ったら次の日そいつの上司と名乗る奴が「昨日、部下が失礼しました。」と詫びをしに来た。

けど結局その自称上司もマンション説明を始めやがった('A`)


業者さん必死過ぎて恐怖すら感じたよ。

「セールスマンの中のセールスマン、A」
ナレ「午前9時40分。都内某所にそびえたつ高層ビル。そこから颯爽と現れたのがあの、
　　　『巡回セールスマン問題セールスマン』として世間を騒がせたセールスマン、Aである。」
ナレ「Aは35年前、日本屈指の商社に入社したがその後、バブル崩壊により業績は悪化。
　　　そこで編み出した驚くべきセールス方法により、日本全体が業績悪化を発表するなか、
　　　停滞する業界を横目に成長を牽引してきた立役者でもある。
　　　しかし、長い間、企業秘密として独占的に用いられ、Aの名前が表にでることは無かった。
　　　5年前から続いてきた会社との訴訟に終止符が打たれたことで
　　　Aは『巡回セールスマン問題セールスマン』の秘密をついに明かしてくれた。
　　　この方法で世界中のセールスマンの希望の光となることを願っている、とAは語る。」