5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

巡回セールスマン問題

1 :132人目の素数さん:2007/01/21(日) 23:06:18
 

2 :132人目の素数さん:2007/01/21(日) 23:08:36
king

3 :132人目の素数さん:2007/01/21(日) 23:11:28
数学者たちは都市の距離ばかりに着目して多項式時間では解けないなどとほざいているみたいだが、
ユークリッド巡回セールスマン問題は位置という情報も持っているため位置+距離からの最短経路の推測は可能だと考えられる。
--------------------------------------------------------------------------------------------------
P≠NP なら多項式時間での解法は存在しない。
>>1によってP≠NP が証明されたので多項式時間での解法も存在しない。
以上。
--------------------------------------------------------------------------------------------------
例えば1次元の空間上の都市におけるユークリッド巡回セールスマン問題を考えてみるとO(n)で解けることが分かる。
しかしブルートフォースではO(n!)になる。
これが位置が計算量に及ぼす影響である。
この次元に関することも俺はひそかに研究している。(次元を下げることができればO(n)にできるんじゃないか?とか)
--------------------------------------------------------------------------------------------------
おまえ、以前「巡回セールスマン問題」ってスレ立てた
専門学校生だろwwwwwwwwwwww
一緒にゼミやろうって誘われて必死に逃げたのがなつかしいよw
元気してたか?
--------------------------------------------------------------------------------------------------
専門学校と大学のダブルスクールやってるんだよ。
今ちょうど新しいTSPプログラム作ってたところだ。

あの後いろいろ本買って勉強した。
勧められた本も一冊買ったが内容がしょぼかった。

一応俺に多少の誤解があったことは認めるが、根本的に俺の言っていることは正しかった。
というか、俺の理論の方がやっぱりワンランク上だった。

P≠NPがやっと証明できました。
http://science5.2ch.net/test/read.cgi/math/1167141950/l50

4 :132人目の素数さん:2007/01/21(日) 23:11:43
最後に「都市数2」を付けると前スレで決まっただろ!

建て直し。

5 :132人目の素数さん:2007/01/22(月) 00:53:20
>例えば1次元の空間上の都市におけるユークリッド巡回セールスマン問題を考えてみるとO(n)で解けることが分かる。
少なくともO(nlogn)はかかると思うが

6 :KingOfUniverse ◆667la1PjK2 :2007/01/22(月) 09:27:54
talk:>>2 私を呼んだだろう?

7 :132人目の素数さん:2007/01/22(月) 10:39:11
巡回セールスマン問題
http://science4.2ch.net/test/read.cgi/math/1150725457/
いつの間にか前スレ死んでたのか

8 :132人目の素数さん:2007/01/22(月) 20:41:48
>>5
O(n)で済むだろ。

9 :132人目の素数さん:2007/01/22(月) 22:44:29
1次元の都市ってw
トポロジカルソートと同次元で考えてる時点で終わってるな。

あと、最短路問題を使おうとしてるみたいだが、
離散凸解析を勉強すると、いかに愚かなことをやってるかが分かるw
M凸とかL凸関数でぐぐってみ

10 :132人目の素数さん:2007/01/23(火) 21:24:14
>>9
べつにソートと同じに考えているわけではないよ。

だから「一次元」ってわざわざ書いたのに・・・。終わってるな。


あと、この手法で解けるようにする次元の研究ってのも、あなたみたいな馬鹿に説明してもわからないかもしれないけど、
イメージ的には例えばクラインの壷は4次元でしか表現できないけど強引に3次元で表現すると壷みたいな形になる。
そんな要領で2次元空間に擬似的な1次元空間を張り巡らせることで実質1次元化できるのではないかということね。
どうせ私がいくら発展的な話をしても君たちは否定すること意外脳が無いことが分かっているから無視してもいいけど。

現在この方面からの研究は行っていないが論文には書く予定。

11 :132人目の素数さん:2007/01/23(火) 21:44:05
>>10
ソート≠トポロジカルソート

基本的な勉強が足りないのでは・・・

12 :132人目の素数さん:2007/01/23(火) 21:52:36
>>11
トポロジカルソートなんて知らなくても、一次元の空間の座標をソートすれば最適解になるでしょ?

基本的にソートで十分なのでは・・・

13 :132人目の素数さん:2007/01/23(火) 22:09:31
論文書いてもrejectされる件

14 :132人目の素数さん:2007/01/23(火) 22:37:56
おまいら言っていることが矛盾しているぞ。

15 :132人目の素数さん:2007/01/24(水) 22:23:24
ところで前スレで聞き忘れたけどコンコルドってどうやったら起動できるの?

ダウンロードしたけど普通に動かないよ。

16 :132人目の素数さん:2007/01/24(水) 23:24:42
>>15
おかしいな。俺は動いたよ。

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ALL_tsp.tar.gz
この辺からちゃんとベンチマーク問題をダウンロードしたか?

17 :132人目の素数さん:2007/01/25(木) 00:06:41
とりあえずダウンロードしたファイルをどうやって解凍すればいいのかよく分からん。

+Lhaca使ったんだけど解凍されたフォルダ内に何も無いし、

Lhaplus使って解凍するとなんかよく分からんファイルが入っているだけ。

コンコルドも論文に記しておきたかったのだが・・・。orz

18 :132人目の素数さん:2007/01/25(木) 00:53:22
>>17
おまいはコンピュータも使えないのかよ。
gzはunixでは標準的な圧縮方式。gz -d で解凍する。

windowsしかなければ
http://www.vector.co.jp/soft/win95/util/se094501.html
とか使え。condordeは書かないとモグリだと思われるぞ・・・

19 :132人目の素数さん:2007/01/25(木) 01:12:40
一応情報系の大学生なのだがorz...

エンドユザーコンピューティングは苦手なのだよ。



どうせ4年間引きこもって巡回セールスマン問題やってるんだったらがんばって数学科目指すべきだったかも・・・。

仮に数学科に行ったところで1年でTSP習うとは限らんのかもしれないが。

20 :132人目の素数さん:2007/01/25(木) 01:53:44
>>19
4年ひきこもって、俺の4日分程度の仕事しかできないのだから、
まずは基礎勉強をすることを薦める。

21 :132人目の素数さん:2007/01/25(木) 19:45:54
http://www.vector.co.jp/soft/win95/util/se094501.html

使ったけど解凍できなかったよ。

>>16のはできるけど。


というか俺間違ったファイルをダウンロードしてしまったのかもしれない・・・。

どのファイルをダウンロードしてどういう手順でwindowsに導入するのか教えてくれYO!

22 :132人目の素数さん:2007/01/30(火) 23:01:18
http://sakuratan.ddo.jp/imgboard/img-box/img20070130225252.gif
concorde何とかダウンロードできたのですが、分岐限定法のやり方がわかりません、
どこをどう設定すればいいのか教えてください。

23 :132人目の素数さん:2007/02/01(木) 22:34:29
やっぱ自己解決したからいいわ。

concordeいいね。

TSPが150%楽しめるような気がする。

24 :132人目の素数さん:2007/02/05(月) 18:17:07
183

25 :132人目の素数さん:2007/02/10(土) 16:16:15
非決定性チューリングマシンと量子力学の多世界解釈

8 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)