巡回セールスマン問題
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2007/01/21(日) 23:06:180002１３２人目の素数さん
2007/01/21(日) 23:08:360003１３２人目の素数さん
2007/01/21(日) 23:11:28ユークリッド巡回セールスマン問題は位置という情報も持っているため位置＋距離からの最短経路の推測は可能だと考えられる。
--------------------------------------------------------------------------------------------------
P≠NP なら多項式時間での解法は存在しない。
>>1によってP≠NP が証明されたので多項式時間での解法も存在しない。
以上。
--------------------------------------------------------------------------------------------------
例えば1次元の空間上の都市におけるユークリッド巡回セールスマン問題を考えてみるとO(n)で解けることが分かる。
しかしブルートフォースではO(n!)になる。
これが位置が計算量に及ぼす影響である。
この次元に関することも俺はひそかに研究している。（次元を下げることができればO(n)にできるんじゃないか？とか）
--------------------------------------------------------------------------------------------------
おまえ、以前「巡回セールスマン問題」ってスレ立てた
専門学校生だろｗｗｗｗｗｗｗｗｗｗｗｗ
一緒にゼミやろうって誘われて必死に逃げたのがなつかしいよｗ
元気してたか？
--------------------------------------------------------------------------------------------------
専門学校と大学のダブルスクールやってるんだよ。
今ちょうど新しいTSPプログラム作ってたところだ。
あの後いろいろ本買って勉強した。
勧められた本も一冊買ったが内容がしょぼかった。
一応俺に多少の誤解があったことは認めるが、根本的に俺の言っていることは正しかった。
というか、俺の理論の方がやっぱりワンランク上だった。
P≠NPがやっと証明できました。
http://science5.2ch.net/test/read.cgi/math/1167141950/l50
0004１３２人目の素数さん
2007/01/21(日) 23:11:43建て直し。
0005１３２人目の素数さん
2007/01/22(月) 00:53:20少なくともO(nlogn)はかかると思うが
0006KingOfUniverse ◆667la1PjK2
2007/01/22(月) 09:27:540007１３２人目の素数さん
2007/01/22(月) 10:39:11http://science4.2ch.net/test/read.cgi/math/1150725457/
いつの間にか前スレ死んでたのか
0008１３２人目の素数さん
2007/01/22(月) 20:41:48O(n)で済むだろ。
0009１３２人目の素数さん
2007/01/22(月) 22:44:29トポロジカルソートと同次元で考えてる時点で終わってるな。
あと、最短路問題を使おうとしてるみたいだが、
離散凸解析を勉強すると、いかに愚かなことをやってるかが分かるｗ
M凸とかL凸関数でぐぐってみ
0010１３２人目の素数さん
2007/01/23(火) 21:24:14べつにソートと同じに考えているわけではないよ。
だから「一次元」ってわざわざ書いたのに・・・。終わってるな。
あと、この手法で解けるようにする次元の研究ってのも、あなたみたいな馬鹿に説明してもわからないかもしれないけど、
イメージ的には例えばクラインの壷は4次元でしか表現できないけど強引に3次元で表現すると壷みたいな形になる。
そんな要領で2次元空間に擬似的な1次元空間を張り巡らせることで実質1次元化できるのではないかということね。
どうせ私がいくら発展的な話をしても君たちは否定すること意外脳が無いことが分かっているから無視してもいいけど。
現在この方面からの研究は行っていないが論文には書く予定。
0011１３２人目の素数さん
2007/01/23(火) 21:44:05ソート≠トポロジカルソート
基本的な勉強が足りないのでは・・・
0012１３２人目の素数さん
2007/01/23(火) 21:52:36トポロジカルソートなんて知らなくても、一次元の空間の座標をソートすれば最適解になるでしょ？
基本的にソートで十分なのでは・・・
0013１３２人目の素数さん
2007/01/23(火) 22:09:310014１３２人目の素数さん
2007/01/23(火) 22:37:560015１３２人目の素数さん
2007/01/24(水) 22:23:24ダウンロードしたけど普通に動かないよ。
0016１３２人目の素数さん
2007/01/24(水) 23:24:42おかしいな。俺は動いたよ。
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ALL_tsp.tar.gz
この辺からちゃんとベンチマーク問題をダウンロードしたか？
0017１３２人目の素数さん
2007/01/25(木) 00:06:41+Lhaca使ったんだけど解凍されたフォルダ内に何も無いし、
Lhaplus使って解凍するとなんかよく分からんファイルが入っているだけ。
コンコルドも論文に記しておきたかったのだが・・・。orz
0018１３２人目の素数さん
2007/01/25(木) 00:53:22おまいはコンピュータも使えないのかよ。
gzはunixでは標準的な圧縮方式。gz -d で解凍する。
windowsしかなければ
http://www.vector.co.jp/soft/win95/util/se094501.html
とか使え。condordeは書かないとモグリだと思われるぞ・・・
0019１３２人目の素数さん
2007/01/25(木) 01:12:40エンドユザーコンピューティングは苦手なのだよ。
どうせ４年間引きこもって巡回セールスマン問題やってるんだったらがんばって数学科目指すべきだったかも・・・。
仮に数学科に行ったところで1年でTSP習うとは限らんのかもしれないが。
0020１３２人目の素数さん
2007/01/25(木) 01:53:444年ひきこもって、俺の4日分程度の仕事しかできないのだから、
まずは基礎勉強をすることを薦める。
0021１３２人目の素数さん
2007/01/25(木) 19:45:54使ったけど解凍できなかったよ。
>>16のはできるけど。
というか俺間違ったファイルをダウンロードしてしまったのかもしれない・・・。
どのファイルをダウンロードしてどういう手順でwindowsに導入するのか教えてくれＹＯ！
0022１３２人目の素数さん
2007/01/30(火) 23:01:18concorde何とかダウンロードできたのですが、分岐限定法のやり方がわかりません、
どこをどう設定すればいいのか教えてください。
0023１３２人目の素数さん
2007/02/01(木) 22:34:29concordeいいね。
TSPが150%楽しめるような気がする。
0024１３２人目の素数さん
2007/02/05(月) 18:17:070025１３２人目の素数さん
2007/02/10(土) 16:16:150026１３２人目の素数さん
2007/03/11(日) 22:08:340027１３２人目の素数さん
2007/04/20(金) 18:07:34巡回セールスマン問題において、
例えば、各都市の座標値のみが与えられた巡回セールスマン問題の場合は「ユークリッド巡回セールスマン問題」と呼ばれますが、
他に、
各都市間の距離（双方向とも同じ距離）のみが与えられる場合、
各都市間の距離（双方向の距離が違う可能性もある）のみが与えられる場合、
の各巡回セールスマン問題の呼び名が分かりません。
知っている方が居ましたらぜひ教えてください。
0028１３２人目の素数さん
2007/04/20(金) 21:56:51前者は対称巡回セールスマン問題、後者はただの巡回セールスマン問題。
0029１３２人目の素数さん
2007/04/20(金) 22:27:06どうもです。。。
0030１３２人目の素数さん
2007/05/08(火) 20:55:24■ このスレッドは過去ログ倉庫に格納されています