トップページ⇒math
1001コメント342KB

巡回セールスマン問題

レス数が1000を超えています。これ以上書き込みはできません。
0001１３２人目の素数さん2006/06/19(月) 22:57:37
私は巡回セールスマン問題というものを解こうとしています。
巡回セールスマン問題とはなにか？という人は下記URLを参照して下さい。
http://e-words.jp/w/E5B7A1E59B9EE382BBE383BCE383ABE382B9E3839EE383B3E5958FE9A18C.html

私は約2年間研究を続けていますが、私独自のアルゴリズムではまだ最適といえる解が
そう多くもない要素数でも確実に出すことはできません。

現在私はTSPLIBというサイトにあるeil51という問題に挑戦しています。
私のプログラムが出した距離は436.335512であり、現在知られている最短距離(下記URL参)
http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/stsp-sol.html
より2%以上も多くなってしまいました。

なお、私のプログラムが算出した結果を視覚的に表したものが下記URLにあります。
http://sakuratan.ddo.jp/uploader/source/date15996.bmp
最短経路っぽいですよね。。。

有能な2ちゃんねらーの皆様。どうか私に知恵をお貸しください。
0002１３２人目の素数さん2006/06/20(火) 00:07:44
いや、無理っすよ
0003１３２人目の素数さん2006/06/20(火) 00:35:30
数学者はあんまり興味無さそう…
0004１３２人目の素数さん2006/06/20(火) 01:25:42
そうでもないとは思うが。
0005１３２人目の素数さん2006/06/20(火) 01:29:48
線形計画法に持ち込めなければ、諦めろ。
0006１３２人目の素数さん2006/06/20(火) 02:21:26
実際沢山のサラリーマンに巡回させてみりゃいいんじゃね？
自ずと答がでるだろ
0007１３２人目の素数さん2006/06/20(火) 04:49:57
>>1
最短経路っぽくない
0008１３２人目の素数さん2006/06/20(火) 05:09:47
近似アルゴリズムのスレッドって2chにないのかな？
0009１３２人目の素数さん2006/06/20(火) 05:14:59
昔hadタンのスレにいた奴だな
計算理論の基礎すら分かってないド素人だったがあれから少しは勉強したのか？
0010１2006/06/20(火) 08:14:32
>>5
線形計画法は計算量もそんなに大きくないから組み込みたい手法ではありますね。

>>6
>サラリーマンに巡回させて
ある意味ニューラルネットワーク的な手法ですね。
しかし、人間の力でもこの問題はかなり難しいです。
私が買った本「巡回セールスマン問題への招待」という本の作者が毎講演で提示している
問題を解けた人は一人もいなかったみたいです。
http://www.infonet.co.jp/ueyama/ip/software/salesman.html
にある問題を実際にやってみればわかりますが、人間に解かせれば割合優秀な近似解が得られますが
確実な解を得ることはまず無理です。

私のプログラムは一応この問題は解けました・・・(というか下にあった経路図と一致した)。
0011１３２人目の素数さん2006/06/20(火) 09:50:26
経路は一筆書きで、交差させずに最後の点を最も始点に近いところにとるとか？
0012１３２人目の素数さん2006/06/29(木) 06:50:52
>>10
http://www.tsp.gatech.edu//concorde.html
コンコルド使えば？

確か、分枝切除平面法だったと思われ。
0013１３２人目の素数さん2006/06/29(木) 09:23:03
>>10
または、海洋大の久保さんに直接聞きに行ってはどう？
TSPソルバーも公開していたはずだよ。
0014１３２人目の素数さん2006/06/29(木) 20:57:20
>>6
生身の人間にやらせると
「途中ここの自販機でコーヒーを買う」とか
余計なことするから不適解になるｗ
0015１３２人目の素数さん2006/06/29(木) 21:13:09
日本全国にあるラーメン屋を一筆書きで巡回する方法　巡回ラーメン問題

各ラーメン屋をＨＤＤに登録すれば、一軒づつポインターがついてゆくので
順番に手繰れる。電話番号順でもいい。
0016１３２人目の素数さん2006/06/29(木) 21:22:55
A=aijei^ej
SA=minTrace(A,ei^ej)
0017１３２人目の素数さん2006/06/29(木) 21:29:56
分岐点では２度とおることになるから、出発点はバウンダリー、
でも、バウンダリーでは最短時間になるとは限らないから、
最適解はないときもある
だから、２度通ることも許すのが現実的。
0018１３２人目の素数さん2006/06/29(木) 21:33:14
高校の頃数オリの合宿で秋山仁がやってたやつかｗ
0019１３２人目の素数さん2006/06/29(木) 21:44:41
ｎ個のポイントを一筆書きにまわると、ｎ個のパスができる。
n個の点を互いに結ぶとnC2個あるからそれから、それから長い順に
消していって、ｎ個のパスにすればいい。ただし、各点からはかならず
1個パスを残す。
0020１３２人目の素数さん2006/06/29(木) 21:50:28
しゃぼんだまの膜にｎ個の点をちりばめ、大きいほうの膜を破れば
一発で答えが出るのでは？
0021１３２人目の素数さん2006/06/29(木) 22:32:16
各点からは２個のパスが残る。
0022１３２人目の素数さん2006/06/30(金) 10:54:35
>>20
局所解しかでない
0023１３２人目の素数さん2006/06/30(金) 22:10:11
たしか、適当に一番近い点をつないでいっても、
最適値の2倍以下の局所解が出るんだっけ？
>>22がいうのはそのような解だな。
0024１３２人目の素数さん2006/07/01(土) 04:56:02
石けん水って最適解じゃないの？
002512006/07/01(土) 11:11:48
いつの間にかレスがいっぱい来ている。。。
正直誰も興味ないのかと思ってた。。。

多くの人は巡回セールスマン問題において要素数や要素の位置に関係なく
100%正確な解を出力するアルゴリズムを考える場合、
そのアルゴリズムの計算量はO(n^2)となり多項式時間では解けないと考えているのかもしれません。

しかし、私はすぐにそうは思えないのです。
なぜならば、巡回セールスマン問題にはさまざまな特徴が見られ、
たとえば>>11が挙げているように経路が交差しないように一筆書されるのもその特徴のひとつであります。
つまり、私はこうしたさまざまな関係を抽出しその関係を元に分析をすることにより100%確実な解が得られると考えているのです。
（まあ、当たり前の事。問題はその分析した結果の経路数が要素数に対して多項式通りなのか否かであり、
その経路数が指数的に増加していると考えるのは間違いとは現状ではいえない。)
そして、それらの抽出された関係により計算量はO(n^k) (kは定数)程度で解ける問題だと私は確信しております。
0026１３２人目の素数さん2006/07/01(土) 11:26:33
巡回セールスマン問題ってNP完全だよな？
002712006/07/01(土) 13:01:20
>>26
NP完全以上のNP困難と呼ばれるものですが、私はそう簡単に断言していいのか疑問に思います。
0028１３２人目の素数さん2006/07/01(土) 13:18:36
いや、証明されているから
002912006/07/01(土) 13:29:31
>>28
NP完全だということが証明されているということ？
それとも非決定性チューリングマシン上で多項式時間で解けないことが証明されているということ？
0030１３２人目の素数さん2006/07/01(土) 13:35:55
後者が出来たら大発見だなｗ前者に決まってるだろう。
003112006/07/01(土) 14:25:58
私が買った本「巡回セールスマン問題への招待」にはNP困難というべきだと書かれていたのだが・・・。

とりあえず、時間計算量が下げられないことが証明されたわけではないのだ。
0032１３２人目の素数さん2006/07/01(土) 14:42:56
もちろんそうだが、それができないであろうとほとんどの人は思っている。
そして、その不可能であろうことの証明に力を注いでいるというのが現状。
だから、極めて困難なことに挑戦しているとは言える。そして、>>29のような
質問をしている人間にその困難が克服できるとは思えないと、ほとんどの人
は思うだろうな。
0033１３２人目の素数さん2006/07/01(土) 19:54:40
>>31
まず、NP-Hardの定義を勉強しろ。
そして、近似スキームの勉強をしろ。

最適解を求めるという方針ならば、多項式時間はほぼ無理。
（P=NPが証明されたら可能)
分枝切除平面法ならば、最適性の保証つきでかなり速いが、
ランダムなデータを与えると全然だめだ。
なぜなら問題の構造を生かしたカットを入れているから。

近似解法なら多項式時間のがいっぱいあるから調べな。
0034１３２人目の素数さん2006/07/01(土) 19:55:42
>>31
それと、>>12にも書いてあるが、コンコルドを試してみなよ。
どうしても分からなければマジで著者の久保さんに聞きに行きな。
003512006/07/01(土) 20:38:52
>>33
>まず、NP-Hardの定義を勉強しろ。
>そして、近似スキームの勉強をしろ。
ネット上では端折った説明しかないみたいです。
あなたがこの場でわかりやすく説明してくれるとありがたいです。

>P=NPが証明されたら可能
私はP=NPだと信じて研究を続けてきたのですが。。。

>コンコルドを試してみなよ
英語読めません。ごめんなさい。
0036１３２人目の素数さん2006/07/01(土) 21:07:50
>>35
P=NPだと信じてるならもう教えることは何もないな。
すでにトンデモの仲間入りしてる。
まずは思想を改めてもらわないと。

それと、英語が読めないようだとTSPの研究は無理だぜ。
0037１３２人目の素数さん2006/07/01(土) 21:23:45
>>35
ネットで素人が書いたHPを漁るよりもまともな教科書読んだほうがずっと早いぞ
ついでに山口人生に弟子入りしてP=NPを証明してくれ
0038１３２人目の素数さん2006/07/01(土) 21:29:31
>>35
http://www-wada.elcom.nitech.ac.jp/~wada/SLA/aa1.pdf
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/index.html
本当に探したのか？
いっぱいあるじゃん。

近似スキームってのは誤差εを与えたとき、
その誤差を達成するアルゴリズムのことで、
εに依存した計算量の解析が可能。
TSPにはFPTASが存在しないことが知られているから、
少なくともε^(-1)の計算量での近似解法すら無理。

マジメに勉強する気がないならもう相手にするのやめるから。
0039１３２人目の素数さん2006/07/01(土) 23:47:52
O=n^2+n!
0040１３２人目の素数さん2006/07/02(日) 00:16:04
aijをijの距離にすればaij=0で対称な距離行列ができる。
あとはn!の組み合わせを計算するだけじゃないか。
aijが球面上にあればトポロジーの問題、オイラーラグランジェ方程式
が使えるじゃないか。
0041１３２人目の素数さん2006/07/02(日) 00:27:38
IC回路で電気抵抗を測定するロジック回路を組んで、数十秒回せば
最適ルートがでるだろう。距離なんか測定する必要もない。
0042１３２人目の素数さん2006/07/02(日) 01:53:50
アントコロニー最適化とか遺伝的アルゴリズムで
局所最適解を何回も計算するのが現実的かと
0043１３２人目の素数さん2006/07/02(日) 02:01:40
>>40
100!の値を計算したことある？
0044１３２人目の素数さん2006/07/02(日) 06:12:53
>>42
お前GAの収束の遅さを全然知らないだろ？
0045１３２人目の素数さん2006/07/02(日) 06:45:53
100!のあたいはスターリングの公式ですぐ出るじゃないか
0046１３２人目の素数さん2006/07/02(日) 06:50:06
log(100!)=罵ogn=Slogxdx<100^2/2
100!<exp(5000)
0047１３２人目の素数さん2006/07/02(日) 07:04:22
5MFLOPでexp(5000)回演算させたら何秒で終わる？
0048１３２人目の素数さん2006/07/02(日) 07:10:43
ぐぐると
100 ! = 9.33262154 × 10^157
0049１３２人目の素数さん2006/07/02(日) 07:20:33
100個PCをネットワークさせて99個にPINGを撃てばいいだけじゃないか。
すぐ終わる。
0050１３２人目の素数さん2006/07/02(日) 08:04:05
100個PCをつないで、各PCは送信元の同じPINGは99個のPCにPINGをコピーする。
PINGをうけたPCは2回きたPINGを破棄する。100個が同時に99個PINGを発射すれば
P-問題になってしまう。
0051１３２人目の素数さん2006/07/02(日) 08:14:10
光速でPINGが撃てるセールス専用グリッドボードを製作すれば巨万の富が
チップにして携帯にも組み込める？
0052１３２人目の素数さん2006/07/02(日) 08:30:32
>>49
その99台のコンピュータは99!通りの組合せを計算するわけだ。
99! = 9.33262154 × 10^156
ｶﾜﾝﾈ

>>42
遺伝的アルゴリズムって全く使えないから。
0053１３２人目の素数さん2006/07/02(日) 08:40:05
各ノードではＰＩＮＧのルート情報を読んで、破棄するかコピーするかだけ。通過するときに
次のノードの距離を足すだけ。並列コンピューテイングだから。99*99ステップで全計算がおわる。
0054１３２人目の素数さん2006/07/02(日) 14:20:19
>>53
コンピュータが100!台近く必要なのだが。
0055１３２人目の素数さん2006/07/02(日) 14:24:48
Softeatherで仮想PCを１００個作ればいいじゃないか。
0056１３２人目の素数さん2006/07/02(日) 14:25:39
最短経路なら多項式時間で計算できるからわざわざPC100台準備する必要ない
0057１３２人目の素数さん2006/07/02(日) 14:41:20
NP－Hard問題だから暇つぶしにはいい。
最適アルゴなんかまゆつばだね。
プリズムに偏向版を傾けてはりつけ、レーザーをあてるほうが速いかも？
0058１３２人目の素数さん2006/07/02(日) 14:42:10
>>54
>>49-50,53を見る限りノード計算機は100台で済むんじゃないか？
ただ、ノード計算機は自分以外の99台のノードからパケットを受け取って
その1つ1つのパケットを98個複製して、送信元ノード以外の98台のノードに送り返すから
（もちろん過去に自ノードを通ったパケットは複製せずに破棄するけど）
処理の最初の方でパケット流量が凄いことになりそう
0059１３２人目の素数さん2006/07/02(日) 14:48:51
>>58
パケットをうけとって送り返す回数を考えてみろ
普通に100!通り計算したほうが速い
0060１３２人目の素数さん2006/07/02(日) 15:00:36
>>59
全ノードから受けとったパケットの合計と同じ量を
次のステップでは一台一台のノードから受けとるのか
こりゃ追い付かんなー
0061１３２人目の素数さん2006/07/02(日) 15:07:22
>>41
そういやエニグマの解読も電気工学的手法だったんだよな。
自然現象と上手くかみ合った解法を見つければ超高速に計算できる辺りアナログは強い。
0062１３２人目の素数さん2006/07/02(日) 15:19:10
>>55
100個でなく、100! 個だ

>>59
>>1はアホだから冗談でなく、本気で信じちゃうだろ。
下手な妄想をふくらませる前にやめてやれ。
0063１３２人目の素数さん2006/07/02(日) 15:27:06
数学板の馬鹿共も案外本気かもしれないのだが
0064１３２人目の素数さん2006/07/02(日) 16:03:14
NP-HARDでもKnapsackとかなら簡単なんだがな。
0065１３２人目の素数さん2006/07/02(日) 16:37:43
Ｐ＝ＮＰ？問題が未解決である間、
本スレのようなトンデモが出回るのだろうな。
0066１３２人目の素数さん2006/07/02(日) 17:26:56
部分最適化をどんなに頑張っても、部分が2^100個あるんだから
それ以下にはならないことぐらい簡単に分かりそうなもんだが
0067１３２人目の素数さん2006/07/02(日) 18:03:17
世の中にはコンピュータで解けない問題が多すぎる！例えば、因数分解のように
一見簡単に見える計算問題でも、対象となる数が桁数が200桁くらいになると現在
のスーパーコンピュータでも手出しが出来ない。また、顔の認識判断など、私たち
人間が瞬時でやってのけるような問題に、なぜコンピュータが長い時間を必要と
するのだろう？

１００！個スパコンを買ってってＩＢＭ巡回セールスマン問題だろう
0068１３２人目の素数さん2006/07/02(日) 18:06:58
200桁くらいの因数分解はそろばん１級ならよくやる問題じゃないか
0069１３２人目の素数さん2006/07/02(日) 18:24:16
２００行ぐらいの成績表でピボットテーブルを使うと固まるどこかの
ばか表計算ソフトの壁と同じだな・・・
007012006/07/02(日) 21:42:23
>>36
私は喧嘩を売っているわけではないのですよ。

>>38
http://www-wada.elcom.nitech.ac.jp/~wada/SLA/aa1.pdf
はおそらく大学の講義で使用するためのもので、教授の説明がなければ理解が難しいかと・・・。
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/index.html
は結構うまくまとめられているので暇を見て目を通しておこうと思います。

>マジメに勉強する気がないならもう相手にするのやめるから。
私は今までまじめに巡回セールスマン問題を研究してきましたし
まじめにこの問題を解決しようとこのスレを立て、真面目にレスを行ってきたと自負しています。
それでも私を不真面目と判断するのでしたらどうぞ断りなく退場してください。
掲示板というものは強制参加ではありませんし、教える気もなくただ私を貶すだけの人はいいなくて結構ですから。

レス数が増えたのはいいのですが煽りが多すぎですね。。。
007112006/07/02(日) 21:54:36
>>41
なんだか非常にいいヒントに感じます。
わたしも嘗ては回路に電気を流すだけで最短経路を算出出来るのではないかと考えていました。

もしかして>>41がいいたいことは極端な話、
各都市間を同じ抵抗を持つ導線で網目型に接続し、抵抗が最も少なくなる経路を見つけるということでしょうか？
少し興味深い・・・。
007212006/07/02(日) 22:10:39
>>62
100!がとてつもなく大きな数値であることは知っているが、一概に>>59を否定することも無いと・・・。
もちろん世界中のコンピュータを並列したって無理だってことはわかるのだよ。
現在のアーキテクチャの物はね。
007312006/07/02(日) 22:19:20
>>65
まあ、Ｐ＝ＮＰだと仮定しているということね。
数学的には賢者様たちの言うような結果もあることは事実なのでP≠NPの可能性も片隅にはおいていますよ。

それにしてもＰ＝ＮＰ発言だけでトンデモ扱いはないのでは？
0074１３２人目の素数さん2006/07/02(日) 22:52:51
>>70
>大学の講義で使用するためのもので、教授の説明がなければ理解が難しい
学部の講義ぐらい、説明無しで理解できないようじゃ研究は無理だよ。
どうしても分からなければ、その教官にメールを出してみるとか。
とにかく、あなた積極性がないよ。
別にけなされている訳じゃなくて、態度が悪いんだよ。

「巡回セールスマン問題への招待」ですら
きちんと読んでないみたいだし・・・

>>73
少なくとも、一般的な学会では速攻でトンデモ扱いされるよ。

あと、あなたがやってきた研究を簡単にまとめてPDFかPPTに
まとめてくれれば、問題点を指摘しやすいんだけど・・・
今のままじゃアドバイスも抽象的にしかできない。
0075１３２人目の素数さん2006/07/02(日) 22:56:17
>それにしてもＰ＝ＮＰ発言だけでトンデモ扱いはないのでは？
この板にはP≠NP問題は消滅したとか言ってる香具師もいるからね。
十把ひとからげにトンデモ扱いされる事はある程度覚悟しなければならない。
0076１３２人目の素数さん2006/07/02(日) 22:58:15
>>74
>少なくとも、一般的な学会では速攻でトンデモ扱いされるよ。

P=NPだと信じてる人も1割ほどいるよ(LAアンケート)
0077１３２人目の素数さん2006/07/02(日) 23:00:33
>>76
そうでないと夢がないからでしょ。
実際はほぼ、その可能性は絶望で間違いない。
0078１３２人目の素数さん2006/07/02(日) 23:37:30
可能性が消えてないうちはどっちを主張してもトンデモ扱いされる筋合いはない。
ポアンカレだって反例を作ろうとしていた人はいたし、リーマン予想もいる。

少数派になるのは仕方がないけどね。
0079１３２人目の素数さん2006/07/02(日) 23:45:37
ブラジルまけたのか・・・
0080１３２人目の素数さん2006/07/02(日) 23:46:25
>>79
サッカースレの誤爆？
0081１３２人目の素数さん2006/07/02(日) 23:53:13
>>79
大会直前に絶好調のチームが本番で負けるのはW杯のデフォルト。
直前に問題が多いチームこそ優勝に近い。

また、欧州開催で南米の優勝がないのも有名な話。
0082１３２人目の素数さん2006/07/02(日) 23:54:33
＞教える気もなくただ私を貶すだけの人はいいなくて結構ですから。
＞
＞レス数が増えたのはいいのですが煽りが多すぎですね。。


お約束のパターンを突っ走ってますね・・・
0083１３２人目の素数さん2006/07/03(月) 00:00:37
学ぶ気があるならこんなとこで聞かん普通。
0084１３２人目の素数さん2006/07/03(月) 00:00:45
なんだ、まともな人かと思っていたらトンデモ予備軍かよ。
0085１３２人目の素数さん2006/07/03(月) 00:02:54
まともな人なら巡回セールスマン問題を解こうとか言い出さないと思うが
0086１３２人目の素数さん2006/07/03(月) 00:16:02
ブラジルがヨーロッパでぼろ勝ちしたら、ヨーロッパはサッカーをやらなくなる。
そうすると、金儲けができなくなるから、・・・
0087１３２人目の素数さん2006/07/03(月) 00:17:15
P=NPのことはおいておいて…
英語が読めないから英語の文献は読まないとか言っている人間が，
自分は真面目に研究していると言っている時点で，アマチュア決定ですよ．

アマゾンでも買えるので，下の2冊ぐらいを頑張って読んでから研究始めてください．

E. L. Lawler (ed.)
The Traveling Salesman Problem: A Guided Tour of Combinatorial
Optimization (Wiley-Interscience Series in Discrete Mathematics)
＃有名な本だが1985年出版とちと古いのが問題かも

Gregory Gutin, Abraham P. Punnen (eds.)
Traveling Salesman Problem and Its Variations
(Combinatorial Optimization, V. 12)
0088１３２人目の素数さん2006/07/03(月) 00:18:40
１００箇所の巡回でギブアップしていたら、サッカーは毎回、動きが止まってしまう。
0089１３２人目の素数さん2006/07/03(月) 00:24:39
TSPはぱっとみ、幾何学的な条件で最低エネルギー問題だから、シャボン玉
問題に展開するかオイラーラグランジェかジオデジック、それでなきゃ
パラレル演算でけりがつくハードをつくるだけだ。

偏光ゲート素子で光ネットワークをつくれば、通過してくる光の減衰度合いで
最適ルートのひとつがすぐでる？
0090１３２人目の素数さん2006/07/03(月) 00:26:31
>70
組合せ最適化とアルゴリズムを専門分野とする研究者として
言わせてもらうと，明らかにあなたは勉強が足りません．
せいぜい，学部1,2年生レベルです．

だいたい，研究と言うのは従来研究を理解した上で，それらの問題点を
明らかにして，問題点を克服する新たなアイデアを出すことなのに，
自分自身で勉強や従来研究の調査をできないんじゃダメなんじゃないの？
0091１３２人目の素数さん2006/07/03(月) 00:28:57
各ノードから波長の違うレーザーを同時に照射する。
ファイバーを通過する距離で減衰する。
各ノードを通過するたびに、位相が素数の逆数倍シフトする。
・・・
0092１３２人目の素数さん2006/07/03(月) 00:41:56
A=(aij)=(aji)=(aii=0)
PnA=d(PnA)=P(v,A)
距離行列とn!のパーミュテーションを変数とするｳﾞｪｸﾀｰﾊﾞﾘｭｰﾄﾞ函数の最適化問題
パーミュテーションを連続函数にしてP(t)にすれば、オイラーラグランジェ
0093１３２人目の素数さん2006/07/03(月) 00:58:38
>92
n!のパーミュテーションを用意すれば，可能な巡回路を
全て列挙できるので，各巡回路の距離を計算するだけで
解けます．

n!のパーミュテーションと言っている時点で，TSPの都市数
の指数オーダになってるのでダメですよ．
0094１３２人目の素数さん2006/07/03(月) 01:14:51
パーミュテーションをt=(0,1)にまっぷして微分でとけばいいのです。
デスクリートでやってるからコンビやはキテイーなのです。
0095１３２人目の素数さん2006/07/03(月) 01:21:58
t=(0,1)上で得られた連続最適解を離散最適解に変換できるのでしょうか？
0096１３２人目の素数さん2006/07/03(月) 01:32:21
連続だからその近傍の有理解がある。多様体はウエルでファインドに設定して
極端なピークがないようにする。
0097１３２人目の素数さん2006/07/03(月) 01:40:18
それらの有理解を表現するのに必要なビット数は，
常に都市数の多項式オーダで抑えられるのでしょうか？
そこら辺に問題がある気がしますが…
0098１３２人目の素数さん2006/07/03(月) 01:54:47
最適解自体が数値計算によって得られた近似解にすぎないのであまり考えても意味がない
0099１３２人目の素数さん2006/07/03(月) 02:03:52
…それは逃げでしょう？
TSPは，都市間の距離を有理数で与えれば，n!通りの巡回路を
全て列挙することで，数値誤差に左右されることなく最適値を
求めることのできる問題なんですから．
0100１３２人目の素数さん2006/07/03(月) 02:05:27
最適解なんて求めようとしたら計算時間がいくらあっても足りないから近似解で我慢しろ
0101１３２人目の素数さん2006/07/03(月) 02:08:50
>>89
お前も何も分かってないな。
それじゃ局所最適解だっていってるだろ。
0102１３２人目の素数さん2006/07/03(月) 02:10:40
>>95
だめ。
それを言ったら整数計画と線形計画が同じ程度の難しさと
いってるのと同じだろ。
普通に全然だめな例がゴロゴロしてるからググれ。

FPTASが存在するナップサック問題とかですらうまくいかないよ。
0103１３２人目の素数さん2006/07/03(月) 02:11:22
>>98
数学をやってるものとして、公理とか定義とか
無視してそういうこというの恥ずかしくない？
0104１３２人目の素数さん2006/07/03(月) 02:19:17
ていうか、concordeが現在最強の方法だって教えてもらってるのに、
それを調べないなんて頭おかしいとしか思えない・・・
研究以前の問題だよ・・・
0105１３２人目の素数さん2006/07/03(月) 02:22:00
なにをもって最強と見なすかだな。concordeのオーダーは大きいし
0106１３２人目の素数さん2006/07/03(月) 02:24:54
じゃあArora？
0107１３２人目の素数さん2006/07/03(月) 02:26:37
>>105
まぁね。実測ではナンバーワンなんだがな。

いじわるなことをいうと、concordeでTSPを解くと
ランダムな構造を持たないデータだと
カットが効かなくてconcordeも遅くなっちゃう。
だけど、応用ではあんまりそういう変な例はないけどね。

LPで単体法が未だに使われてるのと同じ事でｗ
0108１３２人目の素数さん2006/07/03(月) 02:37:39
>>1は巡回セールス問題への招待を読んだといってるが、
http://www.tosho-u.ac.jp/~kubo/presen/tsp.ppt
同じ著者のこの辺のスライドとかはきちんと理解してるのか？
0109１３２人目の素数さん2006/07/03(月) 03:59:19
工学じゃ平均的に速いのが「最強」でしょう。
0110１３２人目の素数さん2006/07/03(月) 04:32:59
ざっと読んだんだけど，誰も>>25には突っ込まないの？
0111１３２人目の素数さん2006/07/03(月) 09:27:34
いちいち構ってられんわ！
0112１３２人目の素数さん2006/07/03(月) 17:32:54
>>110
O(n^2)で最適解に行ったら大発見だな。
011312006/07/03(月) 17:54:00
>>74
>学部の講義ぐらい、説明無しで理解できないようじゃ研究は無理だよ
さすがに説明が無さ過ぎだし、下手に解釈して誤解するのは最悪だからさ・・・。
仮に正しい解釈ができたとしてもその解釈に自信が持てなければ意味ないし。

>あなた積極性がないよ。
どうしても検証しておかなければならないことがひとつだけある。
それをどうしても自分で検証しておきたい。
その結果しだいではチューリング賞を目指すくらい積極的になるよ。

>今のままじゃアドバイスも抽象的にしかできない。
現在の手法はまだ公表するべきではないと思っている。
もしも、Ｐ＝ＮＰを裏付ける結果となったら一大事ですから。
もうすぐ夏休みなのでそのときにプログラムを書き換える予定。（いま試験とかで忙しいから。）
もしも自分で検証した結果、間違いであることがわかったらアルゴリズムやプログラム(C読めない人はごめん)を
アップロードしたいと考えています。
そのときには本格的なアドバイス頼みますよ。

ちなみに、私の理論が正しければO(n^7)程度で解けます。
011412006/07/03(月) 17:57:20
言い忘れていたけど、「巡回セールスマン問題への招待」を読み始めたのは結構最近なんだ。（1ヶ月くらい前）
それまでは約1年半試行錯誤してプロトタイプを完成させた。
それをコーディングしながらもいろいろ変えて現在に至っている。
011512006/07/03(月) 18:00:37
>>112
もはや揚げ足取りの領域だから無視するのが妥当なのかもしれないが一応訂正。

//ここから
いつの間にかレスがいっぱい来ている。。。
正直誰も興味ないのかと思ってた。。。

多くの人は巡回セールスマン問題において要素数や要素の位置に関係なく
100%正確な解を出力するアルゴリズムを考える場合、
そのアルゴリズムの計算量はO(2^n)となり多項式時間では解けないと考えているのかもしれません。

しかし、私はすぐにそうは思えないのです。
なぜならば、巡回セールスマン問題にはさまざまな特徴が見られ、
たとえば>>11が挙げているように経路が交差しないように一筆書されるのもその特徴のひとつであります。
つまり、私はこうしたさまざまな関係を抽出しその関係を元に分析をすることにより100%確実な解が得られると考えているのです。
（まあ、当たり前の事。問題はその分析した結果の経路数が要素数に対して多項式通りなのか否かであり、
その経路数が指数的に増加していると考えるのは間違いとは現状ではいえない。)
そして、それらの抽出された関係により計算量はO(n^k) (kは定数)程度で解ける問題だと私は確信しております。
011612006/07/03(月) 18:03:00
ずっとノーヒントでやってきたことなんだから多少無知でも許してくれよ。。。
0117１３２人目の素数さん2006/07/03(月) 18:10:28
>>115
> アルゴリズムの計算量はO(2^n)となり
まだ間違ってるよ
O(n!)だろ。
n! >> 2^n だから圧倒的に違いすぎる。
久保さんの本にも書いてあったと思うが。

> ずっとノーヒントでやってきたことなんだから多少無知でも許してくれよ。。。
それは研究とは言わない。
研究は過去の結果を調査してから始めるのが基本。
0118１３２人目の素数さん2006/07/03(月) 18:12:22
>>113
>さすがに説明が無さ過ぎ
普通の論文なんかもっと説明なさすぎですが？

>Ｐ＝ＮＰを裏付ける結果となったら一大事ですから。
だからそんなことはないから。

>O(n^7)
いいかげんなことばっかりいうなよ。
オーダーの定義をちゃんとしってるのか？
0119１３２人目の素数さん2006/07/03(月) 18:15:57
>>115
> 巡回セールスマン問題にはさまざまな特徴が見られ
だからconcordeはその特徴を使って
分枝切除平面法を構成していると何度いえば（ｒｙ
0120１３２人目の素数さん2006/07/03(月) 18:40:02
かわいそうな>>1がいるスレ
0121１３２人目の素数さん2006/07/03(月) 20:20:54
>>116
むしろそっから先でいろいろ言われてるんじゃん。
012212006/07/03(月) 21:43:51
>>117
個人的にはO(n!)の方が好き。
うちの大学でも一般的なサイトでもほとんどの本でも計算量で最も大きいものはO(2^n)とされている。
もちろん巡回セールスマン問題の計算量もO(2^n)と書かれているものが圧倒的に多い。
私がO(n!)という指標を見たのは久保さんの本と日本経済新聞社のソフトウェア開発技術者試験の午後問題集と
あなたのレスの３回だけです。

>>118
>普通の論文なんかもっと説明なさすぎですが？
論文って簡単なんだな。
適当にごまかしても普通の論文になるね。

>いいかげんなことばっかりいうなよ。
>オーダーの定義をちゃんとしってるのか？
知っている。
ただO(2^((log n)^2))と考えてよい箇所をO(n^2)と置き換えた箇所がある。
0123１３２人目の素数さん2006/07/03(月) 22:02:57
やっぱり>>1はただのトンデモじゃねーか
ヤマジンとhadの仲間が増えたなw
0124１３２人目の素数さん2006/07/03(月) 22:03:10
>>122
O(2^n)をO(n!)と書くならともかく、
O(n!)をO(2^n）と書くのは間違いだ。
2^nと書いてあるのならソースを見せてみろよ。
0125１３２人目の素数さん2006/07/03(月) 22:11:01
TSPがO(2^n)で解けるってのは教科書レベルの常識だろ・・・
0126１３２人目の素数さん2006/07/03(月) 22:26:34
>>122
あんたがやってきたアイディアを
概略でいいから書いてみ？
わざわざ盗もうなんて酔狂な輩はいないと思うから。
どうしても心配なら自分のWebサイトにおきゃいい。
今のままじゃ何も議論が進まん。
0127１３２人目の素数さん2006/07/03(月) 22:31:21
http://www.tsp.gatech.edu/
0128１３２人目の素数さん2006/07/03(月) 22:33:20
DPならn^2・2^n程度だっけ？
どっちにしろ良くないことに変わりないな。
0129１３２人目の素数さん2006/07/03(月) 22:35:36
O(nlogn)で解けるのか・・・100log100だから200ぐらい？
ぜんぜんＮＰ－ＨＡＲＤでないじゃないか？
0130１３２人目の素数さん2006/07/03(月) 22:38:06
>>127
コンコルドは>>12に出てる。
なぜか>>1が使わないのが不思議。
0131１３２人目の素数さん2006/07/03(月) 22:39:27
>>129
近似解だろｗ

このレスみて気づいたが、
>>1は近似解を多項式時間で見つけても
P=NPとは言えないことを知ってるんだろうな？
O(n^7)とかいうのも近似解くさい。
0132１３２人目の素数さん2006/07/03(月) 22:48:17
NP-Completeな問題に対してわざわざNP-Hardと言い続ける理由はなんだろう？
0133１３２人目の素数さん2006/07/03(月) 22:51:39
>>132
決定問題でない場合があるから。
NP-Complere ⊂ NP-Hard だから、どっちでもいい。
普通、NP-Hardの方が安全だな。
0134１３２人目の素数さん2006/07/03(月) 23:38:10
>>131
nによらない定数倍近似ができればP=NPが言える問題があったはずですよ。
最大クリーク問題とかね。というか巡回セールスマン問題もこのクラスだったはず。
三角不等式とかを仮定しないと近似解すら難しい。
0135１３２人目の素数さん2006/07/03(月) 23:56:59
>>134
> nによらない定数倍近似
それが難しいんだがな。
ていうか、P=NPなんて山口人生以来聞いたよ。
学会に持って行ったら追放されるだろうな・・・
0136１３２人目の素数さん2006/07/04(火) 00:19:39
>122
2chだからって学生ばかりが書き込んでると思わないようにな…
カキコを見ると，院生さんや先生もいるようだし．

論文は基本的に新規な内容を中心に書くもので，既知の内容については
参考文献を示すのが通常のやり方．
説明が不十分だと感じるならば，やはり研究するには勉強が足りないと
言うことですよ．

やる気があるのは良いが，人の言うことを素直に聞かない奴は研究室
入っても皆に嫌われてドロップアウトするだけだぞ．
あと英語できないのは，研究やる上で致命傷なので今のうちから
勉強しといた方が良いよ．

あなたが思っている以上に先輩や先生は頭が良くて知識も深いのですよ．
0137１３２人目の素数さん2006/07/04(火) 03:41:25
>>114
1年半試行錯誤するまえに論文読まんかい
013812006/07/04(火) 04:43:33
>>126
盗まれそうでマジで怖い。
ハッキング対策でもうじき研究用マシンはもうじきスタンドアロンにしようと思うし。。。

でも、知られないようにかなり抽象的に書くと
(iは回数をあらわす。この場合は回数自体に特に意味は無いが、回数が変わった条件はまったく別の条件である可能性がある)
1.部分的な都市(i=1のときは全体を指す)を最短経路を導き出すことのできる関係を持たせることができる条件Xiに基づいて分割する。
2.その条件の定義を行う。
3.関係を導き出せなくなるまで1、2を繰り返す。(微妙に違うがデータベースの正規化をイメージすると少し楽かも。)
4.さらに分割した都市間などに条件が見られる場合はその条件を定義する。
5.1～4で行ったことにより実質木構造ができており、この木をたどることで最短経路が導き出せる。

実際こんなにきれいなことはしてないんだけどな・・・。
木をたどるといっても頭の中で勝手にやってプログラム組んだだけだし。
簡単に書くと都市をどんどん分割してそのグループに関係を付加したということね。

>>129
O(n^2)×O(n)=O(n^3)となる。
O(n)の部分をO(1)に置き換えると全体ではO(n^2)となる。
決してO(1)で解けるわけではない。

ああ、わかってるよ。ケアレスミスということにしておくよ。
ただ、自信満々で叩くと自分が間違っているときに痛い目にあうから。

>ぜんぜんＮＰ－ＨＡＲＤでないじゃないか？
私はそう確信していますが断言はしません。

>>131
知っている。心配しないでくれ。
ただ、私が抽出したあ・る・も・のの間にいま非常に強い相関が見られている。
P=NPの可能性がどうしても捨てきれないんだ。
0139１３２人目の素数さん2006/07/04(火) 05:38:29
御託はいいからとっとと証明して論文出せ
話はそれからだ
0140１３２人目の素数さん2006/07/04(火) 06:17:38
TSPがnC2で解ける証明
１　nx(n-1)のグリッドをニクロム線でつくる(長さは距離に比例）
２　水につける
３　ｎC2のポイントに電圧をかける
４　速く水が蒸発した経路がその2点の最適解
５　最初に乾く時間をはかり、ベストの経路を探す。
QED
0141１３２人目の素数さん2006/07/04(火) 06:21:31
>>138
それのどこに最適性の保証があるんだよ・・・ｗ

グラフ分割や最小木を用いた解法ならすでにたくさんあるんだが。
お前のくだらん使い古されたアイディアなんか誰も興味ない。
それより、他の解法と比較しろ。
でないと論文にしても誰も読まないぞ。
0142１３２人目の素数さん2006/07/04(火) 06:22:07
>>140
局所最適解だっていうの何度目？
秋山仁とかの影響受けすぎだ、馬鹿。
0143１３２人目の素数さん2006/07/04(火) 06:29:35
>>138
>ハッキング対策
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ﾊﾗｲﾃｰ
0144１３２人目の素数さん2006/07/04(火) 06:34:17
局所最適をｎC2で比べればベストが出るだろ。
ｎC2でトーナメントやれば、トーナメントリーダーが決まるじゃないか。
１００ｘ９９／２＝５０ｘ９９　高々５００でおわる。タコが実験室で
２日徹夜すれば済む。
0145１３２人目の素数さん2006/07/04(火) 06:36:35
ニクロム線グリッドアレイを作れば、瞬時に解決だな。
100C2=5000のポイントデータを入れて1回でやればいいだけ
0146１３２人目の素数さん2006/07/04(火) 06:46:31
俺さ、今更気づいたんだが、>>1って院生だな。
研究はじめて1年半ってとこで気づくべきだった。

プロの研究者ならともかく、院生ならイタい学生ですまされるかもな。
ただ、学会や修論審査会ではメタメタにされると思う・・・
その前に、指導教官が通してくれない・・・
0147１３２人目の素数さん2006/07/04(火) 06:52:03
>>144-145
ばかすぎ。そのアイディアで論文書きなよ。
0148１３２人目の素数さん2006/07/04(火) 07:00:07
>>140
そんなことをしなくても、もともと2点間の最短経路探索はO(n^2)なのだが
0149１３２人目の素数さん2006/07/04(火) 07:02:56
>>146
あーマスターの学生か。
アイディア盗まれるとか香ばしい発言が昔のおれにそっくりｗ
0150１３２人目の素数さん2006/07/04(火) 07:04:25
一般向けの解説書を読んで分かった気になっている
他人の論文をまったく読んでいない
他人には詳しい説明をもとめ，自分は一切まともな説明・回答をしない

あたりでアマチュアのｷﾓｵｻｰﾝだと思ってたんだが
試験とか言い始めたし学生か？
指導教官ｶﾜｲｿｽｗｗｗｗ
0151１３２人目の素数さん2006/07/04(火) 07:09:08
>>150
それにこんな時間まで起きてるしな。
どう見てもマスターの学生に決定だな。
どこの大学だろ？
今年の修士論文でTSP関係のは全部目を通そうｗｗｗｗｗｗ
0152１３２人目の素数さん2006/07/04(火) 07:15:00
>>1が痛すぎてｶﾜｲｿｽ
指導教官はもっとｶﾜｲｿｽ(´・ω・`)
0153>>1と指導教官2006/07/04(火) 07:25:26
指導教官「修論タイトルに巡回セールスマン問題とあるけど？」
>>1　「はい。巡回セールスマン問題です。」
指導教官「巡回セールスマン問題とは何のことですか？」
>>1　「最適化問題です。」
指導教官「え、最適化問題？」
>>1　「はい。最適化問題です。全ての点の最短巡回路を求めます。」
指導教官「・・・で、その巡回セールスマン問題はうちの研究室にどう役立つのかね？」
>>1　「はい。P=NPが証明できます。」
指導教官「いや、P=NPを信じている輩は誰もいません。それに学会ではトンデモ扱いだよね。」
>>1　「でも、私は確信してますよ。」
指導教官「いや、確信とかそういう問題じゃなくてだね・・・」
>>1　「クレイ研究所から100万以上もらえるんですよ。」
指導教官「ふざけないでください。それに100万って何だね。だいたい・・・」
>>1　「100万ドルです。$とも書きます。クレイ研究所というのは・・・」
指導教官「聞いてません。帰って下さい。」
>>1　「あれあれ？怒らせていいんですか？証明しますよ。P=NP。」
指導教官「いいですよ。証明してください。P=NPとやらを。それで満足したら帰って下さい。」
>>1　「運がよかったな。俺は英語が読めないみたいだ。」
指導教官「帰れよ。」
0154１３２人目の素数さん2006/07/04(火) 07:31:15
実際巡回セールなんかやっているのは、新聞勧誘とＮＨＫぐらいだろう。
ペプシ行員は巡回ベンデイグマシン問題と呼ぶ
0155１３２人目の素数さん2006/07/04(火) 07:33:52
>>154
普通は配送計画と呼ぶ。
0156１３２人目の素数さん2006/07/04(火) 07:35:41
>>153
ﾃﾗﾜﾛｽｗｗｗｗｗｗｗｗ
ｸｵﾘﾃｨ ﾀｶｽｗｗｗｗｗ
ガイドラインに登録してきたよ。
0157１３２人目の素数さん2006/07/04(火) 07:46:47
学生だとしたら学部生じゃね？
曲がりなりにも卒論を出した身なら「英語読めませんごめんなさい」は許されないでしょ
0158１３２人目の素数さん2006/07/04(火) 08:00:32
学部生だとしたら知識がなさ過ぎる。やっぱ勘違いしたおっさんぐらいじゃねーの？
0159１３２人目の素数さん2006/07/04(火) 08:02:20
2年間研究を続けたのに巡回セールスマン問題がNP完全である事すら知らなかったんだぜ
0160１３２人目の素数さん2006/07/04(火) 08:28:01
>>ぜんぜんＮＰ－ＨＡＲＤでないじゃないか？
>私はそう確信していますが断言はしません

NP-Hardであると数学的に証明されている事を知りながらもこういう発言をできる>>1は
稀に見る逸材だと思う
0161１３２人目の素数さん2006/07/04(火) 09:30:51
>>138

> 知っている。
> ただO(2^((log n)^2))と考えてよい箇所をO(n^2)と置き換えた箇所がある。

2^((log n)^2) = n^(log n) でもうすでに多項式時間ではない気が・・・
0162１３２人目の素数さん2006/07/04(火) 10:46:29
>>161
アンカミス。

>>138　×
>>122　○
0163１３２人目の素数さん2006/07/04(火) 11:51:14
>>157
落ちこぼれた院生ならそういうのいっぱいいる。
学部生なら2年も研究してない。
0164１３２人目の素数さん2006/07/04(火) 13:36:02
>>153
ﾃﾗﾜﾛｽ
0165１３２人目の素数さん2006/07/04(火) 16:22:15
>>161
2^((log n)^2) = n^(log n)
は正しいよ
両辺のlogをとるとどちらも
(log n)^2

2^(logn)=log(2^n)=n
0166１３２人目の素数さん2006/07/04(火) 19:56:38
>>165
y = 2^((log n)^2) としたら、
log y = (log n)^2
log log y = 2 log log n
にならないか？2^((log n)^2) = n^2って大丈夫か？
0167１３２人目の素数さん2006/07/04(火) 20:05:29
>>166

log ( 2^((log n)^2) ) = (log n)^2

log (n^2) = 2 log n

だから全然違うよな。というわけで O(n^7) って計算量もダウトか。
0168１３２人目の素数さん2006/07/04(火) 20:34:06
各ノードを糸電話でつないで、各糸の張りを変えておけば、キャーっと叫べば
各点に到達する音波をFFTにかけて通過ノードを判定できる。
0169１３２人目の素数さん2006/07/04(火) 20:41:10
たしかに、nが十分に大きければ
2^((log n)^2) < n^2 だから、オーダーの定義(定数倍の上界)からして
O(2^((log n)^2))をO(n^2)を書くのは間違いとはいえないが、
クイックソートのO(n logn)をO(n^2)と書くようなもので
誤解をまねくからやめた方がいいだろうな。

>>1は不勉強すぎる。院生でももう少しきちんとやれ。
0170１３２人目の素数さん2006/07/04(火) 20:42:30
>>168
だからそんなことしなくてもDijkstra法でO(nm)で判定可能。
しかし、2点間の最短路をTSPの巡回路の部分解に用いても
あまりよい結果は得られていない。
0171１３２人目の素数さん2006/07/04(火) 20:43:04
↑ごめん、O(m log n)だな。
0172１３２人目の素数さん2006/07/04(火) 20:51:30
１　各ノードにプリズムとポラロイドフィルムで通過するレーザーの偏向を微妙
に変え、各ノードに全ノードを通過して偏向面がある角度になった光に反応する
感知機をセットする。

２　最終点を除外して、その点に連結する(n-1)に感知気をつけてもう一度する。
ｎ－１晩目の最適点が出る。

３　２にもどる

ルートがわかる。
017312006/07/04(火) 20:52:06
議論になっているオーダーの箇所は実質ブルートフォースで解くための研究時のみの箇所。
そのプログラムの結果によっては、( 2^((log n)^2) )の部分は取れる。
最悪でもそうなるというだけで実際はもっと少なくなる。
0174１３２人目の素数さん2006/07/04(火) 20:58:37
>>116
> ずっとノーヒントでやってきたことなんだから多少無知でも許してくれよ。。。

>>1 の2年間の研究は徒労だったわけだが 2chにスレを建てたおかげでたった2年で済んだな
017512006/07/04(火) 20:58:46
>>141
頼まれたから無理に書いてあげたのにわがままだね。
たぶん結果が証明しますよ。
もし正しければ世界記録と並ぶか更新するかのどちらかになるからさ。
017612006/07/04(火) 21:00:10
>>174
仮に失敗でも近似アルゴリズムとしてはかなり優秀なものになりますよ。
0177１３２人目の素数さん2006/07/04(火) 21:00:59
近似度はどのくらいになるの？
0178１３２人目の素数さん2006/07/04(火) 21:03:35
>>1は近似度の存在を知らないに250ペリカ
017912006/07/04(火) 21:08:01
>>177
ランダムなデータを試して平均を取るのがいいが、都市数が20～30個程度なら確実に正確な解を出すと考えていい。
都市数は現在63個までしか試せないからまだ近似度についてはっきりしたことは言えない。(プログラムの書き換えが必要。)
制度は>>1以上になるから最悪でも2%程度と考えていいかもしれない。
0180１３２人目の素数さん2006/07/04(火) 21:09:08
>>175
>>176
調査してないのになぜ分かるｗｗｗｗ
指導教官がかわいそうだから、ちゃんと研究してやれよ。
0181１３２人目の素数さん2006/07/04(火) 21:10:02
>>179
たった63ｗｗｗｗｗｗｗｗｗｗｗｗ
concordeなら1000以上でも最適解出すよｗｗｗｗ
0182１３２人目の素数さん2006/07/04(火) 21:11:00
たった63で世界記録って m9（＾Д＾）ﾌﾟｷﾞｬｰ!!
018312006/07/04(火) 21:12:08
>>181
だから後で書き換えます！！
そうすればたぶん1000000個でも最適解になります！
0184１３２人目の素数さん2006/07/04(火) 21:12:15
だから近似アルゴリズムだとか言う前に近似度の定義を調べろよ・・・
0185１３２人目の素数さん2006/07/04(火) 21:12:44
>>179
ここ数年で一番笑った。
それでどうやってP=NPを示そうと？
ランダムなデータは構造を持たなくて解きにくいから、
TSPLIBのベンチマーク解きなよ。
018612006/07/04(火) 21:13:39
>>184
１０２％って書けばよかったのか？
0187１３２人目の素数さん2006/07/04(火) 21:13:56
>>183
だから、最適解だということをどうやって示すんだよ？
|N|=10^2 と |N|=10^7 を同列に考える意味が分からん。
018812006/07/04(火) 21:14:34
>>185
もちろんその予定。
0189１３２人目の素数さん2006/07/04(火) 21:14:45
>>186
あんたどこの大学？
0190１３２人目の素数さん2006/07/04(火) 21:16:04
>>188
P=NPをどうやって示すんだよ
たとえ|N|=10^10000が解けたってP=NPを示したことにはならないよ？
それと、どの論文と比べる気なんだよ。
019112006/07/04(火) 21:16:21
>>187
その質問に答えると勘のいい香具師(たぶんいないのだろうけど)にアルゴリズムを推察される可能性があるから言えない。
019212006/07/04(火) 21:17:21
>>189
個人情報流出阻止のため言えない。
0193１３２人目の素数さん2006/07/04(火) 21:17:47
>>191
誰もお前のアイディアなんか推察もしないし、盗みもしないが。
せいぜい学会で叩かれな。
019412006/07/04(火) 21:18:20
>>190
私の論文を読んだ第三者が証明します。
0195１３２人目の素数さん2006/07/04(火) 21:18:27
だんだん>>1が香ばしくなってきたな・・・ｗ
最初はまともな人かと思ってたのにガッカリだ。
0196１３２人目の素数さん2006/07/04(火) 21:19:01
>>194
比較しないと意味無いということが分からないのか？
0197１３２人目の素数さん2006/07/04(火) 21:19:56
>>195俺も。

他人に対しては「知恵を貸せ」
自分に対しては「アイディア盗まれる」

こりゃひでー自己中＆ダブスタ。
019812006/07/04(火) 21:19:58
>>193
これはかなり個人的にやっている研究です。
誰かと一緒にやってるわけではありません。
いい結果が出なければ学会にも行きません。
0199１３２人目の素数さん2006/07/04(火) 21:20:25
研究結果というのは公表して議論しないと無意味なんだがな。
学生でもそれぐらい分からないとやっていけんぞ。
0200１３２人目の素数さん2006/07/04(火) 21:21:19
>>197
同意。何をして欲しいのかわからん。

>>198
時間の無駄だからもうやめた方がいいよ。
020112006/07/04(火) 21:22:49
皆さん私を叩くことに専念してません？
0202１３２人目の素数さん2006/07/04(火) 21:22:52
英語も読めない。
論文も読めない。
比較もできない。
オーダーも知らない。
近似度もしらない。
学会にも行かない。

↑何がしたいのか不明すぎる。
0203１３２人目の素数さん2006/07/04(火) 21:23:06
素人の横レスですまないが、巡回セールスマン問題って、
ある経路が最適かどうかはすぐに判別できるの？
0204１３２人目の素数さん2006/07/04(火) 21:23:35
>>201
してない。やる気がないならもう帰れよ。
せめて従来の研究ぐらい調査して、他人の聞く耳持って。
020512006/07/04(火) 21:26:17
>>200
P=NPを支持しているだけで叩かれる。
そんなやつに多項式時間で解く方法を一緒に考えてもらうこと自体間違っていたと思ってるよ。
0206１３２人目の素数さん2006/07/04(火) 21:29:07
>>203
解を与えて、総費用がある閾値以下ってことしか分からない。
0207１３２人目の素数さん2006/07/04(火) 21:31:56
>>205
呆れた。叩かれてるのは君の研究に対する態度。
論文も読まない、比較もしない、基礎勉強もしないなんて
話にならないじゃん。
0208１３２人目の素数さん2006/07/04(火) 21:32:39
>>205
感情的な態度をやめて、まず真摯になれば？
0209１３２人目の素数さん2006/07/04(火) 21:33:29
ここで一念発起して基礎を学び、過去の論文を読み、比較をすれば
ずっといい段階に登れるよ。
0210１３２人目の素数さん2006/07/04(火) 21:36:10
>>201
真剣な最適化の研究者に対してそんなこといったら
殴られかねないよ。
君は非常に研究をなめた態度に見える。
0211１３２人目の素数さん2006/07/04(火) 21:36:22
まず近似アルゴリズムだというなら「近似アルゴリズム」であることを証明しろよ
近似アルゴリズムの定義は知ってるか？
021212006/07/04(火) 21:36:53
>>207
>>153あたり見ればP=NP発言だけで叩かれているとわかるだろう？
正直こんなんじゃ私もまともにレスする気が失せるよ。
私が下手に出ていればどんどんぶっ叩いて調子に乗ってな。
態度が悪いのはどっちなんだか・・・。
0213１３２人目の素数さん2006/07/04(火) 21:37:42
>>212
君はこれだけ真摯に諭されているのに何が不満なの？
0214１３２人目の素数さん2006/07/04(火) 21:38:42
>>212
P=NP以前に、研究するに値する基礎と態度が・・・
0215１３２人目の素数さん2006/07/04(火) 21:39:47
>>212
じゃ最初から一人で研究すればいいのに。
学会でもきちんと説明しなければ叩かれることは当たり前なんだよ。
0216１３２人目の素数さん2006/07/04(火) 21:42:39
>>212
http://www.amazon.co.jp/exec/obidos/ASIN/4320016173/
http://www.amazon.co.jp/exec/obidos/ASIN/4320016475/
http://www.amazon.co.jp/exec/obidos/ASIN/4254126174/
http://www.amazon.co.jp/exec/obidos/ASIN/4254275129/
http://www.amazon.co.jp/exec/obidos/ASIN/4320017862/
このあたりは読んだ？
まず、みんなあなたのアルゴリズムの近似度やオーダーを
真剣に聞いてくれてるのに、答えないから怒られてるんだよ。
まず、答えられるように基礎勉強してはいかがか？
021712006/07/04(火) 21:48:34
>>216
まったく同じ本は持っていない。
ネットワークに関してはオーム社の「ネットワークの基礎」という本は持っている。
組み合わせに関する本は残念ながら無い。
0218１３２人目の素数さん2006/07/04(火) 21:49:17
>>203
そっか、thanks。
021912006/07/04(火) 21:50:27
>>215
誰かのふとした発言が大きなヒントになる可能性が捨て切れなかった。
本当は一人で完成させる予定だった。
0220１３２人目の素数さん2006/07/04(火) 21:50:34
>>218は何が分かったのだろう……(´－｀)
0221１３２人目の素数さん2006/07/04(火) 21:51:33
人の脳を読む能力を悪用する奴を潰せ。さすればアイディア盗用などには悩まされずに済むであろう。
0222１３２人目の素数さん2006/07/04(火) 21:52:18
>>217
まず、組合せ最適化の本を読んだ方がいいと思う。
研究のアイディアがいっぱいのってるよ。

> ネットワークの基礎
誰の本？
0223203,2182006/07/04(火) 21:52:36
>>206
アンカーミスりました…
改めて、ありがと。
0224１３２人目の素数さん2006/07/04(火) 21:53:13
>>219
じゃあ、なおさら>>216が挙げた本を読むといいよ。
良書ばかり挙げてくれてるから。
0225１３２人目の素数さん2006/07/04(火) 21:54:59
>>223
追記すると、これを決定問題といって、
「yes」であることを多項式時間で判別できればクラスNPという。

「no」であることは列挙しないと分からないから、
とりあえず問題にしない。
TSPの決定問題は「巡回路の総距離がθ以下である」ってことな。
022612006/07/04(火) 21:57:00
>>221
昔考えたことがある。
ウイルスにサブリミナルメッセージを埋め込んで
そのウイルスに感染したＰＣは人の目にはあまりわからない程度に画素値を変えてメッセージを表示する。
その画面を見たものは催眠にかかってメッセージどおりの行動をする。と言った按配。

そのうち、こういった人間に感染するコンピュータウイルスが出ると俺は思っている。
0227１３２人目の素数さん2006/07/04(火) 21:58:38
>>226
そういうこと書くとみんなの呆れ具合が2^nのオーダーで膨れ上がると思う。
022812006/07/04(火) 22:00:34
>>222
競馬で負けたからもうしばらくしたら買うことにする。

ネットワークの基礎の著者は吉岡良雄という人のようだ。
0229１３２人目の素数さん2006/07/04(火) 22:01:46
もう諦めてバカキャラに方向転換したんじゃね？
0230１３２人目の素数さん2006/07/04(火) 22:02:57
>217
ないなら買え，読め

誰もP=NPだけで叩いていない．
研究に値しない行為をいさめているだけだ．

頼むから学会に来ないでくれ，みんなに迷惑だ．
学会運営ってのはボランティアなんだぞ．
君の勘違いに付き合ってるほど皆暇じゃないんだ．

みんな分かってないと思うかもしれんが，君の今までの発言だけで
君のアイデアは100%ダメだと分かる．断言する．
0231１３２人目の素数さん2006/07/04(火) 22:03:52
>>228
待ち行列やトラフィック解析の本じゃん。
TSPと全く関係ないよ・・・
一刻も早く組合せ最適化の本を買うべきだ。
0232１３２人目の素数さん2006/07/04(火) 22:05:08
>>228
せめて本読んでよ
図書館に行くとか

>>229
そうとしか思えない。
>>1抜きでまじめにTSP語ろうか。
023312006/07/04(火) 22:07:20
>>230
行かないって言ってるじゃないか。
0234１３２人目の素数さん2006/07/04(火) 22:08:45
>>233
じゃTSPもやめたらどうか。
0235１３２人目の素数さん2006/07/04(火) 22:09:22
>>233
なんでいうこと聞きたがらないの？
みんな的確なアドバイスくれてるぜ？
023612006/07/04(火) 22:09:42
>>234
なんで？
023712006/07/04(火) 22:11:06
>>235
>>230の言うことを聞いて学会に行かなければいいのだろ。
0238１３２人目の素数さん2006/07/04(火) 22:12:36
帰るわ。>>1にはほとほと呆れた。疲れた。
0239１３２人目の素数さん2006/07/04(火) 22:14:31
おい、P=NPが証明出来たぞ！！俺の脳内で！！
でもアイデアが盗まれると困るから学会発表とかしないからな！！！
0240１３２人目の素数さん2006/07/04(火) 22:16:44
>>239
人の脳を読む能力を悪用する奴が学会で発表します。
024112006/07/04(火) 22:17:12
>>239
すごいね。
発表は個人の自由だから拒むことは咎めないよ。
0242１３２人目の素数さん2006/07/04(火) 22:20:38
こうして数学板に雑談スレがまた一つ増えるのであった。
0243１３２人目の素数さん2006/07/04(火) 22:22:35
>>242
もう>>1は放置しような。
0244１３２人目の素数さん2006/07/04(火) 22:24:10
指導教官「修論タイトルに巡回セールスマン問題とあるけど？」
>>1　「はい。巡回セールスマン問題です。」
指導教官「巡回セールスマン問題とは何のことですか？」
>>1　「最適化問題です。」
指導教官「え、最適化問題？」
>>1　「はい。最適化問題です。全ての点の最短巡回路を求めます。」
指導教官「・・・で、その巡回セールスマン問題はうちの研究室にどう役立つのかね？」
>>1　「はい。P=NPが証明できます。」
指導教官「いや、P=NPを信じている輩は誰もいません。それに学会ではトンデモ扱いだよね。」
>>1　「でも、私は確信してますよ。」
指導教官「いや、確信とかそういう問題じゃなくてだね・・・」
>>1　「クレイ研究所から100万以上もらえるんですよ。」
指導教官「ふざけないでください。それに100万って何だね。だいたい・・・」
>>1　「100万ドルです。$とも書きます。クレイ研究所というのは・・・」
指導教官「聞いてません。帰って下さい。」
>>1　「あれあれ？怒らせていいんですか？証明しますよ。P=NP。」
指導教官「いいですよ。証明してください。P=NPとやらを。それで満足したら帰って下さい。」
>>1　「運がよかったな。俺は発表ができないみたいだ。」
指導教官「帰れよ。」
0245１３２人目の素数さん2006/07/04(火) 22:24:36
個人的には物理的な手法を用いた解法に興味があるんだが。
計算理論とは関係ないけどね。
0246１３２人目の素数さん2006/07/04(火) 22:25:22
スパゲティアルゴリズムとか始めて見た時は笑ったな
0247１３２人目の素数さん2006/07/04(火) 22:30:45
>>246どんなの？

（沢山のスパゲティーを都市に通して最短のものを選ぶ、とかかなあ…）
0248１３２人目の素数さん2006/07/04(火) 22:32:16
>>245
解法としちゃ面白いが、性能はいまいちだな。
むしろ、風洞実験みたいに実物を使わなくても
よくなったというのが、現代の進歩やし。
0249１３２人目の素数さん2006/07/04(火) 22:33:28
ここの>>1を見て、コミュニケーション能力の低い奴は
研究もできないということがよく分かった。
0250１３２人目の素数さん2006/07/04(火) 22:38:29
やたら進んでたんで100レス分ぐらいの1の行動をまとめて
0251１３２人目の素数さん2006/07/04(火) 22:40:33
>>250
>>239
0252１３２人目の素数さん2006/07/04(火) 22:41:35
>>250
オーダーや近似度を知らず、本も読んでないことが発覚し
みんなから注意されたら逆ギレ。
学会に行かないとか何とか宣って帰った。
0253１３２人目の素数さん2006/07/04(火) 22:41:51
特定の経路だけで最適回を探すアルゴリズムより、n!の経路全てを計算してしまえばいい。
ハードが遅いからソフトにこりたくなるけど・・・n!の演算を数秒でするハードを開発する
ほうが簡単だよ。シメトリックな距離マトリックスをほりこんで、パーミュテーションで
データを読んで足し算して、短いやつだけ残してゆく。Cn-1にnC2個の距離データを任意の間に
ほりこむだけ。それかain足すだけ。nC2データをいれかえるのは、Cn-1のaiとanを入れ替えて
Cn-1を計算して、aiを足すだけ。これはパラレルでできる。
0254１３２人目の素数さん2006/07/04(火) 22:44:35
>>253
>>43
0255１３２人目の素数さん2006/07/04(火) 22:50:39
100億年かかるのなら10000億倍にクロックを上げるか、並列チップをいれるだけ。
0256１３２人目の素数さん2006/07/04(火) 22:54:03
そんなゴリ押し解法で済ますならこんなスレいらない
0257１３２人目の素数さん2006/07/04(火) 22:57:07
10000THzのPCはきっと身体に悪いとおもうよ。電磁波漏れでミデイアムレアになる？
クオークは破裂してクオンタムリープする？
0258１３２人目の素数さん2006/07/04(火) 22:58:37
>>255
なるほど、現在の技術で100億(=10^10)年かかる問題でもそれなら解決できますね！
では現在の技術で 10^140 年ほどかかる問題だったらどうしましょうか。
0259１３２人目の素数さん2006/07/04(火) 23:01:27
>>258
自己修復機能を備えた計算機とタイムカプセルを作って、延々と計算してもらいましょう。
きっと未来の知的生命体が計算結果を解読してくれます。
0260１３２人目の素数さん2006/07/04(火) 23:06:03
その前に，物理的に信号の速度は光速を超えられないわけでな．
10000億倍にクロックを上げるには，現在の計算機ストラクチャーを
根本から覆すようなアイデアが必要なのよ．
ハード開発の方が簡単なんて幻想．

ちなみに10000億倍なんて100!にくらべりゃはるかに小さい．
計算してみ．指数関数の暴力の前には無力．
0261１３２人目の素数さん2006/07/04(火) 23:12:42
n(n-1)個の距離データaijからn個を足して最短を見つけるだけ。
組み合わせはn! Aはシンメトリーでaii=0
100!=(e^2log10)!=(e^8)!
もしaijがΦなら,iでも入れておけばいい。iを含む経路はオミットされる。

0262１３２人目の素数さん2006/07/04(火) 23:12:50
我々の脳のクロックが10000億分の一になれば相対的に解決。
0263１３２人目の素数さん2006/07/04(火) 23:15:36
>>262
どうして人間が、もっと身体も脳もデカくて、主観時間の長い生物じゃなかったのか、と思うことがあるよ。
そうすれば知識ももっと詰め込めただろうし、
ナノテクどころかマイクロテクぐらいでも十分超技術だったろうし、
光速の壁だってずっとずっと遠かっただろうに、と。
0264１３２人目の素数さん2006/07/04(火) 23:16:44
CPUに微小なブラックホール素子を入れ込めば、外の時間は止まったまま
何兆年でも計算して、答えをクオンタムホールからタングルドペアで
お告げしてくれるPCができるかも？
0265１３２人目の素数さん2006/07/04(火) 23:19:00
>>264
そのチップはとんでもなく重そうだなｗ
0266１３２人目の素数さん2006/07/04(火) 23:21:06
おぬしは毎年数千個もの微小ブラックホールが地球のコアを素通りしている
天文学的な事実をしらないのかな？
0267１３２人目の素数さん2006/07/04(火) 23:23:36
素通りしてるから大丈夫なんだろ。
固定させようとしたらどれほどのエネルギーを要するか……
エネルギーを消費しないようにうまいこと固定できたら、
それは作用反作用で外装（チップ）の慣性質量として跳ね返ってくるよね。
0268１３２人目の素数さん2006/07/04(火) 23:28:24
>>263
それでもその人間も超技術であるマイクロテクに満足せず、
ナノテクに到達し、その先を目指すんだろうな。
0269１３２人目の素数さん2006/07/04(火) 23:28:53
微小ブラックホールはハイゼンベルグの不確定性原理の許す時間だけ
生成消滅すれば、計算するときだけ発生する。重力波を増幅させる
マイクロ波で使うような共振デバイスが組み込まれている？
0270１３２人目の素数さん2006/07/04(火) 23:29:41
>>264
それって時間が止まるのは素子の方じゃないか？
0271１３２人目の素数さん2006/07/04(火) 23:33:40
マイクロ微粒子は肺の中でどんな副作用するかはこれからのフィールド
実験でわかるんじゃないかな？
0272１３２人目の素数さん2006/07/04(火) 23:37:09
おまえらほか行け。
0273１３２人目の素数さん2006/07/04(火) 23:39:39
ブッラクホールでは時空がひっくり返っている。問題を解こうとおもう前に
回答が紙に書かれてしまう・・・それを外にクオンタムホールとタングルドペアで
通信するか、別の微小ワームホールから電磁波で伝える。
0274１３２人目の素数さん2006/07/04(火) 23:41:27
だから、ＤＯＶマシンじゃ100億年かかるってゆうからＱＴＭマシンを
妄想してるんだよ。
0275１３２人目の素数さん2006/07/04(火) 23:48:01
最強の計算機は人間の妄想だな。
なんでも擬似解にたどり着く。
0276１３２人目の素数さん2006/07/04(火) 23:51:58
なんでこんな香ばしい話してるの？
SF板かよ。
0277１３２人目の素数さん2006/07/04(火) 23:54:28
雑談スレッドですから。
0278１３２人目の素数さん2006/07/04(火) 23:55:54
n個のホールを持つ、複素多様体を考えるとか？各ホールとの距離を与えてやる。
その中で全てのホールを1回だけ通る経路積分を考えるとか？
0279１３２人目の素数さん2006/07/04(火) 23:57:44
>>275
その最たるモノが>>1の頭脳
0280１３２人目の素数さん2006/07/05(水) 00:05:00
ＰＮＰ問題ってアキレスの亀より巧妙なトンでも一派じゃないかな？
お、それはＮＰ問題じゃないの・・・っていわれたら・・・一瞬引きたくなるから・・・
ちょっと昔の相対論者みたいな扱い？
0281１３２人目の素数さん2006/07/05(水) 00:31:46
>>280
巧妙でもなんでもない、ただのトンデモだろ。
>>153は>>1の愚かさをうまく表してると思う。
0282１３２人目の素数さん2006/07/05(水) 00:39:38
Ｐ＝ＮＰはＮＰと証明された問題がＰで解けたら、反例になるから、その時点で
サドンデスですね。
0283１３２人目の素数さん2006/07/05(水) 00:53:28
>>282
それを言ったら、x^n+y^n = z^n (n>=3)での整数解x,y,zが
1つでも見つかったら判例になるからサドンデスとか
いくらでもいえるからｗ
0284１３２人目の素数さん2006/07/05(水) 00:59:04
>>1はついに逃げ帰ったか。
0285１３２人目の素数さん2006/07/05(水) 21:39:28
あきれて帰ってやっただけニダ。逃げ帰ったとは決して認めないニダ。
0286１３２人目の素数さん2006/07/05(水) 22:11:02
やっぱ逃げたんだな。修論もこのぶんじゃ通らなそう
0287１３２人目の素数さん2006/07/05(水) 22:12:17
>>1
は撃沈？
028812006/07/05(水) 22:30:34
帰れとか言っておいて私がいなければまともに議論もできないのですか？
大体本気で巡回セールスマン問題をまともに解こうともしないでただ誰かの考えた理論をひけらかしているだけの人に
研究できないとか言われる筋合いはありませんよ。

かつて物理学者達がロータリーエンジンの実用化は無理だと断言し、誰もが無理だと思っていたのに
今、ちゃんとRX-7が走っているじゃないですか？
それともこんなのはどうだ？かつて物理学者達がＣＰＵのクロック周波数が300MHzを超えると太陽熱ぐらいに発熱するため
300Mhzを超えられないとほざいていた。誰もがそれを信じていた。
今あなたが使っているＣＰＵは何GHzですか？ｗ

わからない問題が出てきたら敵前逃亡ですか？
そして、誰かがその問題を解いたらその、解き方だけ盗んで、その解き方を知らない人に
「お前そんなのも知らないのか、アホだな」とか言って見下すんでしょうね。
虎の威を狩る狐だね。
いや、もっと卑怯だ。
虎の牙を盗む溝鼠が妥当だろう。

私はP=NPを信じて堂々と戦いますよ。逃げも隠れもしません。
0289１３２人目の素数さん2006/07/05(水) 22:43:26
だから信じてる事自体よりも、こちらが普通に質問したりしてるのに
まともに応じなかったりするのがぺけなわけで・・・。別人かも知れんけど一応。
0290１３２人目の素数さん2006/07/05(水) 22:46:57
>>288
下手かな。偽物臭いよ。

本物だとしたら信じて貰えるようにきちんと説明するのが義務だ。
勉強したくない、言いたくない、意見は聞きたくない、
じゃどうしようもないな。
0291１３２人目の素数さん2006/07/05(水) 22:47:42
>>288
>P=NPを信じて堂々と戦いますよ
ｱｯｿ
0292１３２人目の素数さん2006/07/05(水) 22:48:18
>>288
その「無理だと断言した」資料を明示してくれないか？
某の理由から現在の技術の延長では壁に突き当たる、という程度の話ではないか。

先人の知恵を蔑ろにして車輪の再発明をしても、
分不相応な難問に挑戦して玉砕しても
誰もほめてはくれないよ。

もちろん突き当たった壁を突破する方法を見つけられたら
相応の報酬と賞賛が得られるだろうね。
0293１３２人目の素数さん2006/07/05(水) 22:50:47
>>1は研究のなんたるか？を全然理解してないのがダメなところ。
>>292がいうように、今の時代にノーヒントで石器・土器を発明しました！
っていっても誰も認めてくれないのと同じだ。
たとえどんな素晴らしい土器だったとしても。
0294１３２人目の素数さん2006/07/05(水) 22:54:29
>>1
は撃沈？
029512006/07/05(水) 22:59:09
>>290
説明したじゃないか？>>138に。
逆切れされたけどな。

>>292
プロジェクトＸ観ろ。

>>293
石器はもうすでに発明されているだろ？
巡回セールスマン問題は未知なる領域なのだ。
既知のことを知っているだけでは解けないもの。
自力で解くためのセンスと根性は必要だ。
既知の物を検証するだけの研究なら君の言っていることで十分だよ。
ただ君は未知なる物を研究するということをまったくわかっていない。
0296１３２人目の素数さん2006/07/05(水) 22:59:56
>>288
敗北宣言にしか聞こえないんだけど……
029712006/07/05(水) 23:01:08
>>296
溝鼠はさっさとドブに帰りなさい。
0298１３２人目の素数さん2006/07/05(水) 23:05:08
>>1
近似アルゴリズムの定義は調べたか？
近似度の定義は調べたか？
NP-Hardの定義は調べたか？
0299１３２人目の素数さん2006/07/05(水) 23:08:25
素数の判定アルゴリズム体操のほうが・・・・
掛け算は簡単なのに、割り算は・・・おそるべし、多価函数
足し算は簡単だけど、分割数は・・・・これまた・・・
フラクタルやカオスと同じトリックなんだね
n^1000をすらすら表記できるアルゴリズムすらないのですね。
030012006/07/05(水) 23:10:55
>>298
近似度・近似アルゴリズムの定義は調べた。
ＮＰ-Hardの説明は納得がいかない点がある。

近似度・近似アルゴリズムについて定義だけ知っても意味が無い。
それをどのように利用できるかが問題。
0301１３２人目の素数さん2006/07/05(水) 23:13:11
>>295
それが説明ではない。アウトラインという。
0302１３２人目の素数さん2006/07/05(水) 23:14:00
>>299
素数判定は 2002 年に P になった。
0303１３２人目の素数さん2006/07/05(水) 23:14:07
>>300
ひょっとして、P=NPもちゃんと知らないんじゃないか？
定義だけ知っても意味無いという主張は正しいが、
定義をきちんと知らなければ考えること自体ができないだろ。
030412006/07/05(水) 23:15:32
>>301
>>126が概略だけでいいって言ったから要望通りにしただけだ。
0305１３２人目の素数さん2006/07/05(水) 23:17:28
>>295
> 石器はもうすでに発明されているだろ？
> 巡回セールスマン問題は未知なる領域なのだ。
同じさ。
TSPだってすでに発明された優秀なアルゴリズムがいっぱいある。
君が同じ物を作ってしまわないとなぜいいきれるだろうか？
0306１３２人目の素数さん2006/07/05(水) 23:19:20
>>304
標準的な書き方をしなければ、ただの落書きなんだが。
せめてPDFで配布してくれよ。
そうしたらいくらでも問題点を指摘してあげるから。

2chに落書きしてるまえに1日待つからちゃんとしたペーパー作って。
0307１３２人目の素数さん2006/07/05(水) 23:22:55
アルゴリズムは無意識のうちに誰かのマクロを使ってしまい、あとで著作権
問題になるから、やらすんだったら、ＰＣを見たこともない、僻地の学生を
密室に入れて開発させるしかない。論文はいっさい見せない。
メーカーＳＥの常識です。
0308１３２人目の素数さん2006/07/05(水) 23:24:14
>>304
何で君はわざと標準と違うことをするの？
標準でないことが個性だと思ってるのかも知れないが勘違いだぞ。

サッカーだってオフサイドのパスを手で掴んで
ゴールへダイブしたってダメでしょ？
0309１３２人目の素数さん2006/07/05(水) 23:25:00
>>307
で、シンドラーみたいになるわけだ。
031012006/07/05(水) 23:25:25
>>305
それを調べるために巡回セールスマン問題への招待を買った。
そこには巡回セールスマン問題に関する論文は100以上あると書かれていたが、
それは手法の数ではなく既知の手法の検証をしただけのものもあるだろう。
私の手法は図示すれば非常にシンプルで優秀だ。
巡回セールスマン問題への招待には私のアルゴリズムよりも明らかに複雑で性能が低いものもが多数ある。
もしも私と同じ手法があるのなら、巡回セールスマン問題への招待に紹介されていてもおかしくない。
031112006/07/05(水) 23:27:59
>>308
サッカーボールを手でつかんでゴールに突っ込む人もいなければラグビーも生まれない。
常識にとらわれているから巡回セールスマン問題もいまだに解けないんだ。
0312１３２人目の素数さん2006/07/05(水) 23:28:20
こういう人たちって、何の理由があって啓蒙本を読む以外のことをしようとしないのかな。
0313１３２人目の素数さん2006/07/05(水) 23:32:48
１００！通りあるんだから統計的手法で２０００経路をサンプリングして、
分布を見れば、あとはモンテカロで最適経路が・・・・
031412006/07/05(水) 23:33:31
>>308
ついでにあなたの標準というものを提示してもらえますか？
標準なんていくらでもあるのですよ。
原稿用紙に書くのもA4の紙に印刷するのもTCPで送るのもUDPで送るのも標準です。
私の説明も十分標準です。
0315１３２人目の素数さん2006/07/05(水) 23:35:44
>>314
！！！？
標準といったらPDFかポストスクリプトだと思うんだけど……
本当に「研究」してるの？？
0316１３２人目の素数さん2006/07/05(水) 23:35:45
>>310
あの本は著者曰く「シャレで書いた」本なんだよ。
論文も全然読んでないだろｗ
君が専門書に感じているなら修行が足りないんだな。
>>138の「概要もどき」もモロフレームワークになったりするし・・・

>>312
>>1が「ノーヒントでやったからほめてくれ」とか言ってたが、
最近のガキは見ないでやることが偉いと教育されてるんだろうな。
実績＜＜プロセス　というゆとり教育で育ってるから。
0317１３２人目の素数さん2006/07/05(水) 23:36:15
>>314
つ 論文
0318１３２人目の素数さん2006/07/05(水) 23:37:12
>>316
標準が「没個性」だと勘違いしてるわけか。
まず思想からたたき直す必要があるな。ﾏﾝﾄﾞｸｾ
0319１３２人目の素数さん2006/07/05(水) 23:37:29
ラテイスーガスのアルゴリズムもロスアラモスやフランス軍で研究されているけど、
専用ハードの開発も同時進行でやられた。ソフトだけじゃ片手落ちだよ。
0320１３２人目の素数さん2006/07/05(水) 23:38:18
>>1は本当に論文というものを読んだことがないらしいな……
0321１３２人目の素数さん2006/07/05(水) 23:38:58
>>1
揚げ足ばっかとって(とれてないが)恥ずかしくないのかね？
ココロ入れ替えて勉強しては如何か？
032212006/07/05(水) 23:42:48
>>316
>「ノーヒントでやったからほめてくれ」とか言ってたが
捏造するなよドブ鼠。
その「ノーヒントでやったからほめてくれ」とか言った資料を明示してくれないか？
0323１３２人目の素数さん2006/07/05(水) 23:44:48
>>116確かに「ほめてくれ」とは言って無いな。
032412006/07/05(水) 23:44:55
>>321
勉強はしてるさ。
ただ巡回セールスマン問題だけに時間をとってられない時期なのだよ。
0325１３２人目の素数さん2006/07/05(水) 23:45:36
なんか「誉める」って部分がカチンときたらしい
0326１３２人目の素数さん2006/07/05(水) 23:46:05
>>322
> ずっとノーヒントでやってきたことなんだから多少無知でも許してくれよ。。。
じゃこれはどういう意味なんだ？
免罪符だったら同じ事なんだが。
0327１３２人目の素数さん2006/07/05(水) 23:46:44
>>324
ハッキング対策のスタンドアロン化はもうやったの？
0328１３２人目の素数さん2006/07/05(水) 23:46:55
>>322
君もその「研究」とやらの資料を明示してはどうか？
揚げ足取りしかできないんですか？
0329１３２人目の素数さん2006/07/05(水) 23:47:27
>>326
>>325
0330１３２人目の素数さん2006/07/05(水) 23:49:11
>>329
なんか>>1って感情むき出しで恥ずかしいな。
M2ってことは最低でも23歳なはずだが、
まるで小学生以下のEQだな。
033112006/07/05(水) 23:49:28
>>326
日本語も読めないのか？死ねよ。
033212006/07/05(水) 23:50:14
>>328
以前明示する条件を示したはず。
0333１３２人目の素数さん2006/07/05(水) 23:50:56
>>331
君の文章や表現は標準から外れてるから
行間が読めないのだ。
君の指導教官や両親ではないから、心のケアまでは見切れないしな。
033412006/07/05(水) 23:51:01
>>327
した。
0335１３２人目の素数さん2006/07/05(水) 23:52:11
>>332
君にアドバイスする最低の必要条件が
研究内容の説明のはずだが。
一体何しにここへ来てるわけ？
0336１３２人目の素数さん2006/07/05(水) 23:54:03
>>1
作法に従えないなら研究する資格はないですよ。
研究者はいそがしいので、効率的に他人の考え方を
理解するために編み出した方法が「論文の標準化」なのです。
033712006/07/05(水) 23:54:23
>>335
以前説明したはず。
0338１３２人目の素数さん2006/07/05(水) 23:55:04
>>334
おめ。
誰にも秘密ってことは、知人や教官にも話してないの？
0339１３２人目の素数さん2006/07/05(水) 23:55:07
>>337
以前と今は明らかに理由が違うよね。
君は今日TSPについて1度でも話したかな？
0340１３２人目の素数さん2006/07/05(水) 23:56:26
>>332
>>337
研究成果の場で質問されて「以前答えた」というのは
最悪の質疑応答だよ。
たぶん、次から門前払いだな。
034112006/07/05(水) 23:56:31
>>339
ここに来ている理由を説明したはず。ってこと
0342１３２人目の素数さん2006/07/05(水) 23:58:51
>>341
>>219でいいの？
研究内容を説明しないとヒントは出せない、と言われてるなら
来る理由はないよね。しかも、君がTSPの話題を全く出さないのは
なんでなのかな？
0343１３２人目の素数さん2006/07/05(水) 23:59:46
先輩にバカスレがあるからと聞いて来てみれば・・・ｗ

これはひどいインターネッツですね
034412006/07/06(木) 00:02:01
>>342
>>1は放置してＴＳＰの話を進めるという意見が複数でたのでＲＯＭってたら
>>1が来るだの来ないだの>>1の話ばかりになったので勢いを取り戻すためにやむ終えず書いた。
0345１３２人目の素数さん2006/07/06(木) 00:03:35
>>344
じゃあTSPの話題をどうぞ

--------------　開始 -------------------
034612006/07/06(木) 00:03:37
>>343
つまりこの中にその先輩がいる可能性もあるということですね。
おもしろい。
0347１３２人目の素数さん2006/07/06(木) 00:03:57
現状，50程度のサイズの問題もまともに解けない，糞のような学部生並みのプログラムしか書けていない人間が
なにを偉そうに言っているのかねえ

ことばの定義もしらなかったり，
たかだか学部生レベルの解説書をあたかも大論文であるかのように何度も引き合いに出してみたりといった
「研究」とよぶにはおこがましい態度はなんとかならんかね
0348１３２人目の素数さん2006/07/06(木) 00:04:18
>>346
TSPはどうしたんだい？また逃げるのか？
0349１３２人目の素数さん2006/07/06(木) 00:05:35
>>347
修論落ちないとだめかもね。

まずは言葉の定義から復習しようか。
クラスP、クラスNP、NP完全、NP困難

このあたりからいこうか？
0350１３２人目の素数さん2006/07/06(木) 00:07:54
>>333
指導教官だってそんなとこまで見きれんぞ・・・。
035112006/07/06(木) 00:08:58
それではこれまでの議論の結果を整理しよう。

わかったこと
・巡回セールスマン問題はP=NPの可能性がある。
・>>1のアルゴリズムは未発見の可能性が高い。
・NP-Hardで困難な問題であり挑戦するものは勇敢である。

これからの議題
・巡回セールスマン問題を多項式時間で解く方法を考える。
・それが無理ならば多項式時間では絶対に解けないことの証明を考える。

取り合えずこんな門でいいな。
0352１３２人目の素数さん2006/07/06(木) 00:09:08
>>1
は撃沈？
0353１３２人目の素数さん2006/07/06(木) 00:11:11
>>351
・・・
根拠を書かないといけないのは小学生でも分かるよね。
禅問答や精神論語ってるんじゃないんだよ。

>>349に答えれ。
0354１３２人目の素数さん2006/07/06(木) 00:11:56
>>351
君は>>349に挙げられてることばの定義が
しっかりしてないんだから先走りすぎ。
0355１３２人目の素数さん2006/07/06(木) 00:12:36
>>351
もうギャグだなｗ
勝手に議題を作るなよ
0356１３２人目の素数さん2006/07/06(木) 00:15:04
わかったこと
・正直>1はやる気も能力もない可能性が高い。

これからの議題
・秘密主義って言ったって話にならんほど秘密にしても仕方ないという事をいかに理解させるか。
・とりあえず、受け答えくらいはまともにして貰いたい。

これちゃかしではあるけど、本当に思ってることだから。
0357１３２人目の素数さん2006/07/06(木) 00:15:27
>>351
わかったこと
・宇宙はメタ宇宙の素粒子の1つの可能性がある
・私の考えは未発見の可能性が高い
・宇宙論は困難であり挑戦するものは勇敢である

これからの課題
・メタ宇宙が存在することを確かめる方法を考える
・それが無理ならばメタ宇宙が存在しないことを確かめる方法を考える

という有名なニセ科学と同じなんですが。
反証不能なものを科学とは呼びません。あしからず。
035812006/07/06(木) 00:16:13
>>353
>>347が復習するんだろ？
俺は今ある病原体に犯されているからもう寝る。
大事な作業もできなかったしな。
私がいなくても議論くらいできることを示してみなよ。
0359１３２人目の素数さん2006/07/06(木) 00:17:10
>>351
×　　＞これまでの議論の結果
○　　私の意見

他人との意見交換を通じて得られた共通見解なのかそうでないのかは
区別しようねー

修論で困るよボク
0360１３２人目の素数さん2006/07/06(木) 00:17:56
>>358
>>243へ戻って無限ループ

まず話を振った人間（つまりスレを立てた>>1)が
能力があることを示すのは当然。
それとも理解不足を指摘されるのが怖いか？
0361１３２人目の素数さん2006/07/06(木) 00:18:05
>>358
自分のアイディアが盗まれるから嫌です＞＜
0362１３２人目の素数さん2006/07/06(木) 00:19:19
>>358
いやいや意見がほしいのはキミでしょ＾＾；
なぜキミのいないところで他人がTSPについてギロンしなきゃいけないの？ｗｗ
いまは>>1か>>1もどきが痛くておもしろいからレスがあるけど
そうじゃなきゃこんな糞スレdat落ちするだけだよｗ
0363１３２人目の素数さん2006/07/06(木) 00:20:15
ある病原体ってなんだそりゃｗｗｗ
「風邪引いたので寝ます」とか言えば良いだろ。

議論、ねえ。君抜きで君の理論の何を議論するの？
（巡回セールスマン問題についての議論じゃなくて、君理論についての議論だよね。このスレの趣旨って。）
0364１３２人目の素数さん2006/07/06(木) 00:21:46
>>1も交えて、リアルでTSPオフ会やろうか。
議論が活発になれば楽しそうだ。
0365１３２人目の素数さん2006/07/06(木) 00:23:07
>>364
そのためには>>1の住んでいる地域が。
都市部だといいけど…
0366１３２人目の素数さん2006/07/06(木) 00:24:12
>>364
>>365
マジでやるなら、久保さん知り合いだから声かけるけど？
0367１３２人目の素数さん2006/07/06(木) 00:27:19
それはちょっと申し訳ない気もする
面白そうではあるが
0368１３２人目の素数さん2006/07/06(木) 00:27:32
>1がかえって来ないんじゃ・・・。
0369１３２人目の素数さん2006/07/06(木) 00:28:07
>>366
今の>>1では失礼すぎるのでは・・・
俺は東京なんですが、行ける場所なら参加したいですね。
0370１３２人目の素数さん2006/07/06(木) 00:31:05
おお！結構賛同者がいて嬉しい！
しかも久保さんまで呼べるなんて盛り上がるなぁ。
>>1がいないと意味ないから予定を聞きたいところ。
0371１３２人目の素数さん2006/07/06(木) 00:37:01
スレ関係なしに数板，物板，マ板，ム板あたりに招集かけてオフ会やるのも面白そう。
都内か、遠くて関東くらいでやるなら僕も行ってみたいな。
0372１３２人目の素数さん2006/07/06(木) 00:38:50
もちろんOFF板にも招集かけろよ。
0373１３２人目の素数さん2006/07/06(木) 00:42:43
>>1
はまだ～？
0374１３２人目の素数さん2006/07/06(木) 00:46:35
今日は寝たんだろ
取り合えず明日>>1が来たら再開かな
0375１３２人目の素数さん2006/07/06(木) 00:47:13
>>373
病原菌に冒されて寝てるみたいだから、
明日また改めてオフ会に誘ってみよう。
0376１３２人目の素数さん2006/07/06(木) 12:42:58
>366
非常に忙しい人なのでやめた方が良いと思われ．
超高級ワインを用意すれば参加してくれるかも知れないけど･･･
0377１３２人目の素数さん2006/07/06(木) 15:18:39
>>376
じゃあ、海洋大まで出向いてゼミやろうか？
0378１３２人目の素数さん2006/07/06(木) 15:29:30
>>351を見ると>>1はこれから計算理論の勉強を始めるようだからあと数年待ってやったほうががいい
0379１３２人目の素数さん2006/07/06(木) 15:35:26
今までにどんなアルゴリズムが発見されているのかを調べてないのに
「>>1のアルゴリズムは未発見の可能性が高い。」とか発言出来る辺りが凄いな
0380１３２人目の素数さん2006/07/06(木) 17:17:44
多面体として考えて、その中で体積が最小なのが最短経路ですよね。
どの多面体が最小なのか？
これは、ある理論ですぐ探せる。
0381１３２人目の素数さん2006/07/06(木) 18:32:48
>>380
まずは一行目についてよく考えたほうが良いと思うよ。平面グラフの場合とかね
0382１３２人目の素数さん2006/07/06(木) 19:02:45
>>380
一見すぐ探せるように見えて難しいのが組合せ論。
TSPだって、点の数が少なけりゃ楽勝なんだよ。
多面体だって凸ならともかく、凹を理論的に解析する
手段は皆無に近い。

とりあえず、>>1のゼミ予定待ちか。
0383１３２人目の素数さん2006/07/06(木) 19:34:25
ポアンカレがヒント！
0384１３２人目の素数さん2006/07/06(木) 20:03:55
結局は、巡回セールスマン問題 ＝ ポアンカレ だったのです！
0385１３２人目の素数さん2006/07/06(木) 21:59:16
また、コンビ屋ｖｓハード屋の戦いか。
アナログパソコンを使えばいちころじゃないか
0386１３２人目の素数さん2006/07/06(木) 22:15:06
100!個の足し算が有限時間でできればいいだけじゃないか。
ウイルスのＤＮＡに組み込んで1時間ぐらいほっておけばシャッフルしてすぐ
100!個になる。あとは最短ＤＮＡをもつやつをスクリーニングすればいい。
0387１３２人目の素数さん2006/07/06(木) 22:36:59
へえ、ウイルスにDNAを仕込むと一時間で
宇宙にある全電子数の二乗にまで増殖するんだ。
038812006/07/06(木) 22:43:14
巡回セールスマン問題を多項式時間で解くための新たな可能性として暗号技術を挙げたい。
基本的な現代暗号を鍵なしで解くには多くのものはブルート・フォース・アタックで解く場合にはO(2^n)
となり多項式時間では解けない。これは巡回セールスマン問題にも言えることである。
しかし、暗号は鍵さえあればほとんどのものはO(n)となり多項式時間で解ける。
もしも巡回セールスマン問題が暗号のように鍵さえあれば解ける問題なのならば暗号技術の適用というものは
巡回セールスマン問題を多項式時間で解こうとする上で大きなヒントになる。
またその逆に巡回セール万問題の近似解法を暗号文に適用できるならば、またある可能性がある。

TSP・・・近似解法の場合要素数が多いほど誤差が出やすく、また要素数が少ない場合には誤差がまずでない。
暗号文・・・暗号文の特性などから分析する場合暗号文が長いほど解き易く、暗号文が短ければ解読はほぼ不可能。

「多項式時間で解けない」というところは一致するが上記に挙げた特性はまったく逆なのである。
つまりこういうことだ。
短い暗号文には巡回セールスマン問題の近似解法を適用し、
要素数の多いＴＳＰには暗号解読の技術を応用することで
両者の計算量を大幅に削減できる可能性があるのだ。（まあ暗号解読の方の可能性は希薄だと自分でも思っているのだが。）

オフ会か。何かの罠の様な気もするのだが本気なら参加してもいいぞ。
ただし私の住居で始めるようなことなら却下。
私の理想としてはパソコン持って会場？についたら人数分データのコピーと資料の印刷ができる環境があるといい。(地球環境の保護のため)
何も無理に開催することも無いが、開催すると意外と面白い展開になるかも。
額にしわ寄せながら厳格に大激論するというよりは、自由奔放に２ちゃんねるが５０％入っているくらいのブレーンストーミングがいいな。
0389１３２人目の素数さん2006/07/06(木) 22:50:20
まさか暗号文が十分長ければ
簡単に解読できる、と思ってるの？
0390１３２人目の素数さん2006/07/06(木) 22:50:35
>もしも巡回セールスマン問題が暗号のように鍵さえあれば解ける問題なのならば
だからNP問題の定義を調べろよ
039112006/07/06(木) 22:53:13
>>389
簡単ではない。
だが短い物に比べれば非常にとき易い事は確か。
0392１３２人目の素数さん2006/07/06(木) 22:53:29
人のＤＮＡは130万個で、1回シャッフルするのに１６年以上かかる。
でも同じＤＮＡの人がいないのは、過去６０万年シャッフルしてきた。
039312006/07/06(木) 22:54:03
悪いが今日はこれで失礼する。
0394１３２人目の素数さん2006/07/06(木) 22:54:49
さすがにここまで何も理解していないとは思わなかった…
0395１３２人目の素数さん2006/07/06(木) 22:57:04
よく知らないんなら無理して暗号の話を持ち出すことないんじゃないの？
0396１３２人目の素数さん2006/07/06(木) 22:59:05
シーザー暗号からの類推か。
0397１３２人目の素数さん2006/07/06(木) 23:11:05
kingにはついていけない話だな
0398１３２人目の素数さん2006/07/06(木) 23:20:18
召喚すんなｗ
0399１３２人目の素数さん2006/07/07(金) 01:10:42
>>388
ゼミは別に罠じゃないよ。
普通にどこかの大学の一室か、店を借りてやるつもり。
予定を教えてね。
0400１３２人目の素数さん2006/07/07(金) 02:43:25
>>399
明らかに>>1はTSPに関しては素人なのにゼミやるって・・・
わざわざつるし上げして楽しいのか？
0401１３２人目の素数さん2006/07/07(金) 03:12:32
>>400
そうじゃなくて、ゼミやった方がちゃんと理解できるじゃん。
俺は知ったかぶりする奴も嫌いだが、
理解しないで批判することも同じぐらい嫌いなのだよ。

>>388
>暗号文・・・暗号文の特性などから分析する場合暗号文が長いほど解き易く、暗号文が短ければ解読はほぼ不可能。
>「多項式時間で解けない」というところは一致するが上記に挙げた特性はまったく逆なのである。
それまちがってない？
暗号文の性質で、長い方が解きやすいってのはヒントが増えるからでしょ？
TSPなら制約式(カット)が増えて強い下界が得られることに相当すると思う。
なら同じコトだよ。

また、TSPで点の数が増えるのは、暗号でいうと鍵のビット数が増えることに
相当するから、やっぱり解きにくくなる。

> 「多項式時間で解けない」というところは一致するが
どの暗号？RSAにも言えるっけ？
その辺は詳しくないからよく知らないが。

あなたはいろいろ勘違いしていると思う。
よく知らずに書くと痛い目に遭うよ。
0402KingOfUniverse ◆667la1PjK2 2006/07/07(金) 13:02:34
talk:>>397 何やってんだよ？
040312006/07/07(金) 21:14:53
少しでも可能性のあるものを提示しただけで何故叩かれなければならないのかわからない。
これでは何一つ発言できないではないか。
私とあなた方とでは考え方に大きな隔たりがあるようです。
否定するのは結構ですが、果たしてその否定と同等の代替案等を提示する能力があなた方にあるのかどうか疑問です。

とりあえずしばらく忙しいからオフ会については現時点ではなんとも言えないな・・・。
0404１３２人目の素数さん2006/07/07(金) 21:44:58
何言ってんだか
0405１３２人目の素数さん2006/07/07(金) 23:06:15
>>403
NP問題の定義を知らずにP=NPだと主張しているのだから馬鹿だと思われても仕方ないな
0406１３２人目の素数さん2006/07/07(金) 23:28:40
1の道程

>>29 TSPがNP完全問題である事を知らないのにTSPはNP完全ではないと主張
>>35 NP完全の定義を知らないのにP=NPを主張
>>35 近似スキーム、NP困難の定義を知らないのでお前が説明しろと要求
>>122 オーダーの計算の仕方を知らないのに自分のアルゴリズムのオーダーを出す
>>176 近似アルゴリズムの定義を知らないのに自分のアルゴリズムは近似アルゴリズムだと主張
>>179 近似度とは何かを知らないのに近似度を算出
>>191 自分のアイデアが盗まれるので自分のアイデアは言わない
>>205 でも人のアイデアは要求する
>>310 本一冊読んだだけなのに自分と同じ手法は今まで発明されていないと主張
0407１３２人目の素数さん2006/07/08(土) 01:56:19
>>403
オフ会に来てくれればいくらでも代替案を提示するよ。
0408１３２人目の素数さん2006/07/08(土) 13:34:39
>>1が逃げる理由がよく分からないな。
自分が正しいと確信しているなら、オフ会に来て
損することは何もないと思うけど・・・

>>1がどうしても後ろめたいのなら、無理には誘わないけど・・・
0409１３２人目の素数さん2006/07/08(土) 14:52:05
都道府県を言ってくれれば最寄りの数オタが対応いたします
0410１３２人目の素数さん2006/07/08(土) 16:30:45
最適ルートのアルゴリズムはゲーデル数の鉱脈にうもれているよ。演繹不能な
アルゴリズムだから証明はできないけど、それでやればどの答えよりもいつも短い。
ゲーデル数解析専用マシンを作るほうが・・・・お・い・し・い・
0411１３２人目の素数さん2006/07/08(土) 16:34:32
演繹不能なアルゴリズムだから証明はできないけどP=NPだよ
0412１３２人目の素数さん2006/07/08(土) 20:31:49
数ヲタで集まって食事でもしたら楽しそうだな・・・
0413１３２人目の素数さん2006/07/08(土) 21:09:17
P=NPの証明
NPC=TSPは演繹不能なゲーデル数に対応しているー＞でも使えばP－＞だからP=NP
041412006/07/08(土) 21:40:45
オフ会やるのなら７月中は厳しい。
>>411とか>>413見たいなP=NP派もいた方がいい結果が得られそうな予感。

事実私がオフ会で懸念していることもある。

・この掲示板と連動してリアルに>>1叩きが始まる。
・見ず知らずの人間と会うことに危険を感じるから。
・今月来月は占いの結果が非常に悪く派手な行動をすることに躊躇いがあるから。
　今月、来月中に悪いことが起こると仮定すると。
　○もしオフ会に行ったならば悪いことが起こる。
　○もしオフ会に行かなければ行っておけばよかったと後悔する。
　このパラドックスが解けないのだよ。

まあ、話し合うメリットがあることはわかっているのだよ。
0415１３２人目の素数さん2006/07/08(土) 22:22:52
俺もねー、やりたいテーマはあっても「研究」「論文」というカタチにもっていくのが極端に苦手だったから
>>1にはちょっとシンパシー感じてるところがあるんだな。
0416１３２人目の素数さん2006/07/08(土) 22:44:03
>>411とか>>413は釣り師だから・・・
0417１３２人目の素数さん2006/07/08(土) 22:47:11
> 見ず知らずの人間と会うことに危険を感じるから
そりゃ、>>1みたいなトンデモと会う方が危険を感じるんじゃないか？
なんか、逆ギレして噛みついたりしない？
0418１３２人目の素数さん2006/07/08(土) 22:56:11
噛みつくｗｗｗｗ

ま、>>1も口悪いぞ。
初対面の人間相手に危険を感じるとか発言すべきでないよ。
それは失礼すぎる。
0419１３２人目の素数さん2006/07/08(土) 23:11:09
> 見ず知らずの人間と会うことに危険を感じるから

お前の場合感じてるのは「恐怖」だろｗｗ
言葉まちがえんなよｗ 対人恐怖症ｗ
042012006/07/09(日) 12:13:45
また、失礼になるのかもしれないが。
ネットで会話しただけの顔も名前も性別も人種もただ人間の可能性が高いだけの人に対して疑心暗鬼にならない方が
不思議なのでは？

話変わるけど、非決定性チューリングマシンというのはたとえば

メイン関数
#include<stdio.h>
#include"1.h"

int main(void){
　int i;
　scanf("%d",&i);

　function(i);

　printf("\n%d",i);
　return 0;
}
042112006/07/09(日) 12:14:18
1.h内は
int function(i){
　int j;
　scanf("%d",&j);
　if(j<0){
　　j*=-1;
　}
　for(;j>=0;j--){
　　i*=i;
　}
　return i;
}
のように定義されていた場合、普通のマシンではO(n)になるが
ひ決定性チューリングマシンで1.h内を別に処理するとした場合O(1)になるってことだよね？
そうだとしたらどんな問題もブルート・フォースで解く為の関数を作ってしまえば
非決定性チューリングマシン上でどのような問題も解けることになってしまう気がするのだが・・・。
それとも何？NP完全というにははこうしたサブルーチンをすべて多項式時間で解けるように分割できなければならないってこと？
0422１３２人目の素数さん2006/07/09(日) 12:41:46
>>420
>非決定性チューリングマシン
だから、キミは言葉の定義をもう少しちゃんと
勉強した方がいいと思う。

非決定性チューリングマシンが
多項式時間で解ける問題をクラスNPという。

ゆえにキミの関数をO(1)で解こうが何だろうが、
P=NP問題と何の関係もない。
0423１３２人目の素数さん2006/07/09(日) 12:49:28
どうせならゆんゆんとかkingとかコテハンもみんな呼ぼうよ。
今井と山口も。
数学板全員集合OFFにしたいな。。。
042412006/07/09(日) 14:20:20
>>422
NP完全のことではなく。非決定性チューリングマシンの構造について
本の説明ととイメージが一致しない点があるから質問しているのだよ。

取り合えずメイン関数を
メイン関数
#include<stdio.h>
#include"1.h"

int main(void){
　int i;
　scanf("%d",&i);

　i=function(i); //書き忘れ。

　printf("\n%d",i);
　return 0;
}

に訂正。
0425１３２人目の素数さん2006/07/09(日) 16:23:29
>>424
久保さんの本に、「ヤマ勘がぜったい当たる計算機」と
書いてなかったか？

要は、分枝した結果をO(1)で全部調べるようなもの。
0426１３２人目の素数さん2006/07/09(日) 16:38:33
>>421
>どんな問題もブルート・フォースで解く為の関数を作ってしまえば
>>1よ。多項式時間帰着って知ってるか？
つまり、NP-完全の問題は、他のどのNP-完全の問題にも
多項式時間で変形できるんだ。

TSPに限らず、NP-完全な問題を1つでも多項式時間でとければ、
あらゆるNP-完全の問題が多項式時間で解けてしまうということ。

てか、それを知ってて今まで色々いってたんじゃないのか？
0427１３２人目の素数さん2006/07/09(日) 19:18:01
>>426
>>1はNP問題の定義すら知らないのに多項式時間帰着なんて知ってるわけないじゃん
042812006/07/09(日) 20:01:31
つまり>>421に書いたように各サブルーチンが多項式時間で解けるように分割できるならばNP完全と定義してもいいわけだな。

なるほど。私の解釈が当たっていたということか。
0429１３２人目の素数さん2006/07/09(日) 20:06:30
本当になにも分かってないんだなぁ
0430１３２人目の素数さん2006/07/09(日) 21:15:36
>>428
ちがうって。
お前のコンピュータは非決定性計算機なのかよｗ
0431１３２人目の素数さん2006/07/09(日) 21:49:02
>>420
> 疑心暗鬼にならない方が不思議なのでは？
だからそれは対人恐怖症
0432１３２人目の素数さん2006/07/09(日) 21:53:39
>>1の非決定性なパソコンはTSPを解くときに分裂しまくるということでFA
0433１３２人目の素数さん2006/07/09(日) 21:58:43
うちの大学に>>1みたいなやつがいるんだけど・・・


頓珍漢な質問をする
↓
返ってきたまともな答えが理解できない
↓
「じゃあ，ぼくの方針が正しいのですね」とのたまう
↓
一同呆然沈黙
0434１３２人目の素数さん2006/07/09(日) 22:30:08
非決定性チューリングマシンを持ち出すと面倒なので違う説明をしよう．

クラスNPに属するとは，問題の答えが与えられたときに，それが正しいかどうかが
問題のサイズの多項式オーダの計算量でチェックできる問題の集合だ．
クラスPに属するとは，正しい答えが問題のサイズの多項式オーダの計算量で
求めるられる問題の集合だ．

クラスNP完全とは，直観的にはクラスNPの中の最も難しい問題から構成される
問題の集合だ．
もし，クラスNPに含まれる問題が1つでも問題サイズの多項式オーダで解けるなら，
多項式時間のアルゴリズムを用いて，クラスNPの任意の問題に変換できるので，
クラスNPの問題は全て問題サイズの多項式オーダの計算量で解けることになる．
すなわち，クラスNPとクラスPは同じであると言える．
これが，P=NP?問題です．

個人的には，クラスNP(Non-deterministic Polynomial)じゃなくて，
クラスPV(Polynomial Verifiability)と名づけるべきだったんじゃないの？
と思ったりするんだけどね・・・
0435１３２人目の素数さん2006/07/09(日) 22:35:27
ちなみに，非決定性チューリングマシンは，計算の複雑さの理論に
おいて議論を行うための数学的な概念であって，実在するわけ
じゃないので，そこらへんを勘違いしないようにね．
0436１３２人目の素数さん2006/07/09(日) 22:39:03
>434
ごめん，ちょっと間違いが多かった．
(誤)「クラスNPに含まれる問題が1つでも・・・」
(正)「クラスNP完全に含まれる問題が1つでも・・・」
0437１３２人目の素数さん2006/07/09(日) 22:47:48
P=NPを証明するには，クラスNP完全に含まれる問題を多項式時間で解く
アルゴリズムを示せば良いわけで，特にTSPである必要はない．

クラスNPに属する問題は，これまで数千～数万ぐらい発見されている．
クラスNPに含まれる問題にも，より細かく分類すれば難しい問題と
そうでない問題に分かれるので，比較的易しいと思われる問題を解いても
構わない．

で，SATがクラスNP完全に属することが示されてから30年余，これだけ
たくさんのNP完全問題があるのに，そのどれ1つとして多項式時間
アルゴリズムは見つかっていない．世界中の研究者が取り組んでいるのにね．

そういうわけで，NP完全問題は多項式時間では解けないかもしくは解けても
非常に大きな計算量を要する(O(n^100)とか)と考えている人が多い．
0438１３２人目の素数さん2006/07/09(日) 22:53:53
>>434
> 個人的には，クラスNP(Non-deterministic Polynomial)じゃなくて，
> クラスPV(Polynomial Verifiability)と名づけるべきだったんじゃないの？

それは名前を付けた当時にも大論争になって、
結局クヌースがまとめ上げて、そう名付けたんだよ。
0439１３２人目の素数さん2006/07/09(日) 23:12:02
>438
だよね．そこは個人的な意見ってことで．
でもまあ，歴史的背景があるとは言え，非決定性チューリングマシンを用いた
クラスNPの説明は初めて聞く人には分かり難いとは思う．

だからと言って>1が開き直る理由にはならんけどな．
0440１３２人目の素数さん2006/07/09(日) 23:14:15
>437
また間違えた・・・orz
3,4行目
×クラスNP
○クラスNP完全
0441１３２人目の素数さん2006/07/09(日) 23:20:13
>>438
( ･∀･)つ∩ﾍｪｰﾍｪｰﾍｪｰ
0442１３２人目の素数さん2006/07/10(月) 02:41:51
>>439
たしかにな。
俺もマイケル・シプサの「計算理論の基礎」を読んだが、
最初、オートマトンの話から始まって結構めげたし・・・

>>1が持ってる「巡回セールスマン問題への招待」にも、
>>439がいうようなVPを「証拠P」みたいに書いてるところが
あるんだけど。これでも理解できないのが信じられない。
0443１３２人目の素数さん2006/07/10(月) 12:57:19
>>442
>>1はその本をちゃんと読んでるのかね？
0444１３２人目の素数さん2006/07/10(月) 18:58:57
最適解が与えられたとして、それが最適解であることをPで確定的に証明することはできるのか。
0445１３２人目の素数さん2006/07/10(月) 19:56:37
>>444
そうじゃなくて、決定問題の場合は、
ある目的関数値以下であることを確かめられればよい。
それがNP-完全。
044612006/07/10(月) 22:27:09
>>434の説明は無駄が無くていいですね。
曖昧な所が少し消えたよ。

取り合えず久保さんの非決定性チューリングマシンの説明は、結構ごまかしている気がしてならないのですよ。
私が非決定性チューリングマシンについて一応確認しておきたいところは

図示した方が伝わりやすいみたいなので・・・。

現在使われている一般的な構造のコンピュータ↓
┏━━━┓
┃1GHz　┃
┃ 　intel ┃
┃　　　　 ┃
┗━━━┛
カーネル：「ペンティアムよO(n^5)のプログラムを動かしてくれ。」
ペンティアム：「いいけど。n^5程度の時間がかかるよ。」
数秒後。。。
ペンティアム：「つ計算結果」
カーネル：「どうも。」
044712006/07/10(月) 22:27:41
非決定性チューリングマシン↓
┏━━━┓┏━━━┓┏━━━┓┏━━━┓
┃1GHz　┃┃nGHz　┃┃n^2GHz┃┃n^3GHz┃
┃　　　p1┃┃　　 p2 ┃┃　　 p2 ┃┃　　 p2 ┃
┃　　　　 ┣┫　　　　 ┣┫　　　　 ┣┫　　　　┣・・・・・・・
┗━━━┛┗━━━┛┗━━━┛┗━━━┛
カーネル：「p1よ。O(n^5)のプログラムを動かしてくれ。」
p1：「いいよ。実質O(1)程度の時間で終わらせますね。」
カーネル：「は？」
p1：「p2よ。私はループ以外の順次処理は全部やるからあなたはループのところお願い。」

p2：「まんどくさい。漏れはループの条件の処理だけやるからp3残りのO(n^4)やってね。」
p3：「まんどくさい。漏れはループの条件の処理だけやるからp4残りのO(n^3)やってね。」
p4：「まんどくさい。漏れはループの条件の処理だけやるからp5残りのO(n^2)やってね。」
p5：「まんどくさい。漏れはループの条件の処理だけやるからp6残りのO(n)やってね。」
p6：「>>p5つ計算結果」
p5：「>>p4つ計算結果」
p4：「>>p3つ計算結果」
p3：「>>p2つ計算結果」
×ｎ回

p2：「>>p1つ計算結果」
p1:「つ計算結果」
カーネル：「速や！！」

みたいに非決定性チューリングマシンってのは本来メイン関数にO(1)で計算しなければならないサブルーチン内からさらに他の高速なプロセッサに処理を依頼することが可能なのかどうかということ。
0448１３２人目の素数さん2006/07/10(月) 22:28:56
ぜんぜん違う
044912006/07/10(月) 22:29:38
なんとなく分かったから、面倒ならレスしなくていいよ。
0450１３２人目の素数さん2006/07/10(月) 22:31:20
図示とかどうでもいいからきちんと教科書読めよ
045112006/07/10(月) 22:34:35
図が間違っていたので訂正。
┏━━━┓┏━━━┓┏━━━┓┏━━━┓
┃1GHz　┃┃nGHz　┃┃n^2GHz┃┃n^3GHz┃
┃　　　p1┃┃　　 p2 ┃┃　　 p3 ┃┃　　 p4 ┃
┃　　　　 ┣┫　　　　 ┣┫　　　　 ┣┫　　　　 ┣・・・・・・・
┗━━━┛┗━━━┛┗━━━┛┗━━━┛
0452１３２人目の素数さん2006/07/10(月) 22:37:09
チューリングマシンの定義を書いてみ？
045312006/07/10(月) 22:41:10
>>452
オートマトンで状態繊維とか紙テープ読ませるとか？
0454１３２人目の素数さん2006/07/10(月) 22:44:53
>>453
・・・
やっぱだめだこいつｗｗｗ
0455１３２人目の素数さん2006/07/10(月) 22:45:20
>>447
全然違うｗｗｗ
0456１３２人目の素数さん2006/07/10(月) 22:48:48
>>447
それじゃO(2^n)をO(n)でできる説明になってないだろ。
045712006/07/10(月) 22:49:11
どう違うんだ・・・。
こうすれば久保さんの言っているヤマ勘が100%当たるマシン、非決定性チューリングマシンになるではないか。
>>447を否定するということは久保さんを否定することに等しい。
0458１３２人目の素数さん2006/07/10(月) 22:51:26
非決定性チューリングマシンが分からないんだったらこっち読めよ
非決定性チューリングマシンを使わずにNPを定義してるから
ttp://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
0459１３２人目の素数さん2006/07/10(月) 22:52:17
>>457
だから、それで指数時間のヤマ勘をどうやってあてるのさ？
0460１３２人目の素数さん2006/07/10(月) 22:54:23
>>458
オートマトンを知らない>>1にはかえって難しくないか？

>>1
オートマトン
状態
アルファベット
遷移関数
開始状態
受理状態
言語

この辺の用語は大丈夫か？
0461１３２人目の素数さん2006/07/10(月) 22:58:53
>>457
結局オフはどうするの？
少しでも行く気はあるの？
046212006/07/10(月) 23:06:46
>>459
指数回のループにならないように関数を分割し次のプロセッサに渡す。

>>460
オートマトン：ある状態から入力により次の状態に遷移させることを繰り返す。
状態：オートマトン上で遷移された場所みたいなもの。
アルファベット：Ａ～Ｚの26文字小文字も26文字ある。
遷移関数：状態から次の状態に遷移させるための条件。
開始状態：たぶん状態が開始になってるやつ。
受理状態：入力により遷移された結果受理される状態◎になるやつ。
言語：自然言語とか人工言語とか？何を説明すれば？

>>461
少しは行く気あるぞ。
046312006/07/10(月) 23:08:04
振り返ってみれば知的なスレだとか思った。
0464１３２人目の素数さん2006/07/10(月) 23:09:41
>>462
行くんなら都道府県よろ
じゃないと話を進めようもない
046512006/07/10(月) 23:10:57
>>464
私の県で開催するってこと？
0466１３２人目の素数さん2006/07/10(月) 23:12:41
>>462
吹いたｗｗ言葉の定義なんにもわかってないねー，ばかだねー．


とりあえず>>447で具体的な指数オーダの問題を解く手順を示してくれ
0467１３２人目の素数さん2006/07/10(月) 23:13:53
>>465
うん。若しくはその近く。（可能なら）
0468１３２人目の素数さん2006/07/10(月) 23:13:55
まあ関東か関西かぐらいは知りたいな。

もしかしたら離島かもしれないが……
046912006/07/10(月) 23:16:53
>>466を見たら県をさらすことにすら身の危険を感じたので中部/北陸地方とだけ。
0470１３２人目の素数さん2006/07/10(月) 23:18:10
>>469
具体的に何の危険を感じてるんだ？
0471１３２人目の素数さん2006/07/10(月) 23:19:46
>>1には>>466が通り魔か何かに見えるらしいｗ
047212006/07/10(月) 23:20:31
>>470
掲示板での中傷がエスカレートしてストーカー、性的嫌がらせに発展する危険。
0473１３２人目の素数さん2006/07/10(月) 23:22:43
とりあえず>>1が>>406を見てどう感じたかを教えて欲しいな
04744662006/07/10(月) 23:22:55
ﾜﾛｼｭｗｗｗ俺悪人ｗｗ

とりあえずさ，
＞指数回のループにならないように関数を分割し次のプロセッサに渡す
じゃかなりごまかしてるっぽいから，じっさいにTSPを解く手順を示してくれ．
047512006/07/10(月) 23:25:20
>>473
>>1が極端に悪くなるように歪曲されている点が気になる。
047612006/07/10(月) 23:26:24
>>474
その条件は以前説明したはず。
04774662006/07/10(月) 23:28:06
>>476
じゃそのレスの場所よろ
047812006/07/10(月) 23:28:59
>>477
あなたには教えません。
自分で探してください。
0479１３２人目の素数さん2006/07/10(月) 23:29:42
>>469
それはその範囲なら行かれると解釈してもいいんだね？
0480１３２人目の素数さん2006/07/10(月) 23:30:30
都道府県でストーカーとか(笑)
04814662006/07/10(月) 23:30:44
やっぱできないのか．ざんねん．
048212006/07/10(月) 23:33:59
>>479
難しい場所もある。
いっそ東京とかにしてくれた方がいいかもしれないとか思った。（迷うかも知れないが）
0483１３２人目の素数さん2006/07/10(月) 23:35:25
>>482
＞迷う
1.行くかどうかを迷う
2.東京で迷う

しっかり書いてくれ
0484１３２人目の素数さん2006/07/10(月) 23:37:03
>>472
ひょっとして貴方はVIPPERのひと？
048512006/07/10(月) 23:41:06
>>483
東京までなら駅員に聞けばたぶん行ける。
東京は私の想像よりも都会と思われるので迷いそうです。

つまり2が問題。
0486１３２人目の素数さん2006/07/10(月) 23:41:15
LA2006のついでにでやればいいんじゃ？
048712006/07/10(月) 23:43:05
>>484
VIPPERって２ちゃんねる用語か何か？
私はそんなに２ちゃんねるに来ない人だったのであまり用語わからない。
048812006/07/10(月) 23:45:37
悪いけど今日は帰るね。
0489１３２人目の素数さん2006/07/11(火) 00:13:22
>>462
帰るなよｗｗｗ

特にオートマトンについてはかなり大ヒントを
出してるんだからちゃんと答えんかいｗｗｗ
定義に使う言葉をわざわざ並べてあげたのに。

あと言語って、オートマトンが受理する言語に決まってるじゃん・・・
0490１３２人目の素数さん2006/07/11(火) 00:13:56
>>482
東京なら海洋大でやるかい？
0491１３２人目の素数さん2006/07/11(火) 00:16:00
>>462
> 指数回のループにならないように関数を分割し次のプロセッサに渡す。
それじゃ決定性計算機で指数オーダーの問題が解けちゃうじゃん・・・
何を考えているのだい？
0492１３２人目の素数さん2006/07/11(火) 00:28:27
>>485
海洋大なら東京駅から10分圏内だから迷わないよ。
0493１３２人目の素数さん2006/07/11(火) 02:05:06
>>1は結局いつ来るのかハッキリしてよ．
04944342006/07/11(火) 02:39:07
なんか自分の説明が全然理解されていないのが悲しい…
わざわざ非決定性チューリングマシンを使わない説明をして，
非決定性チューリングマシンが実在しないとも言ったのに…

>486
今年の夏のLAシンポジウムっていつでどこでしたっけ？
0495１３２人目の素数さん2006/07/11(火) 18:54:47
もしかして>>1ってメスだったりするのか？
0496１３２人目の素数さん2006/07/11(火) 19:17:18
>>495
なんでそう思った？身の危険とかの節？
0497１３２人目の素数さん2006/07/11(火) 19:23:24
>>495-496
>>472のあたりかな？
0498１３２人目の素数さん2006/07/11(火) 19:53:02
>>497
たぶん、自意識過剰なだけだよ。

それより、TSPの話題（主に計算理論）に復帰。
0499１３２人目の素数さん2006/07/11(火) 21:13:14
まーOFF会を装って集団ﾚｲｰﾌﾟとかだったらシャレならんからな……。
不安になる気持ちは分からなくも無い。
0500１３２人目の素数さん2006/07/11(火) 21:28:15
今来た.

>494
広島 http://www.cs.hiroshima-u.ac.jp/la/summer.html
講演締切りも参加締切りも終わってる.
050112006/07/11(火) 22:26:51
がっかりさせないうちに言っておくが男だ。
レイプできなくて残念だったな。
明言しないでレイプ目的の香具師が来たら問題になるからいっておく。

おまいらはいつ頃が都合いいのだ？
私は8/1～8/10程度なら可能かもしれない。
しかし、私の理論がもしも正しかったらどうしようか・・・

「>>1が考えられるわけ無いじゃん？漏れが考えたんだよ。この手法。」とかなったら最悪だ。。。
ネットで晒されるのも困るな。。。まだ未完成な物だし、それに残りの少しを付け足して「俺が作ったんだ」とか言われたら終わりだ・・・。

個人的な範囲のことで問題点はまだ残っているな。
050212006/07/11(火) 22:27:41
悪いけど今日もこれで失礼します。

なんだか具合悪い。。。
0503１３２人目の素数さん2006/07/11(火) 22:44:02
>>501
だれもお前の修論なんか盗まないから安心しろ。
それより、間違いだらけでお前がガッカリする可能性の方が
遙かに高い。

>>502
いきなり逃げるのかよｗ
0504１３２人目の素数さん2006/07/11(火) 22:45:08
>>501
それと、そんなに盗まれるのが怖ければ、
お前の研究室のWebサイトにテクニカルレポートとして
公開しておけばいい。
一流の研究者は広く意見をもらうためにみんなそうしてる。
0505１３２人目の素数さん2006/07/12(水) 04:44:19
最低限>>460とかごく基本的な用語くらいは知っておかないと
オフ会以前に修論がヤバいだろ
0506１３２人目の素数さん2006/07/12(水) 13:04:09
>>504
そうだな．それが基本だな．
0507１３２人目の素数さん2006/07/12(水) 21:20:30
今日は>>1来ないのかよ

どこまで勉強したのか報告ぐらいしろっての．
050812006/07/12(水) 21:32:12
>>507
何か用？
050912006/07/12(水) 21:50:31
それにしても今回の国家試験は痛かった。
ソフトウェア開発技術者試験を受けたのだが・・・
午前、午後１はクリアしていたのだが午後２で落ちてしまった。
私の得意なオーダーの話だったのだが・・・。
0510１３２人目の素数さん2006/07/12(水) 22:07:20
>1
確認したいんだけど,
計算時間が O(n^5 2^((log n)^2)) くらいのを O(n^7) とか言ってない?
0511１３２人目の素数さん2006/07/12(水) 22:11:15
どっちにしろ、n^7だかなんだかの近似アルゴリズムなんて
まったく使えないだろ・・・
051212006/07/12(水) 22:16:50
>>511
最悪でも近似アルゴリズムとしてとして使えるという話だ。
私が狙っているのはもちろん完全な解法です。
0513１３２人目の素数さん2006/07/12(水) 22:22:12
FITでオフ会やろうぜ
FITなら山口人生様も来るのか？
0514１３２人目の素数さん2006/07/12(水) 22:54:12
>>509
わらた
0515１３２人目の素数さん2006/07/12(水) 23:32:18
>>512
厳密解だという保証がなきゃダメなの．
05165102006/07/12(水) 23:45:42
>512
無視された（；´Д｀）

多項式多項式言ってるけど, 前の方のレスを見る限りだと,
>122
>ただO(2^((log n)^2))と考えてよい箇所をO(n^2)と置き換えた箇所がある。
とO(2^{log^2 n})をO(n^2)で評価している等酷い間違いが見られるので,
適当に>510のような予想をしたんだが, そこんところどう?
0517１３２人目の素数さん2006/07/12(水) 23:51:12
>>516
まぁ、nが十分に大きければ
n < 2^((log n)^2) < n^2
だから、O(n^7)と評価しても完璧に間違いではないけど
あんまり良くないね。
0518１３２人目の素数さん2006/07/12(水) 23:52:52
あ、2^((log n)^2)か。
ごめん。勘違いしてた。普通に指数オーダーだなｗｗｗ

n^2 << 2^((log n)^2)
だな。こりゃあかんわ。多項式ですらない。
0519１３２人目の素数さん2006/07/13(木) 00:20:40
このスレ初めて読んだけど、上の方をざっと見ると >>1 は P=NP と
信じている訳ですね。
0520１３２人目の素数さん2006/07/13(木) 01:23:58
山口人生よりはましだろう。
0521１３２人目の素数さん2006/07/13(木) 02:06:58
>509
計算量ってものを正しく理解していないから落ちたと思わないのだろうか？

・・・思わないからスレが続くんだろうな
0522１３２人目の素数さん2006/07/13(木) 04:18:37
情報系でもソフ開落ちるやつっているんだな
0523１３２人目の素数さん2006/07/13(木) 12:04:03
高専３年の俺でも>>1の言ってることの意味不明さは理解できる。
0524１３２人目の素数さん2006/07/13(木) 13:42:01
>>512
盗まれるのが嫌ならそれなりの方法を取ればいいのに、なんで>>1は何もしないの？
0525１３２人目の素数さん2006/07/13(木) 15:56:01
方法を知らない ＆ ノーヒントでやってるんだから無知でも許せよ
0526１３２人目の素数さん2006/07/13(木) 16:30:58
ヒントはこのスレで沢山でたぞ
052712006/07/13(木) 20:19:13
>>526
そうですか？
誰も多項式時間で解く為のヒント出してませんよ？

結局オフ会がどうなったんだろうか？
実行委員長はどこにいった？
やらないなら別にいいのだが・・・。

私にとってはもうこのスレももう終わりってことですね。
多項式時間で解くという核心が抜けている。
0528１３２人目の素数さん2006/07/13(木) 21:24:15
>>527
うん，いい加減おもしろくないからネタはやめたら．

まともに定義も言えないやつがTSPを多項式オーダで解きたい．
一向に構わないけど解きたいのはお前でしょ．
どんなアイディアで，どこで詰まってるのかも言わずにヒントｸﾚｸﾚって設定に無理があるって＾＾；
052912006/07/13(木) 21:33:43
>>528
現状のアルゴリズムでは問題があることは分かっている。そこで改善点の１つも発見した。
そして、その改善点を検証するまでははっきりしたことは言えない。どんなに早くとも公表はプログラムの書き換えが終わる目で待ってもらうことになる。

というか、私のアルゴリズムを知らなければ多項式時間で解く方法を"考える"ことすらできないの？
053012006/07/13(木) 21:35:30
というか>>528=>>466だから一応言っておくけど
検証が終わったからすぐに公表するようなことはするつもりないから。
0531１３２人目の素数さん2006/07/13(木) 21:37:40
>>529
もし思いついたら、お前なんかに教えずに自分で公表するよｗｗ
お前以外の人間はTSPを「考える」必要はないんだけどなーそのへんわかってるか？
こんな糞スレに有意義なコメント残す義務なんてないんだよね
0532１３２人目の素数さん2006/07/13(木) 21:38:52
多項式時間で解けないと"考え"てるんだよ
053312006/07/13(木) 21:47:04
>>531
お前のようなやつがいるから俺も公表できないことを知れ。
>お前以外の人間はTSPを「考える」必要はないんだけどなーそのへんわかってるか？
つまり、他人の理論をコピーするだけで満足し、その理論を知らない人を見下すというドブ鼠か。
>こんな糞スレに有意義なコメント残す義務なんてないんだよね
お前に誰も頼んでないから帰れば？
0534１３２人目の素数さん2006/07/13(木) 21:51:46
＞お前に誰も頼んでないから帰れば？
だ　が　こ　と　わ　る

家庭教師が欲しけりゃ金だして雇えｗ
無料で教え請おうと思ったらそれなりの態度が必要であり十分でないのですよm9（＾Д＾）ﾌﾟｷﾞｬｰ
053512006/07/13(木) 21:52:50
>>532
それはTSPを解決する有効な考え方の一つであるから否定はしない。
053612006/07/13(木) 21:56:35
>>534
まず、お前の態度が悪いから。
>家庭教師が欲しけりゃ金だして雇えｗ
TSPを多項式時間で解く方法を金出せば教えてくれる教師がいたらたぶん金出すな。今の俺なら。
0537１３２人目の素数さん2006/07/13(木) 21:58:23
一億は下らないですがよろしいですか？
0538１３２人目の素数さん2006/07/13(木) 22:00:44
>>537
おいおい、1億だったら俺が買うぞｗ
053912006/07/13(木) 22:01:05
>>537
一億払う覚悟はある。
ただし、近似アルゴリズムではだめだからな。
今、そんなかねないから、ローンでな。
それと、私が発見者になることも条件。
0540１３２人目の素数さん2006/07/13(木) 22:01:40
桁が違う
百億なら売る人がいるかな
054112006/07/13(木) 22:03:00
>>540
\10000000000でも買う。
私の一生を捧げて払う。
でも、発見者は私になることが条件。
0542１３２人目の素数さん2006/07/13(木) 22:04:18
発見者って…
1にはプライドは無いのか。
0543１３２人目の素数さん2006/07/13(木) 22:04:27
キャッシュで出す奴がいるから>>1には買えないよ
ざんねんでした・・・
054412006/07/13(木) 22:06:09
>>542
だって、誰が発見者でもいいのだったら、その解法を久保さんが本にして出すんじゃない？
それだったら本買った方が安い。
054512006/07/13(木) 22:07:31
>>543
ローンでキャッシュの香具師の２倍払うから俺によこせ。
0546１３２人目の素数さん2006/07/13(木) 22:09:59
いやよこせって言われてもｗ
後学のために聞くけどローンで百億どうやって払うの？
利子すら無理だよ>>1じゃ
054712006/07/13(木) 22:12:23
>>546
スキミング・詐欺・麻薬取引・証券取引法違反
なんでもします。
054812006/07/13(木) 22:13:08
>>547
これは犯行予告ではありません。
0549１３２人目の素数さん2006/07/13(木) 22:14:36
>>574-548
うーんつまらないなあもっと面白いこと言ってよ
じゃ担保は？
05505492006/07/13(木) 22:15:06
おっとアンカーが・・・
055112006/07/13(木) 22:16:12
>>549
私のティムポで・・・。
0552１３２人目の素数さん2006/07/13(木) 22:18:01
だめだセンスなさ杉・・・
こんな>>1に振った俺が悪かった
0553１３２人目の素数さん2006/07/13(木) 22:20:09
>>546-548
別に犯罪に走らなくても、
あらゆるNP問題が多項式時間で解けるようになるんだから。
特許を取って実装を製品化するか、
アルゴリズムを秘密にしつつ起業して探索請負でもすれば
億単位の収入が見込めるくらいの需要はあるんじゃない？
100億はどうか知らないけど。
055412006/07/13(木) 22:24:41
>>553
カーナビにでも実装しようか。
0555１３２人目の素数さん2006/07/13(木) 22:48:45
>>544
なんで久保？
もっと有名な研究者はたくさんいるのに
0556１３２人目の素数さん2006/07/13(木) 22:59:34
ヒント：久保しか知らない
0557１３２人目の素数さん2006/07/14(金) 00:27:40
>>536-542の流れと
>>544のレスの「だって」以降の内容とのつながりが全く不明だな
0558１３２人目の素数さん2006/07/14(金) 01:00:24
なんというか最初からここまでまったくもって不明だ。
いまだに1の案のかけらもわからんし。間違ってそうなことはわかるけど。
0559１３２人目の素数さん2006/07/14(金) 01:04:44
カーナビって……しょぼ……

NP問題が解けるとなれば暗号解読やれば各国の諜報機関が垂涎モノじゃないの
0560１３２人目の素数さん2006/07/14(金) 02:06:42
>>555
まぁ、TSPでは久保さんかなり有名だし。
0561１３２人目の素数さん2006/07/14(金) 05:48:09
>>1
ねぇ、もう少し頭よさそうにしてよ
0562１３２人目の素数さん2006/07/14(金) 21:26:49
>>1
はやくゼミの日程を決めろ．
3～5日間ぐらいの予定でいいのか？
056312006/07/14(金) 21:49:44
>>562
やっぱやめていい？
だってお前466だろ？
お前はただ単に私のアルゴリズムを盗みたいだけじゃないか。
056412006/07/14(金) 22:01:51
>>557
つながりの説明。

誰が発見者でもいい。→誰かが発見者である。それは文章から>>1では無くなる。
つまり、誰が発見者でもいい場合、わざわざ大金を払って手法を知ることは賢い方法とはいえない。(なぜならば私が発見者になりたいから。)

誰かが、発見したならばその手法はいづれ広く知られることは容易に推測できる。
当然のごとく久保さんもその手法を知ることが推測できる。
久保さんのそのTSPにかける情熱から推測して「巡回セールスマン問題の解決」みたいな本にその手法を解説した物を出版することも推測できる。
また本の値段は100億円未満であることも推測できることである。

よって、本を買って学習することが賢明だといえるわけだ。
056512006/07/14(金) 22:06:28
>>555
以下の条件から久保さんを挙げた。

日本人の中では最高峰のTSPに精通した人であること。
おそらく日本語が母語であるため、私のような日本人に通じやすいボキャブラリーで本を書くことができると推測できるから。
056612006/07/14(金) 22:09:53
>>558
現段階では私のアルゴリズムに頼らずに多項式時間で解く為の手法または手法になりうる可能性のある物を追求して、
有効と思われる物をこのスレッドに記していただければありがたいです。
056712006/07/14(金) 22:10:54
>>559
TSPに特化したアルゴリズムである可能性もあるだろう？
0568１３２人目の素数さん2006/07/14(金) 22:18:04
> 私のアルゴリズムに頼らずに多項式時間で解く為の手法または手法になりうる可能性のある物を追求して、
> 有効と思われる物をこのスレッドに記していただければありがたいです。

他人のアイディア盗みたいだけじゃん。
056912006/07/14(金) 22:21:43
>>568
名前を挙げていただければ、参考になった場合に論文にその名前が記されます。
もちろん発見者は私にさせていただきます。
0570１３２人目の素数さん2006/07/14(金) 22:26:18
なるほど。盗みたいだけ、と。
057112006/07/14(金) 22:33:44
>>570
盗むとは違う。
私に影響を与えた者にもそれなりの賞賛が与えられるだろう。
つまり、実質一方向的な共同開発といえる。
0572１３２人目の素数さん2006/07/14(金) 22:34:48
>>563
違うし．
妄想と推測だけでいうのやめてくれる？
0573１３２人目の素数さん2006/07/14(金) 22:36:09
>>571
はずかしいな、お前。
いいから早くゼミの日程を決めろ。
勉強不足がはずかしいからって逃げるなよ。
0574１３２人目の素数さん2006/07/14(金) 22:37:30
ますます>>1が馬鹿になっていくねぇ。
必死すぎるとそのうち身元バレするぞ。
マジで逃げた方がいいのでは。
057512006/07/14(金) 22:39:36
466の道程。
>>528　理由はともかく私のアルゴリズムを要求していることが分かる。
>>531　ここでもしいい案が浮かんだら自分の利益にすると考えていることが伺える。

つまり466はただ単に私のアルゴリズムを盗もうと考えることが自然である。
0576１３２人目の素数さん2006/07/14(金) 22:42:33
>>572
1は愚かだからさ、句読点で判断してるのさ
0577１３２人目の素数さん2006/07/14(金) 22:43:01
>>575
でさ、O(2^((log n)^2)）って結局指数オーダーじゃないの？
すでにPじゃないじゃん。
0578１３２人目の素数さん2006/07/14(金) 22:44:50
>>576
句読点かｗｗｗ
普段論文書くから「，．」になってるんだが・・・
研究者なら普通なのに，>>1はそんなことも知らないのか．
057912006/07/14(金) 22:46:57
>>576
重要な判定基準だ。

仮に違う人物であったとしても同類であることが分かる。

>>577
最終的にはO(2n^5)=O(n^5)になる見込み。
O(2^((log n)^2)）は擬似ブルート・フォース用のアルゴリズムの計算量。
05804662006/07/14(金) 22:48:38
じつは>>466 = >>568 = >>570 = >>576 でした．ｸｽｸｽ
>>1よ踊れ踊れ
0581１３２人目の素数さん2006/07/14(金) 22:49:03
>>579
ブルート・フォースってよく逝っているが、
ちゃんと意味分かってるのか？

それに疑似ブルート・フォースなんていう意味不明な用語を
勝手に作るな。指数オーダーを多項式に下げるのは
簡単でないので、見込みなんか当てになるものかよ。
058212006/07/14(金) 22:49:04
句読点以外にも、表現能力の程度も参考にしている。
同類と判断された人は残念ながら小学生レベル。
0583１３２人目の素数さん2006/07/14(金) 22:49:38
>>582
自分のことか？
0584１３２人目の素数さん2006/07/14(金) 22:50:41
>>582
早くゼミの準備始めろよ。こっちはもうやってんだ。
0585１３２人目の素数さん2006/07/14(金) 22:51:32
>>581
>>1にはきちんとした用語の定義などできない．
058612006/07/14(金) 22:52:39
>>581
擬似開発した実際にブルート・フォースを行わなくとも実際にブルート・フォースで計算した物と同じ効果が得られるだろうアルゴリズムのこと。

おそらくここで説明しても理解できる人間は皆無だろう。
0587１３２人目の素数さん2006/07/14(金) 22:53:46
訂正

>>581
擬似ブルート・フォース・・・私が開発した実際にブルート・フォースを行わなくとも実際にブルート・フォースで計算した物と同じ効果が得られるだろうアルゴリズムのこと。

おそらくここで説明しても理解できる人間は皆無だろう。
058812006/07/14(金) 22:59:08
どうでもいいけどみんなが私が院生だとまだ思っているの？
みんながP≠NPだといえばそうなんだとP=NP派を追い出す人と一緒だね。

実は専門学校生なのに院生だと勘違いしてくれてありがとね！
0589１３２人目の素数さん2006/07/14(金) 22:59:24
>>587
だからきちんとした裏付けがないと
単なる近似ヒューリスティクスだろうが。
0590１３２人目の素数さん2006/07/14(金) 23:00:35
>>588
自分からバカですと告白してどうする？
低学歴は所詮低学歴か．
0591１３２人目の素数さん2006/07/14(金) 23:00:41
>どうでもいいけどみんなが私が院生だとまだ思っているの？
いやまさか。
具体的な話をしだして知識の乏しさが露呈してからは
だれも思ってないでしょ。
059212006/07/14(金) 23:01:22
>>589
近似じゃない。
完全だ。
059312006/07/14(金) 23:02:12
>>590
でも大学生であることも事実。
0594１３２人目の素数さん2006/07/14(金) 23:02:21
なぜゼミを避けるのかと思ったら、
ゼミのやり方さえ分からないからだったとは。
専門学生だろうが恥ずかしいものは恥ずかしいがな。
0595１３２人目の素数さん2006/07/14(金) 23:02:33
>>588
まともな大学院の学生だとは思ってませんよ．
それなりの大学を卒業できた人間ならもっと面白いネタスレにしてくれる筈．
0596１３２人目の素数さん2006/07/14(金) 23:03:01
>>592
証明がないと単なる妄想。
059712006/07/14(金) 23:03:16
>>591
その割には修士論文どうこうって結構出てたよね。
0598１３２人目の素数さん2006/07/14(金) 23:05:03
>>597
だいぶ前だな．
学会逝かないとか宣った時点でなんだこいつとは思ってたが
単なる落第者だとは思わなかったよ．
0599１３２人目の素数さん2006/07/14(金) 23:05:26
なにもしなくても卒業できる大学や
そんな人でも入れる大学院はたくさんあるからね

ひとくちに学部生とか院生とか言われてもね
ましてやそれで釣った気になられてもね
0600１３２人目の素数さん2006/07/14(金) 23:05:50
ま、そういって>>1が逃げないためにも、
全国のTSP関係の修論は全部チェックするけど。
0601１３２人目の素数さん2006/07/14(金) 23:07:24
P=NPを信じて研究してる研究室ってある？
あれば、そこも忘れないようにリストにしておきたいが。
060212006/07/14(金) 23:07:55
>>600
はいはい。
院生と信じてくれてありがとさん。
0603１３２人目の素数さん2006/07/14(金) 23:08:48
>>602
念のためさ。
数学者は一応億万が一の可能性があれば
チェックはするのよ。
0604１３２人目の素数さん2006/07/14(金) 23:09:48
さ，>>1がらみの話題はこれぐらいにして，
TSPに戻るか？
0605１３２人目の素数さん2006/07/14(金) 23:12:26
>>564
>久保さんのそのTSPにかける情熱から
最近TSPよりSCM関係の研究がメインだと思うが．
060612006/07/14(金) 23:12:58
>>604
そうだな。
取り合えず検証結果ぐらいはあなた方にも報告しますね。

俺も大学院行けるんだな。ｗ
0607１３２人目の素数さん2006/07/14(金) 23:17:31
>>606
まず，大学院にきちんと入学して基礎を勉強しろ．
話はそれからだな．
0608１３２人目の素数さん2006/07/14(金) 23:19:29
そろそろ大学も大学院も全入時代だもんねぇ・・・
060912006/07/14(金) 23:19:58
>>607
大学院って就職が決まらなくてNEETなりそうな人が就職決まるまで居るNEET収容施設って聞いたんですけど・・・。
嘘だったんですね。
061012006/07/14(金) 23:23:44
>>608
私は大学生なのだよ。
専門学校生でもあるが。
0611１３２人目の素数さん2006/07/14(金) 23:26:42
まあ、>>1がいけるような大学院はNEET収容施設なんじゃないの？
061212006/07/14(金) 23:29:15
>>611
うむ。それじゃあお勧めは？
東京大学の大学院あたりか？
0613１３２人目の素数さん2006/07/14(金) 23:30:25
>>612
院のほうが入りやすいからｵﾇﾇﾒ
061412006/07/14(金) 23:33:43
私は卒業後プログラマかＳＥかＡＶ監督になりたいと思っているんですけど。

仕事しながら大学院って行けるの？

院卒ってのはやっぱり格好が付くような気がする。
0615１３２人目の素数さん2006/07/14(金) 23:33:51
>>612
院は誰でも入れるが，卒業できるかどうかは知らん．
学部と違って決して甘くはない．
まず>>1みたいなのは指導教官から鍛え直されるだろうな．
0616１３２人目の素数さん2006/07/14(金) 23:34:45
>>614
仕事しながらはやめとけ。

それより、なんでTSPでP=NPに挑戦するんだよ。
簡単なKPとかにすればいいのに。
0617１３２人目の素数さん2006/07/14(金) 23:35:05
>>1って何年生？
061812006/07/14(金) 23:47:02
>>616
1年の最初の方で大学の講義で巡回セールスマン問題ってのが提示された。
その説明をしていた助教授は「この問題は世界中の科学者が挑戦してできなかった。私も大学時代に挑戦続けたが無理だった。いいところまで言ったのだが・・・。」と語った。
私はこれを見て「この問題は解ける。なぜならば、明らかに見て取れるさまざまな特性があるではないか。」
その次の日から私は一人でとの問題をあらゆる方向から分析した。
さまざまな形式の表にしたり。木構造にしたり。試行錯誤を繰り返し、その手法は何十にも上った。
しかし、どれも解けるとは言えない物ばかりだったのだ。
やがて数ヶ月の間。私は現在の進展を軽くノートに記して。しばらく封印することにしたのだ。。。

・・・続編は８月号で。

>>617
3rd Grade
0619１３２人目の素数さん2006/07/14(金) 23:54:19
>>618
TSPは構造が少ないから難しいんだよ。
さまざまな特性ってのも思いこみの可能性が高い。
他のNP-完全・NP-困難な問題の方がまだ希望がある。
調べたことがあるのか？
どのNP-完全の問題が解けてもいいということは理解しているのか？
0620１３２人目の素数さん2006/07/14(金) 23:56:03
>>618
ちなみに表にしたり、データ構造を工夫するのは
膨大な研究がある。まず調べるべき。
062112006/07/15(土) 00:08:50
>>619
まあまあ。
まだ残されている可能性があるんだ。
それを検証ぐらいさせてくれよ。
それがだめだったらもう諦めるかも。
実際今までどうしてこんなに続けることができたのかというと、今まで生み出してきた研究成果を捨てるのが惜しかったからってのが一番大きいかも。

でもＴＳＰを解析しているうちにアルゴリズムをどのように解析したら良いかというセンスみたいなのがかなり付いた。
そして、その自分が感覚的に身に着けたセンスそのものを解析することで、さまざまなアルゴリズムを最適な計算量に収束させることのできる分析法も編み出した。
これは、プログラム化も夢ではない物で、将来的にはコンパイラや人工知能に適用できると考えている。
0622１３２人目の素数さん2006/07/15(土) 00:36:42
>>621
> これは、プログラム化も夢ではない物で
だから，コンピュータの限界とかを知っているのか？
停止問題みたいに，アルゴリズム的に決定不能な
問題が存在する．まずはそっちを勉強しろ．
0623１３２人目の素数さん2006/07/15(土) 05:06:57
>>567
いまだにNP完全とは何かを理解してないのねｗ
0624１３２人目の素数さん2006/07/15(土) 06:00:45
1は平面グラフのみを対象にしてたりするんじゃない？
0625１３２人目の素数さん2006/07/15(土) 14:47:03
平面グラフ限定でもNP-Completeなんだが
0626１３２人目の素数さん2006/07/17(月) 20:02:08
>>1は結局にげたのか。
0627１３２人目の素数さん2006/07/18(火) 18:17:26
やはり>>1の知識程度でTSPは無理だったか．
0628１３２人目の素数さん2006/07/18(火) 22:28:09
院を逃げ出したダメ人間の俺も、>>!みたいな発言をしてた時期はあった。

サボりたかったからで、マジに言ってたわけでは流石にないが。
0629１３２人目の素数さん2006/07/19(水) 03:41:01
>>628
>>1も何年か後にこのスレみたら恥ずかしいだろうな。
永久にWebに残骸として残ってしまうが、
自分でも回顧するための材料としてとっておくといいだろうね。
0630１３２人目の素数さんNGNG
巡回セールスマンってなんかやらしいよね
0631１３２人目の素数さん2006/07/19(水) 11:45:01
>>630
頭大丈夫か？
0632１３２人目の素数さん2006/07/19(水) 23:21:59
>>1完全敗北ｗ
063312006/07/21(金) 22:28:46
>>627
あなたの知識程度では可能なのですか？

>>628
つまりP=NPを謳いながらP≠NPを支持していたわけですね。

100000人のうち1人がP≠NPを支持し、
残りの99999人がP=NPを支持していたとしても、
自分はP≠NPが支持できるのか考えてみてください。

どう見てもあなたの発言はP=NP支持者に失礼です。

>>629
多くの人はP≠NPを支持し、そしてP=NP派を弾圧しているという重要な資料になるので保管させていただきます。

かつて電気は神などのみがなせる超常現象として扱われていたようであった。
しかし、ある人は電気を科学的に研究し、さまざまな科学的な根拠に基づく実験を人々に見せ、驚かせた。
だが、そのある人は政府から「人々を惑わす危険な者」として扱われた。
その後、ある人はつらい生活を強いられることになった。
今でこそ電気が当たり前であるから、今では誰もがある人を支持するだろう。
だがこれが江戸時代だったらあなたはどうしただろうか・・・。

>>632
完全である証明が無ければ妄想だとこのスレで誰かが言っていましたよ。
論文及び数学的な証明が必要になるみたいです。
0634１３２人目の素数さん2006/07/21(金) 23:28:55
>>633
( ´,_ゝ`)ﾌﾟｯ
0635１３２人目の素数さん2006/07/22(土) 00:41:59
>>633
君は歴史も勉強する必要がありそうですね．

> 100000人のうち1人がP≠NPを支持し、
> 残りの99999人がP=NPを支持していたとしても、
事実と反した仮定を挙げればどんな結論もありだね．
数学板でそんな有名な詭弁を挙げてもさぁ．
0636１３２人目の素数さん2006/07/22(土) 06:28:31
久しぶりにきたら、また>>1が変なこと逝ってる・・
0637１３２人目の素数さん2006/07/22(土) 16:27:53
絶対この1ネタだろ。
本物の1は気が狂って自殺してるよ。

有名な1の家来のコピぺとか思い出しちまった。
063812006/07/23(日) 00:34:24
>>635
詭弁であろうがなかろうが関係ない。
汝は周りの考えに惑わされること無く汝の理論に汝の思う正当性がある場合に、
その理論を捨てることの無い強さをを持っているのか、そうではないのかということを問うているのだ。
0639１３２人目の素数さん2006/07/23(日) 04:58:11
>>638
日本語でおｋ
0640１３２人目の素数さん2006/07/23(日) 21:14:58
>多くの人はP≠NPを支持し、そしてP=NP派を弾圧しているという重要な資料になるので保管させていただきます。
ちょ、どんどんトンデモ化してるんだが……
0641１３２人目の素数さん2006/07/24(月) 23:45:46
もとの>>1とは違うからね
新しい>>1よ
ネタを引き継いでくれるのは構わんが面白い書き込みをしてくれよ

今のところ相当つまらないから
0642１３２人目の素数さん2006/07/28(金) 18:03:53
900
064312006/07/28(金) 20:21:49
すみません。プログラム書き換えていて思ったのですが・・・。
私のアルゴリズムでは領域計算量がO(n^2)・・・厳密には総和。必要なんです。
つまり具体的にいうと1500都市くらいでメインメモリが足りなくなってしまうんです。
10万都市でも解けるなんて言ってごめんなさい。
だれかスーパーコンピュータ貸してくれませんか？
064412006/07/28(金) 21:03:47
ちなみに10万都市の場合
約240,002,400,000バイト
の領域が必要になる。

ハードディスクに書き出すようにすれば可能な範囲なのかもしれないが、それはマジ勘弁・・・。
064512006/07/28(金) 21:06:17
約1500都市でもいいかもな。。。
0646１３２人目の素数さん2006/07/29(土) 00:05:22
１テラのハードディスクも安くなってるから無問題。俺も使ってる。
064712006/07/29(土) 07:55:36
>>646
メインメモリに比べてかなり遅いように思われるが・・・。
0648１３２人目の素数さん2006/07/29(土) 08:34:14
ハードディスクに書き出すようにすれば可能な範囲って自分で言ってんじゃん
064912006/07/29(土) 08:44:31
それはマジ勘弁といっているではないか(遅いから)。
容量的には可能だ。
0650１３２人目の素数さん2006/07/29(土) 08:46:14
torrentファイルを使えば世界中のPCのHDDがおまえのものですが？
0651１３２人目の素数さん2006/07/29(土) 10:54:41
領域計算量がO(n^2)って，距離行列を記憶するためじゃないだろうな？
それなら，都市(i,j)間の距離が必要になるたびに計算するか，
頻繁に使われる都市間の距離はハッシュにでも覚えておけば良いのでは？
0652１３２人目の素数さん2006/07/29(土) 11:32:34
巡回テロリストマン問題
世界の主要都市の高層ビルを次々に爆破してゆくのに、最適なルートを
さがそう。ただし、爆破した都市は２度と通過してはいけない。
065312006/07/29(土) 12:37:43
>>651
あまりアルゴリズム自体に関することは言いたくないが、それは100%ちがうから安心して(だから安心できないのだが)。
私だったら距離ぐらいならその都度計算させてしまうかもしれない。
065412006/07/29(土) 12:46:48
ある特殊な経路をあらわすのさ・・・。
0655１３２人目の素数さん2006/07/29(土) 15:51:12
経路なんかO(n)で済むだろうが。
何をやろうとしてるんだ、このアホは？
065612006/07/29(土) 16:16:51
>>655
何をしているのか教えたいがこれ以上教えるとアルゴリズムを推測される恐れがあるから教えられない。
ちなみに経路というのは経路そのものを保存するという意味で言っているわけではない。
0657１３２人目の素数さん2006/07/29(土) 16:19:59
またDQN臭いこといってるのか・・・
0658１３２人目の素数さん2006/07/29(土) 16:25:16
要するに>>1のアルゴリズムは，
簡単に推測可能なチープなものだということだな．
065912006/07/29(土) 16:54:11
>>658
簡単に推測できるかどうかは推測しようとする人の脳の程度や経験の程度が大きく関係するでしょう。
0660１３２人目の素数さん2006/07/29(土) 18:29:05
アルゴリズムの計算量の解析は終わったんですか？
プログラムを組んだところでP=NPは証明できませんよ？
0661１３２人目の素数さん2006/07/29(土) 18:54:53
多項式時間で解ける事が証明されてなければ近似アルゴリズムじゃないし
近似度の解析ができてなければ安全性が保証出来ない

近似アルゴリズムだと主張するなら計算量理論ぐらい勉強したほうがいいと思うんだが
066212006/07/29(土) 19:04:36
一応言っておく。
私は今回のプログラムで解けなければＴＳＰをやめるつもりでいる。
もしも解けたならば>>660-661のいう証明及び計算理論に関する勉強もする予定だ。

私は今、今まで研究してきた時間のすべてをかけて最後の戦いに挑んでいるのだ。
半端な覚悟でやっているわけではない。
あまり茶化さないでくださいね。
0663１３２人目の素数さん2006/07/29(土) 19:12:54
馬鹿の考え休むに似たり
今まで長い間研究してきたと言っても教科書も読まない独学は無意味に近いからね。
066412006/07/29(土) 19:38:18
>>663
まず、自力で挑戦するってことは、いかなる場合においても大切なことだと思う。
なぜならば、自分の力だけで考えるということは、他人の理屈の影響を受けていない状態だけでしかできない醍醐味だから。
真っ先に他人の理論に洗脳されて生きてきた人間に私の考えが理解できるとは思えないが。

新聞にアメリカが悪いって書かれていたら皆が口をそろえて「アメリカが悪い」って言っている馬鹿共の発言みたいだ。
0665１３２人目の素数さん2006/07/29(土) 20:27:03
違うだろ．

君が言ってるのは重さによって物体が落下する速度が
変わるとか言ってる小学生か中学生みたいなもんで，
みんなは高校物理を勉強してから議論をふっかけてね
と言ってる程度の話に過ぎない．

自分の不勉強を人のせいにしてんじゃないよ．
自分の力だけでやりたいと言いつつ，スパコン貸せだ，良い教科書を
教えろだ，どれだけ支離滅裂なこといってんのか理解してるかい？

本当に自力でやりたいと言うなら，全ての結果が出てからレポートを
HPにアップロードするってのがスマートな人間のやることじゃないのか？
0666１３２人目の素数さん2006/07/29(土) 20:35:41
> 新聞にアメリカが悪いって書かれていたら皆が口をそろえて「アメリカが悪い」
> って言っている馬鹿共の発言みたいだ。

研究者の実態を知らないのに馬鹿にするのも止した方がよいよ．
どんな書籍・論文であれ，懐疑的・批判的な姿勢で読むのはまともな研究者の基本姿勢．
さんざん議論した，考え尽くした上で構築された，理論であり，理解なわけで，君が
考えるより量も質もはるかに高い．

ようするに君は自分にとって都合の良いことしか信じないわけで，そっちの方がよほど
性質が悪いとしか思えないけどね．
0667１３２人目の素数さん2006/07/29(土) 21:06:18
>>1はNP完全とは何かも知らずにP=NPだと主張するぐらいの神経の持ち主なんだから大目に見てあげないと
0668１３２人目の素数さん2006/07/29(土) 21:10:03
>もしも解けたならば>>660-661のいう証明及び計算理論に関する勉強もする予定だ。

って、チョット待てっw
066912006/07/29(土) 21:23:06
>>665
私は自分の不勉強を誰のせいにもしてませんよ。
解けなければそれは自分の責任です。
自己責任でやっているのですよ。
だからこそ私もそれなりにプライドをもって研究を続けてきたのですよ。
それを無意味などといい加減なことを言われたくないですね。

>スパコン貸せだ
あなたが私にスパコンを貸す気があったのでしたらその恩を傷つけたことを深く反省します。
>良い教科書を教えろだ
上を見ると私が「教えろ」と言った箇所は見当たりませんが・・・。
ですが本を紹介していただいたことはありがたく思いますよ。
今回の検証がうまくいったら購入しようと考えています。
ですが、私は現在の私のアルゴリズムの進行状況を迷惑がかからないように自分が立てたスレで実況しているだけですから、
本の理論を現在私がレスする必要はないように思えます。
067012006/07/29(土) 21:52:33
>>666
私の研究方法を押し付けるわけではないのでスルーしてもいいが。

昔ある一人の男がいた。
その男は授業に遅刻してしまった。
やっちまった・・・と思いながらも黒板に問題が書いてあったので
「これは宿題じゃないか。取り合えず宿題は分かったことだし不幸中の幸いだな」と思ってその黒板の問題を書き写して家に持ち帰った。
その問題をとくことは非常に困難であったが彼は何とかその問題を解くことに成功した。
そしてその問題を解いた次の日、彼はその問題が未解決の物であることを知らされる。
どうやら、その授業ではその問題が未解決の物だということを教えていたみたいなのだ。

彼がもしも遅刻しないで授業にちゃんと出席していたらその問題は未だかつて解けない問題となっていた可能性もある。

これが先入観が研究にもたらす悪影響である。

議論するだの質も量も高いのも結構ですが、確証も無く・・・・・やっぱやめた。逆切れされたくないから。怒らないでくださいね。私がすべていけませんでした。ごめんなさい。
0671１３２人目の素数さん2006/07/29(土) 21:59:38
>>664
> 自力で挑戦するってことは、いかなる場合においても大切なことだと思う。
全然違う。
以前からそこに君の勘違いがあるのだと指摘されていたと
記憶しているが。
0672１３２人目の素数さん2006/07/29(土) 22:01:56
>>670
ダンツィークのことか？
その統計学の未解決問題と、
さんざん研究され尽くしているTSPを
天秤にかける意味がよくわからんのだが。
067312006/07/29(土) 22:02:30
>>671
果たしてぜんぜん違うと言い切れるだろうか。
私の研究方法を押し付けるわけではないのでスルーしてもいいが。

昔ある一人の男がいた。
その男は授業に遅刻してしまった。
やっちまった・・・と思いながらも黒板に問題が書いてあったので
「これは宿題じゃないか。取り合えず宿題は分かったことだし不幸中の幸いだな」と思ってその黒板の問題を書き写して家に持ち帰った。
その問題をとくことは非常に困難であったが彼は何とかその問題を解くことに成功した。
そしてその問題を解いた次の日、彼はその問題が未解決の物であることを知らされる。
どうやら、その授業ではその問題が未解決の物だということを教えていたみたいなのだ。

彼がもしも遅刻しないで授業にちゃんと出席していたらその問題は未だかつて解けない問題となっていた可能性もある。

これが先入観が研究にもたらす悪影響である。

議論するだの質も量も高いのも結構ですが、確証も無く・・・・・やっぱやめた。逆切れされたくないから。怒らないでくださいね。私がすべていけませんでした。ごめんなさい。
0674１３２人目の素数さん2006/07/29(土) 22:06:13
>>673
なんでダンツィークの下りを二回書く必要がある？
更に、そんな誰でも知ってる有名な下りを引用することに
何の意味があるんだ？
067512006/07/29(土) 22:10:31
>>672
ようは自力でやると意外な発見があるって事ですよ。
そして研究され尽くしたＴＳＰだからこそ、そのような意外な発見があったら効果的だと思えるからです。
0676１３２人目の素数さん2006/07/29(土) 22:11:34
>>674
ようは自力でやると意外な発見があるって事ですよ。
そして研究され尽くしたＴＳＰだからこそ、そのような意外な発見があったら効果的だと思えるからです。
067712006/07/29(土) 22:12:42
ようは自力でやると意外な発見があるって事ですよ。
そして研究され尽くしたＴＳＰだからこそ、そのような意外な発見があったら効果的だと思えるからです。

名前付け忘れますた
067812006/07/29(土) 22:13:44
>>674←つけわすれますた
ようは自力でやると意外な発見があるって事ですよ。
そして研究され尽くしたＴＳＰだからこそ、そのような意外な発見があったら効果的だと思えるからです。
0679１３２人目の素数さん2006/07/29(土) 22:19:28
何も成していないくせに口だけは立派な>>1が
自分とダンツィークを同列においていることに嫌悪を感じる
068012006/07/29(土) 22:23:13
>>679
これで許して。

ダンツィーク>>1
0681１３２人目の素数さん2006/07/29(土) 22:29:12
それはたまたま、未解決問題がスカだっただけじゃないの。
フェルマーは３００年目にあたりになっただけ。
0682１３２人目の素数さん2006/07/29(土) 22:33:44
>>678
お前にいい言葉を教えてやろう。
ニュートン「私がより遠くを見渡せたのは、巨人の肩に乗ったからだ」

ダンツィークの統計学への貢献を
適当に考えたみたいにいうな。
彼は基礎理論をしっかりと勉強していたの。
お前なんかと一緒にするとバチがあたるぞ。
0683１３２人目の素数さん2006/07/29(土) 22:37:41
今度はDantzigまで引き合いに出してるのかよ．
一体何様のつもりだか．
0684１３２人目の素数さん2006/07/29(土) 22:47:01
>>1のトンデモ発言もキレがなくなってきたな
0685１３２人目の素数さん2006/07/29(土) 22:48:17
まあ猿がタイプライターを叩いてハムレットが出来上がる可能性もあるんだから
>>1がキーボードを叩いて凄い論文が出来上がる可能性もゼロじゃないよ
0686１３２人目の素数さん2006/07/29(土) 22:49:07
>>1の言う「自己責任」は意味がおかしい気がする……
誰かの研究を引き合いに出して、その結果得られた結論が間違っていたとしても、
先行研究者の責任にはならないよ？
0687１３２人目の素数さん2006/07/29(土) 22:49:18
ダンツィークって読みなの？
0688１３２人目の素数さん2006/07/29(土) 22:49:32
>>685
歴史上、猿が詩を書いたことすら
まだ1度も起きてないがなｗ
0689１３２人目の素数さん2006/07/29(土) 22:50:59
>>687
そう。
たしかロシア系アメリカ人だったかな
0690１３２人目の素数さん2006/07/29(土) 22:52:29
最適解がでなければ、そのアルゴリズムはスカだと見たほうが正解です。
ヒューレリステイックを高速化するかハードをいじくって並列で高速化する以外にないです。
考えられるのはセチのネットワークで最適解を計算できればそれでじゅうぶんです。
0691１３２人目の素数さん2006/07/29(土) 22:56:06
ふーん
1500都市ねえ
>>1で言ってた50くらいのサイズは解けたのか？>>1よ
069212006/07/29(土) 22:57:01
>>686
悪いけど意味が分からない。
自分で勝手に始めた研究が失敗したらそれは自分の責任だろうと言ったつもりなのだが。
069312006/07/29(土) 22:59:03
>>691
いやだからそうじゃなくて、
拡張後はたぶん真っ先にeil51を検証するけど、
取り合えずプログラムできなければだめでしょ？
0694１３２人目の素数さん2006/07/29(土) 23:02:36
>>689
㌧
競走馬の方はドイツ読みかな？
0695１３２人目の素数さん2006/07/29(土) 23:06:16
社会に出てからは結果が求められるけど>>1はまだ学生なんだから結果なんて気にせずに
色々頭を使って考える事は良いことだよ。卒論修論には使えないけどね
069612006/07/29(土) 23:10:30
>>695
もしもいい結果が出たら卒論にするね。
0697１３２人目の素数さん2006/07/29(土) 23:11:56
>>693
なんだまだ出来ていないのにメモリの心配などしていたのか
皮算用というかなんというか。おめでたい人ですね＾＾
0698１３２人目の素数さん2006/07/29(土) 23:14:02
べつに学問的な価値などがなくてもプログラム組んでその結果をグラフにするだけで
最近は卒論として認められたりするのでいい結果がでなくても卒論に出来ますよ。どうせ学内審査だけですし
0699１３２人目の素数さん2006/07/29(土) 23:34:45
>>696
やっと卒論レベルのゴミだと気がついた？
それと，>>682のいうことって大事だと思うが．
0700１３２人目の素数さん2006/07/29(土) 23:45:49
>>694
競馬馬ってダンツィグ？
古いなｗｗｗ
0701１３２人目の素数さん2006/07/29(土) 23:57:08
競走馬でもダンツィヒと読むだろ？sage
0702１３２人目の素数さん2006/07/29(土) 23:57:50
変なとこにコピペしてたww
0703１３２人目の素数さん2006/07/30(日) 02:54:36
どんな研究でも、過去の延長線上にあるということが大事なんだが、
なぜ>>1はそれが分からないのだ？
ゆとり教育だな・・・
0704１３２人目の素数さん2006/07/30(日) 05:56:25
>>703
分かってたらこんなトンデモ発言ばかりしないだろうよ。
070512006/07/30(日) 09:32:12
>>698
マシンの性能を第一に考えなければまともなプログラムなんてまず作れないと思いますが（今のマシンはハイスペックだから些細なプログラムを作るくらいなら気にしてない香具師も多いのかもしれないが。）。
かつては、80年代ではメモリが高価だったから長いプログラムを書くことすら許されなかったみたいだ。

マシンの性能不足を知りながらとりあえずプログラムを作り、またプログラムを書き換えるなんてことはあまりしたくないので。

量子コンピュータ用のプログラム製作中の人に「なんだまだ出来ていないのに量子コンピュータの心配などしていたのか」とは言えるだろうか。
私のプログラムでは現在主流のハードディスク並みのメインメモリが必要で、その問題が解決できなければ都市数が大幅に少なくなってしまうというのは紛れもない事実なのだ。
070612006/07/30(日) 09:33:01
訂正
>>697
マシンの性能を第一に考えなければまともなプログラムなんてまず作れないと思いますが（今のマシンはハイスペックだから些細なプログラムを作るくらいなら気にしてない香具師も多いのかもしれないが。）。
かつては、80年代ではメモリが高価だったから長いプログラムを書くことすら許されなかったみたいだ。

マシンの性能不足を知りながらとりあえずプログラムを作り、またプログラムを書き換えるなんてことはあまりしたくないので。

量子コンピュータ用のプログラム製作中の人に「なんだまだ出来ていないのに量子コンピュータの心配などしていたのか」とは言えるだろうか。
私のプログラムでは現在主流のハードディスク並みのメインメモリが必要で、その問題が解決できなければ都市数が大幅に少なくなってしまうというのは紛れもない事実なのだ。
070712006/07/30(日) 09:36:48
>>699
成功したらチューリング賞レベルな気がするが・・・。
0708１３２人目の素数さん2006/07/30(日) 09:57:13
>>707
そういう気になっている人は人生タン、今井大先生、sikiタン等、ネットにはたくさんいらっしゃいます。
>>1タンもその仲間入りでつね。
0709１３２人目の素数さん2006/07/30(日) 12:57:26
>>706
都合の悪いことは聞こえない耳のようだな。

君が批判されているのは、マシンの性能不足とか関係ないのだよ。
君より腕のいいプログラマなら、効率よく実装するかも知れないしな。

それより問題なのは、
「正しい計算量の推定」と「過去の研究との位置づけ」だ。
特に君は後者がゴッソリ抜け落ちているから
正しいのか誤りなのかの判断が全くできない。
これでは科学ですらない。

どうせ顔も見えない相手につまらない意地を張るヒマがあったら
どんどん意見を受け容れて改良するほうが
よほど生産的だと思うがどうか？
0710１３２人目の素数さん2006/07/30(日) 13:02:30
釣りスキルひくいなあ・・・ま一応全力で釣られてみるか

>>706
プログラムとアルゴリズムの区別もつかないのかこの屑は
0711１３２人目の素数さん2006/07/30(日) 14:21:12
以下のプログラム (テンプレート) および例題データでは，

都市数
都市1 の x 座標と y 座標
都市2 の x 座標と y 座標
　　　　　　：
　　　　　　：
という形式で問題が記述されているものとする．
071212006/07/30(日) 16:53:10
>>709
>君より腕のいいプログラマなら、効率よく実装するかも知れないしな。
絶対にそういうわけではないだろう。

>これでは科学ですらない。
そうだ科学の常識を超えたハイレベルな世界なのだ。

>どんどん意見を受け容れて改良するほうが
>よほど生産的だと思うがどうか？
その通りだが、参考になりそうな意見がなかなかでないんだよな・・・。
071312006/07/30(日) 17:00:20
>>710
おまえもしかして
>量子コンピュータ用のプログラム製作中の人に「なんだまだ出来ていないのに量子コンピュータの心配などしていたのか」とは言えるだろうか。
に突っ込みたいの？
そうだとしたら、量子コンピュータが完成したとしたらプログラムが使えなくてアルゴリズムでしか動かない訳だな。初耳だ。
どうやってそのアルゴリズムを入力するんだろうね？プログラムを使わないで。
07141 ◆salse0FDac 2006/07/30(日) 17:07:29
現在のプログラムの完成度：約３０％
0715１３２人目の素数さん2006/07/30(日) 18:42:58
>>712
だから本当に都合のいい耳だな。
過去の研究を調べろっての。

その上で、優位性や弱点の検討をまず行いなよ。
0716１３２人目の素数さん2006/07/30(日) 18:48:14
>>713
> ～に突っ込みたいのか？

たとえ話には興味なし
実装の話をしてるけどアルゴリズムは完成したのかと聞いている
0717１３２人目の素数さん2006/07/30(日) 19:58:58
>>716
てか、>>1の国語力が低すぎて
議論にならないんだよな・・・
わざと曲解するにしろ、もう少しうまくやってほしい。
07181 ◆salse0FDac 2006/07/31(月) 00:10:22
>>715
だからそれは自分のアルゴリズムを検証してからでいいでしょ？

>>716
まだだといっているではないか。>>714

>>717
>>710の「プログラムとアルゴリズムの区別もつかないのかこの屑は」という発言から
>>706内にプログラムとアルゴリズムの区別を履き違えた点があることが読み取れるがそこはどこなのだ？
一番可能性が高いのが量子コンピュータ用のプログラムのことだと思ったのだが・・・。
もしかして量子アルゴリズムどうこう言いたいのだと思ってね。
07191 ◆salse0FDac 2006/07/31(月) 00:14:15
現在のプログラムの完成度：約35％

自信満々でテストしないで500行くらい書いたら意外とバグだらけでバグ取りに膨大な時間がかかってしまった・・・。
俺もまだ未熟なのか・・・。
0720１３２人目の素数さん2006/07/31(月) 01:14:01
>>718
> だからそれは自分のアルゴリズムを検証してからでいいでしょ？
全然分かっていないな
0721１３２人目の素数さん2006/07/31(月) 01:14:43
>719
プログラムを完成して，ベンチマーク問題例に対して実行して最適解が得られて，
都市数と計算時間の関係をグラフにプロットして，最小２乗法で曲線を当てはめて，
曲線が多項式関数になったとしよう．
それで，それが君の提案するアルゴリズムが多項式時間アルゴリズムだと言うことの
証明になるとか思ってるんじゃないだろうな？

まあ，思ってるからこそプログラムをシコシコ書いているんだろうが・・・南無
0722１３２人目の素数さん2006/07/31(月) 01:21:29
提案するアルゴリズムがTSPに対する多項式時間アルゴリズムかどうか
検証するには，プログラムを実装する必要なんてない．

Step1:アルゴリズムを正確に記述する．
Step2:記述したアルゴリズムがTSPの任意の問題例に対して，
(1)問題例の入力サイズの多項式時間で停止する，
(2)最適解を出力する，
ことを証明する．

これだけ．
0723１３２人目の素数さん2006/07/31(月) 01:23:41
あと，(3)使用する記憶領域が問題例の入力サイズの多項式オーダで収まる，
ことも示さないといかんかったね．
0724１３２人目の素数さん2006/07/31(月) 10:55:28
>722-723
(1)から(3)も言えるんじゃないか.
0725１３２人目の素数さん2006/07/31(月) 15:28:36
1は今まで
あるソーティングアルゴリズムが、入力データを正しくソートするアルゴリズムであるということの証明
や
そのソーティングアルゴリズムの時間計算量が平均的に××であることの証明
を読んだり、自分で証明を導いたりしたことがあるのだろうか？
ひょっとして、そのアルゴリズムを実装したプログラムに「サンプルデータ」を入力して、その出力がソートされていれば
それがアルゴリズムが正しく動作することの証明になったり、計算量が××であるという評価が得られたりするのだと
思ってるんじゃないだろうか？

従来より優れたアルゴリズムを提案したいというのに、従来のアルゴリズムがどの程度の性能なのか調べようとしないというのも謎
0726１３２人目の素数さん2006/07/31(月) 16:44:32
>724
ごめん，寝ぼけてました．
07271 ◆salse0FDac 2006/07/31(月) 19:52:55
>>725

>その出力がソートされていれば
>それがアルゴリズムが正しく動作することの証明になったり、計算量が××であるという評価が得られたりするのだと
>思ってるんじゃないだろうか？

思っていから。
だが、実際にサンプルデータを入れて間違った結果になれば間違っている証明になるだろ？
仮に正しい結果が出力されれば正しいアルゴリズムである可能性が残る。そうなった場合には数学的な証明に取り掛かる予定だと言っているのだ。
0728１３２人目の素数さん2006/07/31(月) 20:12:32
>>727
日本語でおｋ
0729１３２人目の素数さん2006/08/01(火) 04:25:18
>>727
鳥つけて調子乗ってるとこ悪いけど芸風がまったく変わらず詰まらないよ

とりあえずねアルゴリズムができていないのに実装とかｱﾌｫかと
やっぱりプログラムとアルゴリズムの区別ついてないじゃねーか
07301 ◆salse0FDac 2006/08/01(火) 13:39:24
>>729
アルゴリズムならできているぞ。
今回は依然話したアレ（話したらキレられたからあえて言わない）を導入することによりあるパターンを抽出するアルゴリズムを作っている。
そこであるパターンがどのようなテストデータにも見られた場合そのパターンをアルゴリズムに組み込むことで多項式時間で解けるアルゴリズムが完成するという寸法。
イメージ掴めたか？別に掴んでもらわなくていいけど。
07311 ◆salse0FDac 2006/08/01(火) 13:40:51
揚げ足取られる前に訂正。
>>729
アルゴリズムならできているぞ。
今回は依然話したアレ（話したらキレられたからあえて言わない）を導入することによりあるパターンを抽出するアルゴリズムによりプログラムを作っている。
そこであるパターンがどのようなテストデータにも見られた場合そのパターンをアルゴリズムに組み込むことで多項式時間で解けるアルゴリズムが完成するという寸法。
イメージ掴めたか？別に掴んでもらわなくていいけど。
07321 ◆salse0FDac 2006/08/01(火) 13:47:07
誤解される可能性があるためさらに訂正。
>>729
アルゴリズムならできているぞ。
今回は依然話したアレ（話したらキレられたからあえて言わない）を導入することによりあるパターンを抽出するアルゴリズムを基にプログラムを作っている。
そこであるパターンがどのようなテストデータにも見られた場合そのパターンをアルゴリズムに組み込むことで多項式時間で解けるアルゴリズムが完成するという寸法。
イメージ掴めたか？別に掴んでもらわなくていいけど。
0733１３２人目の素数さん2006/08/01(火) 13:48:35
>>731
根本的に間違った考え方を指摘することを
揚げ足取りとは言わない．
0734１３２人目の素数さん2006/08/01(火) 13:49:16
>>732
まずは日本語の勉強をするべきなのではないだろうか．
0735１３２人目の素数さん2006/08/01(火) 14:56:35
>>718でアルゴリズムはまだ出来ていないって言ってるんだけどｗ
実装をはじめたのは>>718より前だよね？あれーおかしいね＾＾
07361 ◆salse0FDac 2006/08/01(火) 15:21:55
>>735
>>716にまだできていないと言ったのはプログラムがまだできていないという意味。
アルゴリズムができていないのにプログラムが完成する分けないだろ？
そんな状態でプログラムを組むことがほぼ意味が無いことは言うまでもない。
だから>>716がプログラムと書きたかった物をアルゴリズムと間違って書いたのではないかと思って気を遣ってあげただけだ。

ちなみに誤解を恐れずに言えばプログラムはアルゴリズムだ。
プログラムという物はアルゴリズムをコンピュータ上で実行できるように記述された物であり、プログラムの内容が示す物はアルゴリズムである。
0737１３２人目の素数さん2006/08/01(火) 19:15:38
ニコラス・ヴィルト「プログラム＝アルゴリズム＋データ構造」
0738１３２人目の素数さん2006/08/01(火) 21:02:54
その「パターン」がどのインスタンスも持っている、という事実は
>>1 が示さなきゃいけないことなんだぞ。
テストデータにいくらパターンがあっても、
それじゃ証明にはなってない。
07391 ◆salse0FDac 2006/08/05(土) 22:54:34
==検証結果==
プログラムが完成したので現時点での検証結果を発表する。

まずeil51の最短距離であるが、これは短縮には成功したもの、TSPLIB上にある最短距離と一致及び更新することはできなかった。
抽出したパターンには弱い相関が観られるが、確実性を得るには十分な分析が必要になるだろう。

以前のデータ
http://read.kir.jp/file/read54389.bmp
距離=436.335512

新しい経路
http://read.kir.jp/file/read54388.bmp
距離=432.162168

つまり、これが事実ならば私の研究は失敗に終わったことになる。


し　か　し　、　疑　問　点　が　有　る　。

まず一つ目だが、TSPLIB内のデータは本当に正しいのか、はたまた私が見間違えていないのかということ。
bayg29という問題に注目してもらいたい。
http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsp/bayg29.tsp
ここのDISPLAY_DATA_SECTIONという項目の
3番目のデータと25番目のデータ間の距離を計算してみたが片道だけで約1796.552254になる。
これはすべての都市間を結んだ現在最短距離とされている1610よりも長く矛盾している。
つまり、eil51についても私の見間違いかTSPLIB内のデータがおかしいためにTSPLIBのデータよりも長い結果算出された可能性がある。

私のプログラムが算出したbayg29の経路
http://read.kir.jp/file/read54390.bmp
距離=9323.955190
現在最短経路の約5.791276516倍らしい。
これを各都市間の経路を繋ぎかえるだけで約17.2673502%まで下げられる人が世界には居るのだろか・・・。(居るから結果が出ているのか？)
0740１３２人目の素数さん2006/08/05(土) 23:11:22
距離を座標から計算してるからだろ。
EDGE_WEIGHT を使えばいいんじゃない？

後、仮に　１６１０の数字が誤りだったとしても、
best known のルートが公開されてるんだから、
それと比較すればいいだけでしょ。

しかし、近似比５．７ってのはひどいな。
0741７４０2006/08/05(土) 23:13:33
ああ、そうか。５．７倍ってのは、
間違った距離情報を使ったから出ただけか。

失敬。
07421 ◆salse0FDac 2006/08/05(土) 23:13:54
次に二つ目だが、計算が非常に速かったこと。
私の予測ではeil51の場合約21時間もの時間が必要になるはずであったが、約5秒で計算が終わった。
プログラムを何度も確認したがバグは見つからなかった。
もしもバグならばさらに記録が更新できる可能性も有る。



がんばったな>>1・・・。
07431 ◆salse0FDac 2006/08/05(土) 23:21:07
>>740
明らかに29都市以上あるが・・・見方が良く分からんニダ。

有る1都市から他の都市への距離が示されているとか？

私のプログラムには未対応であります。
07441 ◆salse0FDac 2006/08/05(土) 23:26:29
>best known のルートが公開されてるんだから、
>それと比較すればいいだけでしょ。

よろしければそのサイトのURLを戴きたいのですが。
軽く探してきましたがそれらしいのが見つからなくて・・・。
0745１３２人目の素数さん2006/08/05(土) 23:39:09
どこ探してんだよ。。。
http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsp/bayg29.opt.tour

。。。やさしいな。俺。

ついでに説明してやると、EDGE_WEIGHT のほうは、
各頂点間の距離を表す行列な。
DISPLAY_DATA は、画像を出力するときにだけ使うものであって、
これで距離を計算しちゃうと、EDGE_WEIGHT の距離とは結構ずれてしまう。
つまりお前が解いてる問題は皆が解いてる問題とは別物ってことだ。
だからお前の解とbest known とを厳密には比較することはできない。
07461 ◆salse0FDac 2006/08/05(土) 23:47:37
どうもです>>745。。。

opt.tourって最短経路ことだったのか・・・知らなかった。
0747１３２人目の素数さん2006/08/07(月) 02:54:17
TSPLIB
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

たしか，TSPLIBのデータでは，数値誤差の問題を避けるため，
都市間の距離を実数値の切上げて得られる整数値としなさいと言うことが
マニュアルに書いてあったような気が・・・
また，問題例によっては距離の定義が異なり，ユークリッド距離以外のものも
あったような気がする．

何にせよ，おかしいとか言う前にマニュアル嫁と
07481 ◆salse0FDac 2006/08/07(月) 21:25:23
eil51はopt.tuorよりも短い経路があることが分かった。数学的な証明をする用意もある。
(私のプログラムが間違っていなければ。ちなみに現在のプログラムで最短経路が出せたわけでもない。)

以前話したパターンだがいい結果があがってきた。
そのパターンはどうも私が分割したあるグループ数が多くなれば多くなるほど、あるパターンに収束するみたいなのだ。
実際にどのように収束しているのかを調べるには残念ながらマシンのスペックが足りなくてできない。
だが、これは都市数が多くなればなるほど逆にとくことが楽になる可能性を示唆している。

つまりこんな感じになるかも。
都市数　(1～20程度)　(20～100程度) （100～）
解き易さ　　　楽　　　　　　　大変　　　　　　　楽

私のプログラムの誤差を回避できる可能性も見つけた。これはほんの可能性にか過ぎないからあまり期待しないでほしいが・・・。
上の楽とか大変とかもこの誤差が回避できることが前提。

私の研究は実は世界一進んでいるのかも・・・とか錯覚しそうだお。
0749１３２人目の素数さん2006/08/07(月) 23:16:45
錯覚ってｗ
0750１３２人目の素数さん2006/08/08(火) 00:21:46
妄想の間違いだろ
0751１３２人目の素数さん2006/08/08(火) 00:53:34
>747
だから，TSPLIBのマニュアルに示された距離の定義と違う距離を用い
ても意味がないんだってば．

opt.tourの最適解は，分枝限定法で得られた厳密な最適解なんだから，
それより短い解があるわけなかろう．
0752１３２人目の素数さん2006/08/08(火) 00:58:33
> eil51はopt.tuorよりも短い経路があることが分かった。
TSPLIBのマニュアルでは，eil51の最短巡回路長は426と書いてあるが，
君の見つけた最短巡回路の長さはいくらなんだ？
0753１３２人目の素数さん2006/08/08(火) 01:06:00
TSPLIBのマニュアルを読むと，eil51の距離関数はEUC_2Dとなっている．
計算方法については，都市iの座標を(x[i],y[i])とすると，
都市(i,j)間の距離dijは，
xd = x[i] - x[j];
yd = y[i] - y[j];
dij = nint(sqrt(xd * xd + yd * yd));
と計算すると書いてある．ここで，nint()は四捨五入を行って，
整数値に丸める関数らしい．原文では，
Since distances are required to be integral, we round to the
nearest integer (in most cases). Below we have used the rounding
function "nint".
と書いてある．
0754１３２人目の素数さん2006/08/08(火) 02:08:41
>>748
> eil51はopt.tuorよりも短い経路があることが分かった
ﾊﾗｲﾃｰｗｗｗｗｗｗｗｗ
0755１３２人目の素数さん2006/08/08(火) 12:24:52
最適解よりいい解が求まったなどという発想自体どうかしてるｗ
素人以下
07561 ◆salse0FDac 2006/08/08(火) 12:48:06
http://sakuratan.ddo.jp/uploader/source/date19619.bmp

赤い線はopt.tour
緑の線は私のアルゴリズムの結果を表している。

左上のアルファベットを振ってある箇所を見ていただきたい。
この場合opt.tourは→A→B→D→C→という経路を描き、
私のアルゴリズムは→A→D→B→C→という経路を描くことを表している。

わたしのアルゴリズムには現在調整のために全体の経路から都市を一つ取り出し、その都市を最適な距離で接続するという簡単な誤差訂正処理が入っている。
つまり、この処理は都市Dを取り出し→A→B→C→としたところに都市DをA→B間とB→C間のどちらに接続した方が短い距離が得られるか判断し、接続しなおす処理も入っているということである。

つまり→A→B→D→C→と接続するよりも→A→D→B→C→と接続した方が短いってことだ。
整数型で計算したわけではないけどさ・・・。
0757１３２人目の素数さん2006/08/08(火) 13:06:57
>>756
> つまり→A→B→D→C→と接続するよりも→A→D→B→C→と接続した方が短いってことだ。

どれだけの距離短いかも書かずに「つまり」はねーだろｗｗ
07581 ◆salse0FDac 2006/08/08(火) 13:15:24
>>757
拡大して定規当てれば一目瞭然。
A→B→D→C：26.9cm
A→D→B→C：26.4cm
0759１３２人目の素数さん2006/08/08(火) 13:18:11
問題はこれ？
http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsp/eil51.tsp
その4点の座標は？
0760１３２人目の素数さん2006/08/08(火) 13:18:12
定規・・・。
07611 ◆salse0FDac 2006/08/08(火) 13:39:22
10,17 at No.41・・・Ａ
5,6 at No.40・・・Ｄ
13,13 at No.19・・・Ｂ
21,10 at No.42・・・Ｃ

だと思うたぶん。

ついでに俺がこの場で距離を求めて世界一早くeil51の最短経路に気づいた人になってやる。
A→B→D→C：32.12256832
A→D→B→C：31.25719553

やっぱり俺の経路の方が短いじゃないか？
最短経路なんてちゃんちゃらおかしい。ｗ
0762１３２人目の素数さん2006/08/08(火) 13:50:12
>>761
残念、それはお前のぬか喜びだｗ
>>753で計算してみ
0763１３２人目の素数さん2006/08/08(火) 15:36:52
ｗｗｗｗ
0764１３２人目の素数さん2006/08/08(火) 17:24:43
おまえなぁ。
お前の解と opt tour との厳密な比較はできない、
って言っただろ。

とりあえず round 関数で丸めてみろ。
07651 ◆salse0FDac 2006/08/08(火) 17:35:50
私の提唱する距離の方が短いことは紛れもない事実なのです。
ルールにとらわれているから新の解が見えないのですよ。

それに私は「これが最適解なんです。」なんていって突きつけられた経路を鵜呑みにできるほど軽率ではありません。
ですから最適解を疑っただけで素人以下などといわれたくありませんし、すぐに鵜呑みにしてしまう方が素人なのだといいたいです。

私が求める物は真の解だけです。偽者は要りません。
0766１３２人目の素数さん2006/08/08(火) 17:39:02
今の1って偽者だろ。今回の偽者は結構レベル高いな。
0767１３２人目の素数さん2006/08/08(火) 17:41:30
低いでしょー。>>765で、もうこの>>1はダメ。
つぎの>>1さんﾄﾞｿﾞｰ
0768１３２人目の素数さん2006/08/08(火) 17:43:03
ダメだからだろ。ｗ
0769１３２人目の素数さん2006/08/08(火) 20:43:49
そうか？結構レベル高いと思うぞ。独自の定義を使って理論値を超えちゃうところとか
既にトンデモの最終段階だろ。あとは俺の定義のほうが正しい、既存の定義が間違ってるんだ
と主張し始めるだけで解脱できる
0770１３２人目の素数さん2006/08/11(金) 18:25:29
ていうか>>1は何で一分もかからないような計算をしてみないんだろう……
0771１３２人目の素数さん2006/08/11(金) 18:29:04
>>770
一分もかからない計算を一ヶ月かけることで、
一ヶ月の間>>1は自分の中で世界一の天才でいられるからだろうさ。
0772１３２人目の素数さん2006/08/12(土) 13:54:44
確かに今回の>>1の行動はちょっと気味が悪い。
ただ単純に面倒くさくて計算しないだけなのかと思いきや
>>761で何故か丸めない場合の値を出してるし。
計算の手間としてはどちらも変わらないのに。
わざと現実を直視しないようにしているとしか思えないな。
0773１３２人目の素数さん2006/08/12(土) 17:45:16
点間距離まで含めて、平面上に描けるグラフの
問題しか解けないアルゴリズムなんじゃない？
07741 ◆salse0FDac 2006/08/13(日) 14:33:03
ふと思ったけど俺ってセールスの綴り間違ってるな。
0775１３２人目の素数さん2006/08/13(日) 14:56:51
コテなんだからいんじゃない？
0776１３２人目の素数さん2006/08/14(月) 02:50:52
ハミルトン閉路問題が多項式時間で解けるか解けないかが証明できれば100万ドルもらえるの？
僕頑張っちゃうもんね☆
07771 ◆salse0FDac 2006/08/17(木) 11:22:49
新型誤差訂正制御を行った結果
http://sakuratan.ddo.jp/uploader/source/date20222.bmp
距離=441.993007

誤差訂正を行ったはずがむしろ距離が長くなってしまった・・・。

いよいよ追い詰められた感じだ。
0778１３２人目の素数さん2006/08/17(木) 11:29:27
いよいよって・・・。
0779１３２人目の素数さん2006/08/17(木) 12:53:50
2色png化すればたった3.5kB程度になる画像を300倍近い1MBのBMPにしていることにだれも突っ込んでないのね。
ファイルサイズの最適化もできないようでは、経路の最適化もできないわな。
07801 ◆salse0FDac 2006/08/17(木) 13:23:26
>>779
つまりファイルサイズの最適化と経路の最適化の間に強い関係があるわけだな。
どのような関係があるのかレポート求む。
0781１３２人目の素数さん2006/08/17(木) 21:42:06
単に足し算が出来ない馬鹿は方程式が解けないってことじゃね？
07821 ◆salse0FDac 2006/08/18(金) 17:42:58
>>777はプログラムには原因不明のバグがあるために私のイメージした処理が行われていなかったことがわかりました。

取りあえず旧式アルゴリズムの結果をpngで
http://sakuratan.ddo.jp/imgboard/img-box/img20060818173430.png
距離は432.162168です。
07831 ◆salse0FDac 2006/08/18(金) 17:44:57
>>756の結果はメモリの確保が足りなかったため、私の意図した結果が得られていない。
0784１３２人目の素数さん2006/08/18(金) 18:33:52
まだ距離計算の定義違ったままだしｗｗｗｗ
07851 ◆salse0FDac 2006/08/18(金) 23:30:01
新プログラムのバグがなかなか見つからないので旧プログラムを見直していたらバグ発見！！
早速直したところ未知なる最短経路を発見した。

http://sakuratan.ddo.jp/uploader/source/date20326.png
距離は428.981647です。

実数型でこの距離だ。
私は神の領域に足を踏み入れてしまったのだろうか・・・。
0786１３２人目の素数さん2006/08/19(土) 13:56:55
>>785
> 未知なる最短経路
じゃ単なる経路だろ
07871 ◆salse0FDac 2006/08/20(日) 00:11:01
>>786
自己新記録という特別な経路なのです。
0788１３２人目の素数さん2006/08/20(日) 00:13:05
>>787
お笑いに走るようになったのか？
今までのように、マジレスっぽいトンデモの方が面白かったのだが。
07891 ◆salse0FDac 2006/08/20(日) 00:18:36
というかさっき５時間半もかけてパターン抽出のシミュレートをしたが収束するどころか思いっきり拡散しているし・・・。（微妙に特徴は見られるんだよ。）

もう引き際かもな・・・。

ランダムな70都市間の最短経路？
http://sakuratan.ddo.jp/uploader/source/date20387.png
07901 ◆salse0FDac 2006/08/20(日) 00:32:09
なるほど。やっぱりそういうことか。

やっと読めたぜ。パターンが。

新アルゴリズム改ができた。

計算量は下がるし、アルゴリズムもシンプルになるしいいことばかりだ。
0791１３２人目の素数さん2006/08/20(日) 00:43:12
>>789-790
そんなゴミデータ見せられても訳わかんねーよ
新しい>>1に期待するから、お前とそのトリップ引っ込めろ。
お前面白くない
07921 ◆salse0FDac 2006/08/20(日) 00:49:22
>>791
訳分からないのはあなたの知能が足りていない事が原因である可能性が高いです。
それに私はウケ狙いでスレ立てたわけでもレスしているわけでもありません。
そのようなことを期待しているのでしたらスレ違いです。
まあ、巡回セールスマン問題に興味のない人にとってはつまらないスレであることは認めますが・・・。
0793１３２人目の素数さん2006/08/20(日) 07:02:31
>>792
君はちょっと面白いかも
0794１３２人目の素数さん2006/08/20(日) 07:21:47
TSP=NPの証明
TSPは素数番目の街を先に通ることー＞NP問題
0795１３２人目の素数さん2006/08/20(日) 07:57:51
>>792
その割には科学的に研究しておられないようですね。
0796１３２人目の素数さん2006/08/20(日) 09:34:39
>>795
ネタだからなｗ
07971 ◆salse0FDac 2006/08/20(日) 10:11:08
>>795
とりあえず科学的どうこう言うよりも可能性を探すことが先決。

あなたはCRCという誤差訂正方式を知っているだろうか？

この方式は数学者達は数学的な根拠が乏しい物として非難しているが、

事実非常に信頼性が高いということで現在主流の誤差訂正法として使われている。

つまり、理屈どうこうよりも、結果が重視されたわけだ。

とりあえず結果が出せそうなアルゴリズムを思いついたら理屈をあまり考えず試すさ。
0798１３２人目の素数さん2006/08/20(日) 10:57:09
>>797
適当なことばっかいうな。
CRCは低コスト(←重要)なバーストエラーの検出として普及しているのであって、
厳密な訂正を期待されているわけではないのだよ。

君はいみじくもP=NPを主張するからこそ、
科学的な態度と厳密さが要求されているのだ。
0799１３２人目の素数さん2006/08/20(日) 11:21:21
CRCが数学的根拠に乏しいって何言ってるんだ？
ちゃんとどういうエラーが訂正できる・できないが数学的に明らかに
なっているじゃないか。だからこそ広く使われているんだろうが。
08001 ◆salse0FDac 2006/08/20(日) 11:24:45
>>789
そのバーストエラーの検出こそが今日における誤差訂正の精度の向上に大きく貢献しているのだが。
08011 ◆salse0FDac 2006/08/20(日) 11:25:36
誤差訂正
>>798
そのバーストエラーの検出こそが今日における誤差訂正の精度の向上に大きく貢献しているのだが。
0802１３２人目の素数さん2006/08/20(日) 11:39:58
>>801
だれも精度の向上に貢献してないなどといっていないが・・・
わざわざ「重要」と書いてやったのにそれが見えないのか？
0803１３２人目の素数さん2006/08/20(日) 11:42:00
>>1は何も知らないのにいい加減なことばっか書くんだな・・・
しかし、初代>>1に比べてネタの切れ味がなさすぎ。
0804１３２人目の素数さん2006/08/20(日) 11:45:50
> CRCに数学的な根拠がない
何いってんだ？このバカ・・・
08051 ◆salse0FDac 2006/08/20(日) 12:57:36
>>804
つまりCRCには確実にバーストエラーを検出できる数学的な証明があるわけだな。
08061 ◆salse0FDac 2006/08/20(日) 13:15:12
>>802
誰も厳密な訂正に期待しているなんて言ってないが。

バーストエラーの検出を確実にできるか否かということについて私は言っているのだよ。

まだ分からない？

これは確実性の無い方式でも実績を挙げているから普及しているということなのだよ。
0807１３２人目の素数さん2006/08/20(日) 13:52:33
>>805
あるだろ？生成多項式の次数未満の長さのバーストエラーなら
確実に検出できるじゃん。
0808１３２人目の素数さん2006/08/20(日) 14:34:31
>>807
だよな。1が自信満々に言うから、思わず本で調べてしまったよ。
何を勘違いしているんだろう。
08091 ◆salse0FDac 2006/08/20(日) 16:06:41
ないだろ。

俺はそう習ったんだ。
08101 ◆salse0FDac 2006/08/20(日) 16:35:33
あのさ、intがたで計算したらeil51普通に世界記録更新したわ。

http://sakuratan.ddo.jp/imgboard/img-box/img20060820163227.png
距離=414

俺のアルゴリズム正しかったんだな。
08111 ◆salse0FDac 2006/08/20(日) 16:46:27
ついでに>>753にしたがって>>756を検証すると、
A→B→D→C:31
A→D→B→C:30

となり私のアルゴリズムの方が短いことは歴然としている。
0812１３２人目の素数さん2006/08/20(日) 16:47:28
ﾌｰﾝ
0813１３２人目の素数さん2006/08/20(日) 16:51:17
なんだ単純計算もできねーふりか
ネタの寿命のばそうとしてわざと間違ったこと書いてるのがみえみえで見苦しい
初代>>1を見習えや
08141 ◆salse0FDac 2006/08/20(日) 16:57:39
>>813
計算してみな。

A→B→D→C=sqrt((10-13)^2+(17-13)^2)+sqrt((13-5)^2+(13-6)^2)+sqrt((5-21)^2+(6-10)^2)
A→D→B→C=sqrt((10-5)^2+(17-6)^2)+sqrt((5-13)^2+(6-13)^2)+sqrt((13-21)^2+(13-10)^2)
08151 ◆salse0FDac 2006/08/20(日) 17:04:18
>>753が事実ならばもっとTSPLIB内の距離が短くてもいいとは思ってるのだが・・・。（私の経路より1長い）
0816１３２人目の素数さん2006/08/20(日) 17:06:17
>>814
nint(sqrt((10-13)^2+(17-13)^2)) = 5
sqrt((13-5)^2+(13-6)^2) = 11
nint(sqrt((5-21)^2+(6-10)^2)) = 16
A->B->D->C : 5+11+16=32

nint(sqrt((10-5)^2+(17-6)^2)) = 12
nint(sqrt((13-21)^2+(13-10)^2)) = 9
A->D->B->C : 12+11+9=32
08171 ◆salse0FDac 2006/08/20(日) 17:17:24
スマソ、少数切捨てだと思ってた。
08181 ◆salse0FDac 2006/08/20(日) 18:15:07
http://sakuratan.ddo.jp/imgboard/img-box/img20060820181216.png
距離=426

一致したニダ！
どうもニダ！
0819１３２人目の素数さん2006/08/20(日) 19:04:57
>>809
つまり、習ったことを鵜呑みにして自分では確認していないわけだな
0820１３２人目の素数さん2006/08/20(日) 19:06:09
もうこのトリップの偽>>1つまらないんだけど。

>>808
俺もｗｗｗ
声の大きい奴が得するってのは本当だなｗｗｗ
08211 ◆salse0FDac 2006/08/20(日) 19:08:26
>>819
私の確認では特に問題点は見当たりませんでした。

私よりも優れた知識を持った方達は様々な問題点に気づいたのかもしれません。
0822１３２人目の素数さん2006/08/20(日) 19:29:25
なぜ知りもしないCRCなんて例を挙げたんだろ？
今度の>>1は背伸びしすぎなんだよな・・・
0823１３２人目の素数さん2006/08/21(月) 12:29:19
今回の>>1は情報工学を囓ったガキ？
082412006/08/22(火) 19:21:03
http://sakuratan.ddo.jp/uploader/source/date20505.png
eil76に挑戦したが距離は539とopt.tourと1の差。
参ったな・・・。
0825１３２人目の素数さん2006/08/22(火) 20:30:45
>>824
76都市．．．
TSPって今は何都市くらいまで厳密解が求まってるのでしょうか？
>>12のコンコルドは15112都市の問題で最適解を得るって書いてますね．
082612006/08/22(火) 23:53:58
>>825
新しいアルゴリズム４つ思いついたから今度それで実験する。

巡回セールスマン問題への招待には最適解の都市数最高記録(7397-1994年)が書いてあるけど、もう古い本だしな。
今はもっといい記録出ているかもね。

私も新しいアルゴリズムを使って世界新記録保持者になってみたいものです。←でトンデモ扱いする事なかれ。
私のアルゴリズムの精度が上がってきていることは紛れもない事実。近い将来に世界新更新する可能性も十分にある。
0827１３２人目の素数さん2006/08/23(水) 00:04:19
>>826
いくら精度が上がっても意味ないんだよ
082812006/08/23(水) 00:10:05
>>827
あなたにとっては意味の無いことかもしれませんが、私にとっては大きな意味を持つ物なのです。

あなたと私では価値観に隔たりがあるようです。
0829１３２人目の素数さん2006/08/23(水) 00:32:59
>>828
だからＰ＝ＮＰはどこにいったんだよ？アホか？
0830１３２人目の素数さん2006/08/23(水) 03:24:04
解を出力すると同時にそれが厳密最適解であることを証明するアルゴリズムでないと，
厳密解法と呼ばないので気をつけてな．最高記録と言うのはそう言う意味なので．

下界値からのギャップが数％の近似解で良いと言うなら100万都市でも解けるので・・・
0831１３２人目の素数さん2006/08/23(水) 08:03:29
俺のアルゴリズムなら常に最適解を出力するぜ。既に世界記録も更新した
>>1の負けだな
0832１３２人目の素数さん2006/08/23(水) 08:16:33
アイデアを盗まれると困るので詳細は説明しないけど
いくつかのアルゴリズムを組み合わせてそれぞれの得意な部分を利用させている
eil76でもoptを出力したし完璧だな
0833１３２人目の素数さん2006/08/23(水) 08:54:37
>>832 全然分かりません。というか、そういう意味不明なアイディアは盗めませんが？で、結局はその程度で俺様はすごいんだぞということでFA？
0834１３２人目の素数さん2006/08/23(水) 09:47:13
すでに最適解が分かっている問題なら、
その解が出るようにアルゴリズムをチューニングすることぐらい簡単だろｗ
083512006/08/23(水) 21:42:21
>>829
どこにもいってない。
P=NPで解く可能性を新アルゴリズムは備えている。

>>830
厳密解法へと進化していることは確かです。

>>831
だったらさっさと申請すればいいだろ。
更新したと嘘を書くことならカスでもできる。
それに貴様のような低脳な奴と勝負した覚えもないし。
「常に最適解を出力」って事はどんに大きな都市数でも最適解を出力するって事だよな。
だったら証拠に未解決の問題でも解いて正しいことを証明してみろ。

>>832
一生その完璧なアルゴリズム抱いて寝てろ。
0836１３２人目の素数さん2006/08/23(水) 23:28:45
未解決問題でも枝狩りすりゃ簡単に最適解を求められるだろｗ
0837１３２人目の素数さん2006/08/23(水) 23:31:52
> だったらさっさと申請すればいいだろ。
> 更新したと嘘を書くことならカスでもできる。

これ自分のこと？ｗｗｗ
0838１３２人目の素数さん2006/08/23(水) 23:46:18
アルゴリズムを工夫して精度を上げていくやり方では、永久に最適解
アルゴリズムは作れないよ。なぜならそれが必ず最適解を求めるという
ことを証明できないから。

むしろ膨大な時間がかかっても確実に最適解が求められるプログラムを
作って、実行時間を短くする努力をした方が良いだろう。
083912006/08/24(木) 17:59:23
>>836
簡単ならさっさと世界記録保持者になってみろ。

>>837
明らかに>>831って書いてあるのだが。
あなたは日本語どころか数字すら読めないみたいですね。
百歩譲って私のことだとしましょう。
何を申請すれば？
更新してませんが？

>>838
人造人間を作るとしよう。

以下の二つの方法を考えた。
1.ある人間サイズの空間上にあらゆる物質やエネルギーの並びを試して作る方法＝ブルートフォース
2.実際の人間の死体などを解体して物質や構造などを調べて、その通りに真似て作る方法。

私は2の方法を試しているのだ。
今は性器を精巧に作ることができたような段階だが、
他の部分も順次分析することで、いつしかは人間を作ることができると信じている。
0840１３２人目の素数さん2006/08/25(金) 11:08:13
>>839
お前が挑戦してるのはベンチマークだから
未知でもなんでもないな。
汎用性がないとダメなのって分かる？
084112006/08/25(金) 19:13:34
>>840
汎用性はあるよ。
なぜならばどのような問題にも見られる特性の抽出により考えられているから。

例えば
・線が交差しない
・一度通った都市には二度と立ち寄らない
・各都市間は直線で結ばれる

などはどのような問題にも共通している最短経路の特徴であることは君にも分かるだろう？
0842１３２人目の素数さん2006/08/25(金) 23:12:25
>>841
どうやらまだ何も分かっていないようだな・・・
084312006/08/25(金) 23:29:46
>>842
どうやらまだ何も分かっていないようだな・・・
0844１３２人目の素数さん2006/08/25(金) 23:32:14
巡回メコスジマン問題
084512006/08/25(金) 23:34:46
>>844
どうやらまだ何も分かっていないようだな・・・
0846１３２人目の素数さん2006/08/25(金) 23:38:31
まさか汎用性という言葉の意味まで知らないレベルとは思わなかったorz
084712006/08/25(金) 23:56:24
意味あっているじゃないか。

>>846が自信満々に言うから、思わずインターネットで調べてしまったよ。 http://glossary.tank.jp/t011D.html
何を勘違いしているんだろう。

それにしても、なぜ知りもしない汎用性の話に突っ込んだんだろ？
>>846は汎用性の意味も知らないくせに背伸びしすぎなんだよな。
0848１３２人目の素数さん2006/08/26(土) 00:41:02
>>847
悪の用語辞典なんて釣りか？
そろそろあきらめろよ。
084912006/08/26(土) 14:26:56
>>848
いい加減に自分の非を認めたらどうだ？
意味が違っているというならばその証拠ぐらい提示するのが社会のルールじゃないのか？
0850１３２人目の素数さん2006/08/26(土) 19:46:49
また>>1の中の人が入れ替わったか？
0851１３２人目の素数さん2006/08/26(土) 21:04:46
>>849
> いい加減に自分の非を認めたらどうだ？
ｗｗｗｗ
お前がなｗｗｗｗｗｗｗｗｗ
085212006/08/26(土) 23:42:10
>>851
ですから、意味が違っているというのでしたら、その証拠を提示してください。
その証拠が妥当な物だと判断できましたら、私は汎用性の意味を間違って使ったことを反省します。
0853１３２人目の素数さん2006/08/27(日) 00:03:35
証拠ｗｗｗｗｗｗ
0854１３２人目の素数さん2006/08/27(日) 01:02:46
そもそもTSPって何のためのベンチマーク問題だったかな？

どんなTSPにも適用できれば汎用性ある？
それともTSP以外の組み合わせ最適化問題にも適用できないと汎用性ない？
085512006/08/27(日) 22:33:08
>>853
そうです。証拠です。早く提示してください。

>>854
どんなTSPにも適用できれば汎用性あるということだろ。
私はTSPを解こうとしているのですよ。

・どんなTSPにも適用できれば汎用性ある？
・それともTSP以外の組み合わせ最適化問題にも適用できないと汎用性ない？
私が上の質問にyesと答えようがnoと答えようが私が汎用性の意味を正しく解釈していることには変わりない。
0856１３２人目の素数さん2006/08/28(月) 00:53:01
お前こそ本物の>>1だって証拠見せろよ
0857１３２人目の素数さん2006/08/28(月) 01:00:00
http://www.se.uec.ac.jp/lab/yura-lab/umetani/nanzan2005/tsp01.pdf
0858１３２人目の素数さん2006/08/28(月) 02:08:49
>>855
トリ付けるの止めたの？
0859１３２人目の素数さん2006/08/28(月) 02:54:02
>>855
今度の>>1は揚げ足取りキャラなのか？
08601 ◆salse0FDac 2006/08/28(月) 18:34:08
>>856
トリップ。

>>857
だから何が言いたい？

>>858
付けてほしいなら付ける。

>>859
>>733
0861１３２人目の素数さん2006/08/29(火) 03:30:53
>>1はトリップつけてねーからｗｗｗ
0862１３２人目の素数さん2006/08/29(火) 03:59:52
>>1は国語と数学を勉強し直してこいってことだな。
086312006/08/29(火) 19:33:16
>>861-862
それでは何を示せばいい？
具体的にいってみろ。
もしも自分が>>1ならば何を自分が>>1である証明を提示するか。
自分が出来もしないことを偉そうに人に指図することが許されるのは小学生までだからね。
私はトリップが最も>>1であることの証明として最も使えるものと判断したのでトリップを提示しただけです。
◆salse0FDacのトリップを持った人が>>1が提示したものと酷似した経路の画像を提示しているのも紛れもない事実。
ちなみにお前らが偽>>1とかいっているのは存在しない。
俺は本物の>>1な訳だが今まで偽者の書き込みは１度も無かった。
信じる信じないはお前らの勝手だが。
当然のごとく最も有力である>>1であることの証明を提示しただけで国語と数学を勉強して来いと意味不明な発言をすることはナンセンスだ。
人に国語の勉強しろという前に汎用性の意味ぐらい調べろということだし、
数学の勉強しなおせということも何の数学を勉強をするかも提示していない時点で数学的に問題の有る文章だ。
それに本物の>>1である証明を何故提示しなければならないのかも分からない。
汎用性の意味を説明できないから話を逸らしたとしか思えない。
0864１３２人目の素数さん2006/08/29(火) 22:22:24
>>863
どこをタ（ｒｔ
086512006/08/29(火) 23:06:10
>>864
>どこをタ（ｒｔ
翻訳するとあなたは>>863の文章を読んだところ、自分が揚げ足をとる要素がどこにも見当たらないため自分の非を認めざる終えなくなったわけですね。
いい加減揚げ足取りやめて>>866に謝罪文書いて逝けばいいのでは？
0866１３２人目の素数さん2006/08/30(水) 00:34:06
>>865
読む価値もないってこったろｗ
086712006/08/30(水) 17:29:53
>>866
字を書けないってこったろｗ
0868１３２人目の素数さん2006/08/30(水) 17:55:40
>>867
つまらんな。
もっと面白いことを書け。どうも今回の1は劣化がひどい。
次の1はまだか？
086912006/08/30(水) 21:19:12
>>868
お前が一番つまらんわな。
0870１３２人目の素数さん2006/08/30(水) 21:22:20
> 厳密解法へと進化していることは確かです
はじめから厳密解法をつかえばいいじゃん
087112006/08/30(水) 21:39:31
>>870
あなたの言う厳密解法はP=NPかつ汎用性のある(どのような問題でも確実に正確な解を出す)ものなのか？
そうじゃなければ意味がないの知ってる？

それがあるなら既に巡回セールスマン問題は難問でもなんでもなくなってる。
0872１３２人目の素数さん2006/08/31(木) 00:14:40
1のアルゴリズムは多項式時間で解けると証明されてないのでP=NPとは無関係だね
087312006/08/31(木) 22:21:27
>>872　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
新アルゴリズムには多項式時間で解ける数学的な証明がある。　　　　
だが、その証明をインターネット上に公表する予定は今のところない。　　
なぜならば、証明をインターネット上に公表するにはアルゴリズムを公表しなければならないから。
証明は論文にアルゴリズムと一緒に記す予定だ。　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
0874１３２人目の素数さん2006/09/01(金) 00:13:40
>>873
論文を書くには、過去の手法と比較しないといけないんですが。
0875１３２人目の素数さん2006/09/01(金) 22:09:55
>>874
過去の手法との比較なんてどうでもいいんじゃない?
多項式時間で解ける数学的な証明があって、
厳密解を出せるという証明もあるならば。
ま、 >>873 がそうだとは全然思えないけど。
087612006/09/01(金) 22:47:20
>>874
比較の必要はないさ。
だって今回のプログラムは確かに巡回セールスマン問題を解けるように作られているが、
解く事が目的というよりもパターンを抽出するために作られたような物。
新アルゴリズムと比較することの方がかえってナンセンス。

>>875
はいはい。
期待してもらわなくて結構。
仮にTSPに失敗しても計算量を極限まで減らしたソートアルゴリズムがすでに完成している。
O(nlogn)だがクイックソートよりやマージソートなどよりも平均的に高速に動作する。
08778752006/09/02(土) 00:27:25
>>876
どちらも元コメントからずれた答えになっちゃってますね。
私は論文として出してもらうこと期待してるんだけどな。もちろんTSPの方ね。
論文を投稿したらネットにも公開してね。
0878１３２人目の素数さん2006/09/02(土) 01:40:58
O(nlogn)「だが」ねえ・・・ｗ
0879１３２人目の素数さん2006/09/02(土) 01:55:14
>>876
トンデモ具合が本当の>>1に比べて足りないんだけど・・・
088012006/09/02(土) 12:15:42
>>877
もちろんTSPも論文に書く予定だが、私はTSPを解く為の論文を書くつもりはありません。
ここまでいうつもりは無かったが、私は計算量を低下させる手法についての論文を書きたいのだ。

>>879
だってトンデモじゃないから。
0881１３２人目の素数さん2006/09/02(土) 15:20:45
ミレニアム問題か･･･懐かしいな。まだ一個も解けてないんだっけか？
まぁ頑張って一億円手にしてくれ>>1よ。
088212006/09/02(土) 15:42:13
>>881
eil51は解けただろ。
0883１３２人目の素数さん2006/09/02(土) 19:49:49
>>882
( ´,_ゝ`)ﾌﾟｯ
08848752006/09/03(日) 10:07:53
>>880
NP-hardな問題を多項式時間で解くという論文だったら
過去の手法との比較なんてどうでもいいと思ったけど、
計算量を低下させる手法について書くなら、
過去の手法との比較が絶対必要だね。

なんかP=NPとか「巡回セールスマンが多項式時間で解ける」から
どんどん離れていってる気がする。
0885１３２人目の素数さん2006/09/03(日) 12:41:12
その「計算量を低下させる手法」とやらが、
プログラミングレベルでのad hocなチューニングでないことを祈る。

↓を読む限りはそんな臭いがぷんぷんしてるんだが。
>仮にTSPに失敗しても計算量を極限まで減らしたソートアルゴリズムがすでに完成している。
>O(nlogn)だがクイックソートよりやマージソートなどよりも平均的に高速に動作する。
0886１３２人目の素数さん2006/09/03(日) 14:42:03
懸賞問題なんだから巡回セールスマン問題が多項式時間で解けたのならさっさと論文を発表したほうがいいと思うが
0887１３２人目の素数さん2006/09/03(日) 17:02:06
>>885
ad hocなチューニングってのは、
計算量の定数部分を下げるって意味？
088812006/09/03(日) 21:37:02
>>884
もちろんTSPがメインだ。
ソートはもしもTSPが失敗した際のバックアッププラン。
TSPもある程度いい所まで行ってだめだったら、適当にデータを捏造して解けたことにするか、
出来そうな最も多い都市数の結果を提示して「P=NPの可能性が高い」で結論付ける予定。

↑まぁ下2行は半分冗談だ。

>>885
ad hocなチューニングってのは既存のアルゴリズムを改良して高速化したって意味？
そうだとしたら違うぞ。
私の開発した計算量を最低に収束させる分析法に基づくアルゴリズムだ。

私のアルゴリズムの特性だが、
例えば最速といわれているクイックソートの場合もともと整列済みまたはほぼ整列済みの場合O(n^2)になるが、
私のアルゴリズムの場合整列してい・・・・やっぱり技術漏洩阻止のため黙秘いたします。
0889１３２人目の素数さん2006/09/03(日) 22:38:07
どんなに整列しても多項式時間にはならんぞｗｗｗ
ソートすべき経路数がn!通りあるのを忘れたのかｗｗｗｗｗ
0890１３２人目の素数さん2006/09/03(日) 22:47:17
> 出来そうな最も多い都市数の結果を提示して「P=NPの可能性が高い」で結論付ける予定。

いやいや、その結果(1のプログラムでは大きな問題が解けなかった)と、
「P=NPの可能性が高い」という結論は全然関係ないから。
ほんっとうになんにもわかってないのねえ。
0891１３２人目の素数さん2006/09/03(日) 22:57:05
NP-hardの中でも簡単なKPなどを多項式時間で
TSPに帰着できるわけないんだが。

普通に考えてP≠NPなのは分かりそうなもんだ。
0892１３２人目の素数さん2006/09/03(日) 22:58:13
>>890
>>1はP=NPを証明した天才だぞ。そんなミスをするわけないじゃないか
08938902006/09/03(日) 22:58:40
読み違えた。「P≠NPの可能性が高い」かと思ってた。
もしかして、「僕が100都市の問題で厳密解と同じものを算出できたから、P=NPの可能性が高い」
と結論づけたいとか?　面白すぎる。
(また私の読み違いでありますように)
0894１３２人目の素数さん2006/09/03(日) 23:00:04
>>1がP=NPを証明して>>891がP≠NPを証明したのか。このスレは天才だらけだな
08958912006/09/03(日) 23:01:15
>>894
違う違う。
普通に考えればP=NPなんて妄想抱くわけないってこと。
0896１３２人目の素数さん2006/09/03(日) 23:03:56
NP困難(not NP完全)な問題がTSPに多項式時間で帰着できないこととP≠NPとは
何の関係もないと思うんだが
0897１３２人目の素数さん2006/09/03(日) 23:14:32
>>896
工学的にはどっちも同じように使われてるんだよ。
0898１３２人目の素数さん2006/09/04(月) 02:40:56
>>897
確かに専門書でもあまり区別してないな。
089912006/09/04(月) 08:36:15
>>894
＞>>1がP=NPを証明して>>891がP≠NPを証明したのか。
P=NPが証明されP≠NPが証明されたとなると、これは矛盾していることになる。

つまり
1がP=NPを証明して891がP≠NPを証明した＝偽
その対偶である
1がP=NPを証明していなくて891がP≠NPを証明していない＝偽
が成り立つ。

つまり
1がP=NPを証明して891がP≠NPを証明していない＝真
又は
1がP=NPを証明していなくて891がP≠NPを証明した＝真
の可能性が残る。

P=NPの証明の難易度=P≠NPの証明の難易度とすると、漏れがTSPを解く確率は50%で>>891がP≠NPを証明する確立は50%
090012006/09/04(月) 08:50:32
>>889
ソートはTSPとは別に研究する。
計算量の低下という点では一致するが。

>>893
100都市ではなく世界記録のデータと比較させてもらう。

>>895
こういう数学者が居るからポアンカレ予想とやらが支那人に解かれてしまうんだよ。
俺は数学科の人間ではないけどさ。

>>896
TSPがNP完全と証明されたなら関係のない話じゃないのか？
090112006/09/04(月) 09:00:12
訂正
>>894
＞>>1がP=NPを証明して>>891がP≠NPを証明したのか。
P=NPが証明されP≠NPが証明されたとなると、これは矛盾していることになる。

つまり
1がP=NPを証明して891がP≠NPを証明した＝偽
その対偶である
1がP=NPを証明していなくて891がP≠NPを証明していない＝偽
が成り立つ。

つまり
1がP=NPを証明して891がP≠NPを証明していない＝真
又は
1がP=NPを証明していなくて891がP≠NPを証明した＝真
の可能性が残る。

P=NPの証明の難易度=P≠NPの証明の難易度とすると、漏れがP=NPを証明する確率は50%で>>891がP≠NPを証明する確率は50%
0902１３２人目の素数さん2006/09/04(月) 13:04:56
勝つか負けるかのどちらかだから勝率50%
というギャグを思い出した
0903１３２人目の素数さん2006/09/04(月) 15:06:52
「1がP=NPを証明して891がP≠NPを証明した → 偽」
の対偶は
「真(偽でない) → 1がP=NPを証明していないかまたは891がP≠NPを証明していない」
だよ

0904１３２人目の素数さん2006/09/04(月) 15:23:35
>>1 カワイソス
0905１３２人目の素数さん2006/09/04(月) 16:29:01
>>901
>1がP=NPを証明していなくて891がP≠NPを証明していない＝偽
すごいな．どちらかがミレニアム懸賞問題解決したことになった．
090612006/09/04(月) 16:32:20
>>903
とりあえず「1がP=NPを証明していなくて891がP≠NPを証明していない＝偽」にしておいてよ。
せっかくTSPが解決したという証明になったのに。。。
0907１３２人目の素数さん2006/09/04(月) 21:44:55
都市数が500万個までならO(1)で解けることが数学的に証明されているアルゴリズムがあるのだが。
0908１３２人目の素数さん2006/09/04(月) 22:03:31
500!
090912006/09/04(月) 22:42:35
>>907
うそ言うな。
あるんだったら証拠出せ。

ちなみに俺はO(n)よりオーダーが下がらないことを数学的に証明する容易も有る。
0910１３２人目の素数さん2006/09/04(月) 22:51:15
>>909
おいおい、都市数500万個以下と制限してある以上計算理論上はO(1)になるのは自明だぞ
計算理論の教科書読めよ
091112006/09/04(月) 23:17:06
>>910
それが許されるなら俺が１００００００００００００００都市をO(1)で解くと言ってブルート・フォースのプログラム提示したら
お前は俺をTSPを多項式時間で解いた神と崇めるか？
馬鹿も休み休みに言え。

とりあえず新アルゴリズムの原型のテスト
http://sakuratan.ddo.jp/uploader/source/date21357.png
0912１３２人目の素数さん2006/09/04(月) 23:22:28
だから１００００００００００００００都市の問題を多項式時間で解けても無意味なんだってば
もう少し基礎を勉強したほうがいいと思うよ
0913１３２人目の素数さん2006/09/04(月) 23:26:41
プログラムとアルゴリズムを混同～♪
091412006/09/04(月) 23:28:31
>>912
お前の言うことが正しければ有限個のTSPは全てO(1)で解けることになるが？
091512006/09/04(月) 23:29:27
>>913
だからなんだ？
0916１３２人目の素数さん2006/09/04(月) 23:32:19
>>914
特定の都市数ではなく任意の都市数で解ける事を示せないとダメなんだよ
もう少し基礎を勉強したほうがいいと思うよ
0917１３２人目の素数さん2006/09/04(月) 23:47:30
>>916
1.まず任意の都市数を入力する
　（ただ単に数値を受け取る。）
＝ここまでO(1)＝
2.その都市数で解けるアルゴリズムにプログラムを書き換える。
　（もともと解くことの出来る限界の都市数をマクロ命令で確保されており、数値の書き換えだけで都市数を変更できるようになっている。もちろんその数値の記されるアドレスは別途記録されている。）
＝ここまでO(1)＝
3.出来た制限付きのプログラムを起動してO(1）で解く。
＝ここまでO(1)＝

つまり、O(1)で解く都市数制限付きのプログラムを生成してそのプログラムを使ってO(1)で解くって事をすれば全部O(1)で解けちゃうの。
さっきプログラム書き換えたばかりで手が疲れてるから、あまりタイピングさせないでくれ。
0918１３２人目の素数さん2006/09/04(月) 23:50:19
>>917
領域量が∞必要
0919１３２人目の素数さん2006/09/04(月) 23:55:17
>>917
計算理論ではプログラムサイズは定数じゃないといけないんだよ
もう少し基礎を勉強したほうがいいと思うよ
0920１３２人目の素数さん2006/09/04(月) 23:56:08
x=O(x)
2x=O(x)
3x=O(x)
...

n<=x<n+1 naraba x^2<(n+1)x=O(x)

yotte x^2=O(x)
0921１３２人目の素数さん2006/09/05(火) 00:17:47
>>1は>>12で紹介されているコンコルドとの比較はしたのだろうか？
0922１３２人目の素数さん2006/09/05(火) 00:40:54
>>917
２の作るプログラムの都市数上限が定数じゃないので３がO(1)じゃなくなる
092312006/09/05(火) 08:45:09
>>919
>>922
それを言うならほとんどのアルゴリズムははO(1)にできるな。
俺のプログラムもO(1)だ。
なぜならばメモリを確保するために最大都市数が設定されているから。

どんな都市数でもコンピュータ上で解くなんて無理な話さ。
いっそ無理であることを数学的に証明して賞金もらおうか？

ちなみに、キーボードからの数値の入力にしてもプログラムのサイズにしても限界があるのだよ。
その限界まで解けると考えればO(1)だろ。
領域が足りないならメモリを増設すれば、そのメモリ全部が限界となり、メモリの限界までの制約付きでO(1)で解けることになる。
つまりメモリを増設すればO(1)になるということになる。
0924１３２人目の素数さん2006/09/05(火) 08:54:46
>923
任意の都市数で解かないとP=NPは言えないぞ（藁
チューリングマシンに置き換えたらメモリは無限に用意されてるから頑張れ.
0925１３２人目の素数さん2006/09/05(火) 09:21:13
>>923
変数と定数の区別ぐらい付けろよｗ
0926１３２人目の素数さん2006/09/05(火) 09:31:04
>>923
「問題を限定すれば」O(1)にできるね。
そしてアルゴリズムとプログラムの区別をつけなよ。
092712006/09/05(火) 21:13:29
>>924
だからプログラムを書き換える事もメモリを増設することもO(1)で出来る以上、
任意の都市数に限定した解法でO(1)で解けてしまうの。
ちなみに入力時のオーダーもメモリの限界まで入力できるアルゴリズムとなるため最悪でも入力用のメモリを全て走査すればよいことになり、入力用のメモリが定まっている以上O(1)とみなすことが出来る。

>>925
あなたのPCのメモリは起動するたびに容量が変化するのかな？
修理に出してから出直しなさい。

>>926
そう。
つまり、PC上で実行できるほとんどのプログラムはO(1)ということになる。
それはPCで実行できる範囲と限定されているとみなせるから。
そしてアルゴリズムの定義を勉強してきなさい。
0928１３２人目の素数さん2006/09/05(火) 22:28:38
>>927
O(1)で解けるのは都市数が定数の場合だけ
0929１３２人目の素数さん2006/09/05(火) 22:35:34
>>1の計算量の変遷
(ソート)
876 ：1：2006/09/01(金) 22:47:20
仮にTSPに失敗しても計算量を極限まで減らしたソートアルゴリズムがすでに完成している。
O(nlogn)だがクイックソートよりやマージソートなどよりも平均的に高速に動作する。

(TSP)
909 ：1：2006/09/04(月) 22:42:35
ちなみに俺はO(n)よりオーダーが下がらないことを数学的に証明する容易も有る。

(TSPはじめ全て)
927 ：1：2006/09/05(火) 21:13:29
だからプログラムを書き換える事もメモリを増設することもO(1)で出来る以上、
任意の都市数に限定した解法でO(1)で解けてしまうの。

つまり、PC上で実行できるほとんどのプログラムはO(1)ということになる。


ちょwwww減りすぎwwwww
093012006/09/05(火) 22:38:59
>>928
そうだ。
それを俺が応用して様々な問題をＯ（１）で解けるようにしたんだよ。
俺はお前らが正しいといったことを信じてやったまでだ。
俺の言っていることが間違っているならばお前らも間違っているって事だ。
093112006/09/05(火) 22:45:36
>>929
そうだ。
俺がお前らが指摘したことを応用して様々な問題をＯ（１）で解けるようにしたんだよ。
俺はお前らが正しいといったことを信じてやったまでだ。
俺の言っていることが間違っているならばお前らも間違っているって事だ。
まっ、俺は都市数500万を限定つきでもO(1)でとけるって事を論理的に否定しているだけだが。
つまり、O(1)ネタは所詮はネタって事よ。
大体それをO(1)ですといっているのを否定しただけで計算理論を勉強しろっていうから、
それが正しかったとしたら計算理論全体が崩れる事を見せただけで発狂されても俺が迷惑だからさ。
0932１３２人目の素数さん2006/09/05(火) 22:57:04
つまらないなあ
ネタ切れならさっさと終了宣言したら
0933１３２人目の素数さん2006/09/05(火) 22:59:41
都市数N以下ならO(1)で解ける、という定理はNが定数の時だけ
>>917では2でNに変数を代入してるから定理は成立しない

>>1は∀と∃の概念が理解出来ないんだろうか？
0934１３２人目の素数さん2006/09/05(火) 23:00:55
>>932
このスレを使い切ってから逃げるつもりだろう
何年もTSPを研究して来たらしいが徒労だったなｗｗｗｗｗ
093512006/09/05(火) 23:02:25
>>932
いや、つまらないなら君が退場すれば全て丸く収まるでしょ？
別に俺は君が以前言ったようなスレの延命やっている訳じゃないから。
真面目にTSPを解こうとしているのだよ。
ネタ目的ならスレ違い。
093612006/09/05(火) 23:03:46
>>933
定数に変換されている。
よってO(1)。
093712006/09/05(火) 23:05:34
>>934
次スレは「巡回セールスマン問題　第Ⅱ都市」で決定だな！
0938１３２人目の素数さん2006/09/05(火) 23:07:14
>>936
お前の主張は

定数Nはxで微分すると0
Nにxを代入する
ここでNをxで微分すれば0
よってxをxで微分すれば0

と同じだぞ
0939１３２人目の素数さん2006/09/05(火) 23:08:51
しょうもない御託並べて引き伸ばすことのどこが真面目なんだか
言い訳も少しは工夫しろ
0940１３２人目の素数さん2006/09/06(水) 00:08:23
>>937
つ 巡回セールスマン問題　都市数2
0941１３２人目の素数さん2006/09/06(水) 01:31:42
>>940
いいセンスしてるね
0942１３２人目の素数さん2006/09/07(木) 04:23:52
次スレのﾃﾝﾌﾟﾚには、>>12のconcordeとか入れたほうがいいな。
094312006/09/07(木) 17:20:50
>>938
よって変数を定数に変換することが出来ましたと。
Q.E.D.

>>939
私はアルゴリズムを改良したり計算結果を発表したりいろいろやっているじゃないですか。
自分の不真面目を人のせいにするのはやめた方がいいと思いますよ。

>>940-941
別に都市をカウントする感じだからかまわないが、
都市数2よりも都市数=2の方が個人的には違和感が無くていい気がする。
いつ消えるか分からないスレではあるが、終わるまでずっと使うものだから慎重に。
他の意見も受け付ける。

>>942
確実に正確な解が出ると保証されていないなら入れなくてもいいのでは？
0944１３２人目の素数さん2006/09/07(木) 17:55:13
>>943
勉強不足だな。
concordeは最適性の保証があるぞ？
0945１３２人目の素数さん2006/09/07(木) 19:23:02
1 は英語読めませんから。
0946１３２人目の素数さん2006/09/07(木) 19:27:55
>>1は英語も読めないのかよ。
いくらなんでもそれは酷すぎだろ。
094712006/09/07(木) 22:00:19
>>944
だったらconcordeで世界新記録出せるのか？
また都市数にリミット付きじゃ意味無いから。

>>945-946
お前らも読めないんだろ。
読めないくせに見栄張るな。
0948１３２人目の素数さん2006/09/07(木) 22:03:34
>>947
世界記録なら出せるよ。最適性の保証があるんだからあたりまえ
094912006/09/07(木) 22:15:39
>>948
マジか。で、多項式時間で？
そうだとしたらTSP解決したな。
0950１３２人目の素数さん2006/09/07(木) 22:18:15
>>947
だからconcordeが世界記録持ってるっていってるだろｗ

http://www.tsp.gatech.edu/sweden/index.html
まずはこれを読め。

これはスウェーデンの24978都市だが、
2004年の記録だからもっと凄いのができてるかもしれん。

51都市とか低レベルすぎて笑われるぞ。
0951１３２人目の素数さん2006/09/07(木) 22:18:53
>>949
まずはconcordeのwebサイトを隅から隅まで読んでこい。
話はそれからだ。
095212006/09/07(木) 22:25:06
2004年5月にスウェーデンの香具師が24,978都市のTSPを解いた。
それまでの世界記録は2001年4月のドイツの香具師の記録の15,112都市。

でもう限界。
095312006/09/07(木) 22:27:07
多項式時間で解けるならP=NPじゃないか。

俺の研究も無駄にならなかったな。
0954１３２人目の素数さん2006/09/07(木) 22:36:12
>>953
まず読んでこいっていってるだろ。
095512006/09/07(木) 22:36:59
>>954
読めないって言ってるだろ。
095612006/09/07(木) 22:45:58
なるほど。
2分木を使うことによりO(nlog n)で解く手法なのだな。
これにより855,528都市のTSPが従来の0.0081%距離を短縮することが出来たとな。
0957１３２人目の素数さん2006/09/07(木) 22:50:54
>>12で紹介された後、何度もコンコルドと比較しろと言われていたが、今ごろようやく調べたのか？
095812006/09/07(木) 22:55:48
>>957
P=NPらしいからな。
0959１３２人目の素数さん2006/09/07(木) 23:00:18
>>956は明らかにネタだろうけど…

英語が読めなくても、空気が読めたら、
コンコルドが多項式時間ではないことは
想像できると思うんだが。
0960１３２人目の素数さん2006/09/07(木) 23:49:13
>>1は分枝切除平面法もしらないのか？

まー知ってれば聞いただけで最適性の保証があると
わかりそうなもんだがな。
0961１３２人目の素数さん2006/09/08(金) 10:48:10
Moustapha Diaby
"P = NP: Linear programming formulation of the traveling salesman problem"
http://arxiv.org/abs/cs.CC/0609005

TSPが多項式時間だってさ（ｗ
096212006/09/08(金) 20:33:16
>>959
想像で仮定を立てるのはOKだが、想像で多項式時間ではないと判断するのは理系の人間のやることではないと思います。

>>960
知りません。
あなたも知らないのでしょう？

>>961
やっぱそうだよね。
0963１３２人目の素数さん2006/09/08(金) 20:57:35
>>962
想像じゃないだろ。
基本的には分枝限定法なんだから最適解に決まってるだろ。
大丈夫か君？
0964１３２人目の素数さん2006/09/08(金) 20:58:13
あと、多項式時間じゃないこともね。
096512006/09/08(金) 21:11:52
>>963-934
分枝限定法が最適解を確実に出せると知っている。→多項式時間じゃないに決まってるだろ。

分枝限定法が最適解を確実に出せると知らない。→多項式時間じゃないと想像する。┳多項式時間じゃないに決まってるだろ。 →理系失格。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　┗想像だけでは多項式時間じゃないとは言い切れない。→OK
096612006/09/08(金) 21:51:16
訂正
>>963-934
分枝限定法が多項式時間で最適解を確実に出せると知っている。→多項式時間じゃないに決まってるだろ。

分枝限定法が多項式時間で最適解を確実に出せると知らない。→多項式時間じゃないと想像する。┳多項式時間じゃないに決まってるだろ。 →理系失格。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　┗想像だけでは多項式時間じゃないとは言い切れない。→OK
0967１３２人目の素数さん2006/09/08(金) 22:36:48
>>962
> 想像で仮定を立てるのはOKだが、想像で多項式時間ではないと判断するのは理系の人間のやることではないと思います。
想像ではない。
・コンコルドが最適性の保証があるTSPの解を出すことが知られている
・しかし、それを元にTSPが多項式時間で解けるという結論を誰も出していない
ということから、コンコルドが多項式時間ではないと結論づけられるのだが。

> やっぱそうだよね。
なんでそっちは根拠もなく信じるんだよ。英語で書いてあるから読めないはずなのに。
0968１３２人目の素数さん2006/09/08(金) 22:39:12
1は文系にも理系にも向いてないな．→ 人間○格？
096912006/09/08(金) 22:47:16
>>967
TSPの技術が軍事転用可能であるためにコンコルドで多項式時間で解けるという事実を隠しているのかもしれない。

>なんでそっちは根拠もなく信じるんだよ。英語で書いてあるから読めないはずなのに。
長年の研究の結果からP=NPの可能性が非常に高いと考えているからです。
097012006/09/08(金) 22:48:13
>>968
あなたは自称理系ですか？
0971１３２人目の素数さん2006/09/08(金) 22:55:14
>>970
イイエ．
0972１３２人目の素数さん2006/09/08(金) 23:01:07
・・・最悪ケースを逆算して代入してみろ。分枝限定法は指数時間になるぞ。もうちょっと調べてから来い
0973１３２人目の素数さん2006/09/08(金) 23:56:13
>>967
> なんでそっちは根拠もなく信じるんだよ
ね。変な宗教みたい。
0974１３２人目の素数さん2006/09/09(土) 06:59:45
>>1は分枝限定法も知らないの？
0975１３２人目の素数さん2006/09/09(土) 09:22:20
スレの存在意義がないので次スレはいらん
097612006/09/09(土) 21:04:54
>>975
じゃ次スレはやめるね。
今まで>>1-975ご苦労さん。
もう一緒に議論することも無いかもな。
さいなら。
0977１３２人目の素数さん2006/09/09(土) 21:50:18
逃げたかｗ
数年間の研究が徒労に終わって良かったねｗｗ
0978１３２人目の素数さん2006/09/10(日) 00:02:40
>>976
( ´,_ゝ`)ﾌﾟｯ
結局逃走か
097912006/09/10(日) 20:19:03
>>977-978
いや、逃げるんじゃないよ。
これからは一人で研究するってだけ。
挑発するなら次スレ立ててもいいが。
0980１３２人目の素数さん2006/09/11(月) 10:09:59
ほしゅ
0981１３２人目の素数さん2006/09/11(月) 10:10:06
ほしゅ
0982１３２人目の素数さん2006/09/11(月) 10:10:29
ほしゅ
0983１３２人目の素数さん2006/09/11(月) 10:10:37
ほしゅ
0984１３２人目の素数さん2006/09/11(月) 10:11:05
ほしゅ
0985１３２人目の素数さん2006/09/11(月) 10:11:12
ほしゅ
0986１３２人目の素数さん2006/09/11(月) 10:11:51
ほしゅ
0987１３２人目の素数さん2006/09/11(月) 10:11:57
ほしゅ
0988１３２人目の素数さん2006/09/11(月) 10:12:37
ほしゅ
0989１３２人目の素数さん2006/09/11(月) 10:13:13
ほしゅ
0990１３２人目の素数さん2006/09/11(月) 10:13:22
ほしゅ
0991１３２人目の素数さん2006/09/11(月) 10:13:52
ほしゅ
0992１３２人目の素数さん2006/09/11(月) 10:15:04
ほしゅ
0993１３２人目の素数さん2006/09/11(月) 10:15:13
ほしゅ
0994１３２人目の素数さん2006/09/11(月) 10:15:36
ほしゅ
0995１３２人目の素数さん2006/09/11(月) 10:15:49
ほしゅ
0996１３２人目の素数さん2006/09/11(月) 10:16:07
ほしゅ
0997１３２人目の素数さん2006/09/11(月) 10:16:46
ほしゅ
0998１３２人目の素数さん2006/09/11(月) 10:16:52
ほしゅ
0999１３２人目の素数さん2006/09/11(月) 10:17:30
ほしゅ
1000１３２人目の素数さん2006/09/11(月) 10:17:36
ほしゅ
1001１００１Over 1000Thread
このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。
レス数が1000を超えています。これ以上書き込みはできません。