- 1 名前：名無しさん＠１周年 [02/01/29 16:10]
- ってなに
- 2 名前：2 mailto:2 [02/01/29 16:12]
- 2
- 3 名前：名無しさん＠１周年 mailto:道順は24通り [02/01/29 16:42]
- あー、休憩中だからマジレス。
1よ、がんばれ。
＜問題＞
ある会社のセールスマンがいます。
このセールスマンは受け持ちの都市をすべて訪問して、仕事が終ったら戻ってこなければいけません。
同じ都市を２度訪問せずに、 最短距離ですべての都市をまわる経路を求めなさい。
問1
このセールスマンの受け持ちの都市をA,B,C,D,Eとし、出発点をAとすると、道順はいくつあるか？
問2は次の方の出題。
- 4 名前：名無しさん＠１周年 mailto:sage [02/01/29 20:00]
- 問2
問1を解け．
- 5 名前： [02/01/29 20:21]
- >>4
よくわからないけど、24通り？
最短距離とか意味不明
- 6 名前：名無しさん＠１周年 mailto:sage [02/01/29 21:20]
- >>5
俺も24通りだと思うが，最短経路という条件があるという問題だけに，答えに困るな．
つか，>>4は>>3の最後の行に突っ込んでるネタなんで，マジレスされても困る．
困ってばかりの俺に乾杯！
- 7 名前：タモリ mailto:sage [02/01/29 21:23]
- ここで一旦，困っちゃう．
- 8 名前：名無しさん＠１周年 mailto:sage [02/01/29 21:40]
- アニーリング法だっけか，懐かしいな
- 9 名前：3 [02/01/29 23:15]
- 最短経路作る暇がなかったので、スマソ。
で、問2を出す人が、経路図作ってくれたらなぁ、と密かな期待
数学パズル本には必ず出てくるね、巡回セールスと、一筆書きと、4色問題
- 10 名前：g [02/01/30 00:46]
- ★楽してお小遣い★
簡単・安心・在宅ワーク可能
興味のある方は下記をクリック！！
members.aol.com/hnworld/
- 11 名前：名無しさん＠１周年 [02/01/30 14:21]
- エネルギー関数ってどうやって求めるの？
- 12 名前：名無しさん＠１周年 [02/01/30 19:17]
- 遺伝的アルゴリズム使えよ、お前ら。
- 13 名前：名無しさん＠１周年 mailto:sage [02/01/30 19:31]
- セールスマンなら，考える前に足を使え．基本を忘れるな！
- 14 名前： [02/01/30 20:53]
- ねえ重みとかの計算はわかったんだけどエネルギー関数ってどうやって求めるの？
- 15 名前：名無しさん＠１周年 mailto:sage [02/01/30 21:33]
- >>14
魚屋で売ってるから，買ってこい．
生で食うなよ，腹壊すから．
- 16 名前：名無しさん＠１周年 [02/01/30 22:21]
- 昨日、近所の吉野家行ったんです。吉野家。
そしたらなんか人がめちゃくちゃいっぱいで座れないんです。
で、よく見たらなんか垂れ幕下がってて、１５０円引き、とか書いてあるんです。
もうね、アホかと。馬鹿かと。
お前らな、１５０円引き如きで普段来てない吉野家に来てんじゃねーよ、ボケが。
１５０円だよ、１５０円。
なんか親子連れとかもいるし。一家４人で吉野家か。おめでてーな。
よーしパパ特盛頼んじゃうぞー、とか言ってるの。もう見てらんない。
お前らな、１５０円やるからその席空けろと。
吉野家ってのはな、もっと殺伐としてるべきなんだよ。
Ｕの字テーブルの向かいに座った奴といつ喧嘩が始まってもおかしくない、
刺すか刺されるか、そんな雰囲気がいいんじゃねーか。女子供は、すっこんでろ。
で、やっと座れたかと思ったら、隣の奴が、大盛つゆだくで、とか言ってるんです。
そこでまたぶち切れですよ。
あのな、つゆだくなんてきょうび流行んねーんだよ。ボケが。
得意げな顔して何が、つゆだくで、だ。
お前は本当につゆだくを食いたいのかと問いたい。問い詰めたい。小１時間問い詰めたい。
お前、つゆだくって言いたいだけちゃうんかと。
吉野家通の俺から言わせてもらえば今、吉野家通の間での最新流行はやっぱり、
ねぎだく、これだね。
大盛りねぎだくギョク。これが通の頼み方。
ねぎだくってのはねぎが多めに入ってる。そん代わり肉が少なめ。これ。
で、それに大盛りギョク（玉子）。これ最強。
しかしこれを頼むと次から店員にマークされるという危険も伴う、諸刃の剣。
素人にはお薦め出来ない。
まあお前らド素人は、牛鮭定食でも食ってなさいってこった。
- 17 名前：1 [02/01/31 00:05]
- 今ごろになって得意気コピペされるシミュ板の悲しさよ。
- 18 名前： [02/01/31 17:16]
- >>17
ねえエネルギー関数の求め方教えろ
- 19 名前：名無しさん＠１周年 mailto:sage [02/01/31 20:04]
- >>16
まんまじゃねぇかよ！
- 20 名前：名無しさん＠１周年 mailto:sage [02/02/01 10:27]
- imadoki ORIGINAL toha...
- 21 名前：名無しさん＠１周年 mailto:sage [02/04/14 16:28]
- なんでこのすれまがじそに載ってるの？>>16神？
なこたーないか
＼(｀Д´ )ノｴｰｲ ｼﾈｼﾈ
- 22 名前：名無しさん＠１周年 [02/05/17 18:25]
- 吉野家で>>1が刃物振り回し３人死亡
東京都新宿区新宿三丁目の飲食店「吉野家」で２４日午後５時ごろ、「客が刺された」と
男性従業員から１１９番通報があった。４０歳代の男性とその家族とみられる女性や子供
がテーブル脇で倒れており、警視庁はその場に居合わせた無職>>1（23）を殺人の疑い
で逮捕し、取り調べている。
調べによると>>1は２４日午後４時ごろ同飲食店に一人で立ち寄り、「大盛りね
ぎだくギョク」と叫んだのち、突然テーブルの反対側に座っていた家族連れの男性に因縁
をつけたうえ、突然持参したナイフで刺したという。警視庁の調べに対して>>1
は、「向かいのテーブルの家族連れが楽しそうに特盛(つゆだく)を注文したのが許せなく、小一時間
問い詰めたかった。殺伐とした雰囲気が欲しかった。」などと意味不明の内容を話してい
るといい、警視庁でさらに詳しい事情を調べている
- 23 名前：名無しさん＠１周年 mailto:sage [02/05/18 18:10]
- ほっぷふぃーるどでとけ！
- 24 名前：名無しさん＠１周年 [02/05/24 17:30]
- 解決？
- 25 名前：名無しさん＠１周年 mailto:sage [02/06/11 15:47]
- おいおい、正統派はちゃんとDPで解けYO
時間かかり過ぎるけど （w
- 26 名前：名無しさん＠１周年 [02/12/06 13:21]
- 巡回セールスマン問題についての質問です。
ネットで検索したのですが載っていませんでした。
Att532で距離を測る場合
long int length(int i, int j, int *x)
/* p[x[i%n]]とp[x[j%n]]のユークリッド距離 */
/* データatt532の定義に従って計算 */
{
int l;
float ax, ay, a, b;
a=(p[x[i%n]].x-p[x[j%n]].x)*(p[x[i%n]].x-p[x[j%n]].x)
+(p[x[i%n]].y-p[x[j%n]].y)*(p[x[i%n]].y-p[x[j%n]].y);
a=a/10.0;
b=sqrt(a);
l=b;
if(l<b-0.001) l=l+1;
return(l);
}
となっており、このa=a/10.0はお約束のようですが
lin318やlin105,kroA200ではどのような値をとれば
よろしいのでしょうか。またそれはネット上のどこで見てるのでしょうか？
- 27 名前：名無しさん＠１周年 [02/12/06 23:31]
- www.nanoelectronics.jp/kaitai/dnacom/3.htm
- 28 名前：26 [02/12/09 15:03]
- >>26の質問
よろしくお願いします。
Att532では10で割っているので
lin318で6,lin105で2で割ってみましたが、
どうも解が良すぎたり悪すぎたりします。
どなたか巡回セールスマン問題を研究テーマ
にしている方いらっしゃいませんか？
- 29 名前：v [02/12/09 15:43]
- ★電話料金を請求しない優良なサイトのみをご紹介しています★
◆yahooo.s2.x-beat.com/linkvp/linkvp.html◆
- 30 名前：も [02/12/12 04:21]
- b -> cの通路は、夕食の材料を買い集めている主婦で込み合ってます。
a -> bの通路は、検問中です。
b -> fの通路は、自動車専用道です。
- 31 名前：名無しさん＠１周年 mailto:sage [02/12/15 15:23]
- グラフ理論でＴＳＰはやったな〜
巡回サンタクロースとかwebで考察されているのは
サンタが複数いたらとかいう本質でない問題を書いててばからしい
これの本質はどういうアルゴリズムで最短距離を求めるかなのに・・・
- 32 名前：名無しさん＠１周年 [02/12/21 02:21]
- 学部時代の研究テーマだったなぁ。
懐かしい・・・。
今はどのような手法で解くのが流行っているのかな？？
ニューラルネット？GA?
- 33 名前：名無しさん＠１周年 mailto:sage [02/12/21 03:28]
- 経路探索の模様をｸﾞﾗﾌｨｯｸ化したら、
うねうねするアレ好き。ﾆｭｰﾗﾙなのか。よーわからん。
>32
GAとSAとかをぶち込んだﾊｲﾌﾞﾘｯﾄﾞな探索ｱﾙｱﾙでない？
- 34 名前：名無しさん＠１周年 [02/12/24 02:24]
- これって応用数学とかでやるんですか？
- 35 名前：名無しさん＠１周年 [02/12/24 07:08]
- ？
- 36 名前：山崎渉 mailto:（＾＾）sage [03/01/11 05:23]
- （＾＾）
- 37 名前：名無しさん＠３周年 mailto:sage [03/03/03 19:22]
- >34
情報数学やアルゴリズムの授業で出てくるねえ．
グラフ理論の話の一環で出てこない事もないので，応用数学でも話がでるかも．
>32
厳密解法ならBranch and Cutと呼ばれる方法で15000都市の例題が解かれて
いるはず（数十台のコンピュータで並列計算して何週間も回したらしいが）
近似解法なら1970年頃にLK法と言うアルゴリズムが提案されており，多くの例題で
最適解から1-2%以内の誤差の精度を出している．
近年の研究はそれの改良もしくは亜流もしくはアルゴリズムの比較解析が主．
分かり易くて有名な問題なので，様々なベンチマーク問題として使われてはいるけど，
効率の良いアルゴリズムと言う意味では研究はすでに収束してる．
- 38 名前：山崎渉 mailto:（＾＾） [03/03/13 13:24]
- （＾＾）
- 39 名前：Nanashi_et_al. mailto:ばか [03/03/19 17:44]
- >37最適解から1-2%以内の誤差の精度を出している．
この表現はあまり意味がない。
ＴＳＰの面白みは、最適解と近似解がパターンではまったく違うことであるからだ。
問題の作りようによってはいかようにでも解（近時）は手に入る。
遊びのテーマにしたほうがいいぜ
- 40 名前：名無しさん＠３周年 [03/03/20 02:25]
- 量子コンピューターに期待
- 41 名前：名無しさん＠３周年 mailto:sage [03/03/21 00:49]
- ＴＳＰに対するアプローチについては
（多くの組合せ最適化問題についてもそうだけど）
・最適解を求める解法
・精度保証がある近似解を求める解法
・解の精度の保証はないけど，実用上良い解が得られる解法
が主なところで，研究者によって興味の視点が異なる．
>最適解から1-2%以内の誤差の精度を出している．
と言うのは３番目のアプローチで，理論家（数学者）にとってはどうでも
良い話だが，実務家（工学者）にとっては大事な話なので，それを意識
して議論をしないと話がかみ合わないですよ．
ちなみに
>問題の作りようによってはいかようにでも解（近時）は手に入る。
最適解が容易に得られる例題も簡単に作れるわけで，最適だから近似
だからと言うのは話がちょっと違うんでは？
- 42 名前：名無しさん＠３周年 mailto:sage [03/03/21 01:00]
- 多分>39さんは理論的なアプローチで考えていると思うのですが，
>最適解と近似解がパターンではまったく違う
そう言う例題が多く存在するだろうとは思いますが，
>問題の作りようによってはいかようにでも解（近時）は手に入る。
これは表現がまずいような気が・・・
任意の例題に対して最適解を求める解法，もしくは精度保証を持つ近似解法
を作るのが難しいから，それらが簡単に求まる例題のクラスを考えてみましょう
と言うのが元々の動機ですよね？
それを例題はユーザーの好きな様に与えていいんですよ，みたいな書き方を
したら何がなんだかわけがわからなくなるかなあと・・・
- 43 名前：名無しさん＠３周年 mailto:sage [03/03/21 01:05]
- まあ，ここじゃあ十分な話ができないから，お互い突っ込み入れてもあまり
意味無いから，そう言う意味では>39さんスイマセン(汗)
ＴＳＰは勉強するにはすごく面白い題材だけど，長年多くの人々によって
精力的に研究されて掘り尽くされてきたテーマでもあるので，これから
手をつけるには余り適さないですね．
これからやるなら，発展版のＶＲＰ(Vehicle Routing Problem)とかが，
良いんじゃあないでしょうか．
- 44 名前：Nanashi_et_al. mailto:ばか [03/03/25 23:50]
- >43
TSPは、キャバレーでも話題にできるポピュラーなものですね。
最初はやさしいが、さいごはむつかしい。
ときどき流行する。 またさめる。
VRPなんかは、ドライブのとき役に立つとおもうけど！
実際ノートPCでつかったりするけど、迷子になって逆効果！？？
期待しているぜ！
＞４２そう言う例題が多く存在するだろうとは思いますが，
ひとつでもとければ。。。。。
- 45 名前：名無しさん＠３周年 [03/03/26 16:10]
- 中国人郵便配達問題っていうのとは別物でつか？
- 46 名前：名無しさん＠３周年 mailto:sage [03/03/27 00:49]
- >44
>ひとつでもとければ。。。。。
巡回セールスマン問題が（多項式時間で）解けたと言うのは，
任意の例題（都市の配置）に対して（多項式時間で）最適解を与える
アルゴリズムを提示すると言うことです．
なので，ある特定の例題（都市の配置）に対して（多項式時間で）最適解を
与える事ができても，それは巡回セールスマン問題が解けたとはならない
のです．これはある特定の例題集合であっても同じ事です．
ただし，任意の例題に（多項式時間で）変換できるような例題集合があって，
それに対して（多項式時間で）最適解を与えるようなアルゴリズムができれば，
巡回セールスマン問題が（多項式時間で）解けたといえます．
- 47 名前：名無しさん＠３周年 mailto:sage [03/03/27 00:56]
- >45
巡回セールスマン問題は全部の都市を巡って初めの都市に戻って
来るのですが，中国人郵便配達問題は全部の「道」を通って（当然
，全ての都市も巡る）初めの都市に戻ってくる問題です．
ここで道とは全都市間の辺を指します．
グラフ理論で言うと，最短のハミルトン閉路を求める問題が
巡回セールスマン問題で，最短のオイラー閉路を求める問題が
中国人郵便配達問題になります．
ネーミングの理由とか問題の難しさは・・・どうだったっけなあ？
マッチングを上手く使うと解ける，と言う話をどこかの本で読んだような
気もするのですが記憶が定かでないです(汗)
- 48 名前：Nanashi_et_al. mailto:ばか [03/03/27 20:53]
- >46
ありがとうございます。 あなたの言われる意味で書いたつもりでしたが
わたしの表現はたしかにあまりにも貧弱で、内容がありませんでした。
もちろんあなたのいわれているほうがはるかにすぐれています。
またあなたのいわれていることまでEXPLICITに理解していませんでした。
ありがとうございます。
いつかおあいしたですな、 あるいはすでにあっているかな
- 49 名前：名無しさん＠３周年 [03/03/27 23:32]
- 218.44.246.37/~2ch/
- 50 名前：名無しさん＠３周年 [03/04/01 15:43]
- 確か、パーセプトロンの次のニューラルネットが出てきたときに、
相互結合型ＮＮで巡回セールスマン問題が解けましたよ。
相互結合型は、その時注目集めたけど、
明確な学習方法が提案されずに今は影の時代・・・・。
- 51 名前：名無しさん＠３周年 [03/04/01 16:10]
- すげ〜よ
homepage3.nifty.com/digikei/
- 52 名前：山崎渉 mailto:（＾＾） [03/04/17 08:53]
- （＾＾）
- 53 名前：山崎渉 mailto:（＾＾）sage [03/04/20 04:14]
- ∧＿∧
（ ＾＾ ）＜ ぬるぽ（＾＾）
- 54 名前：名無しさん＠３周年 [03/05/05 06:26]
- Job-shop Scheduling Problemsって何？
- 55 名前：無料 mailto:age [03/05/05 11:17]
- 入場無料！
ime.nu/www.net-de-dvd.com/
- 56 名前：ももえ [03/05/05 15:19]
- オススメ！カワイイ娘厳選の無料Hサイト☆！ 〜良心的です〜
www.yahoo2003.com/moe/linkvp.html
- 57 名前：_ mailto:ｓａｇｅ [03/05/05 15:20]
- ／:＼.＿＿＿_＼
|:￣＼(∩´∀｀) ＼ ＜先生！こんなのがありました！
|:在 |:￣￣ U￣:|
www.japan.pinkserver.com/kaorin/moe/jaz09.html
japan.pinkserver.com/kaorin/mona/index.html
www.japan.pinkserver.com/kaorin/moe/jaz10.html
japan.pinkserver.com/kaorin/moe/jaz08.html
www.japan.pinkserver.com/kaorin/moe/jaz07.html
japan.pinkserver.com/kaorin/moe/jaz03.html
www.japan.pinkserver.com/kaorin/moe/jaz05.html
japan.pinkserver.com/kaorin/moe/jaz01.html
www.japan.pinkserver.com/kaorin/moe/jaz06.html
japan.pinkserver.com/kaorin/moe/jaz04.html
www.japan.pinkserver.com/kaorin/moe/jaz02.html
- 58 名前：山崎渉 mailto:（＾＾） [03/05/21 21:51]
- ━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―
- 59 名前：山崎渉 mailto:（＾＾） [03/05/21 23:38]
- ━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―
- 60 名前：山崎渉 mailto:（＾＾） [03/05/28 14:25]
- ∧＿∧
ﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
- 61 名前：名無しさん＠３周年 mailto:sage [03/06/03 23:45]
- 俺の卒論、NNを使ったTSPの解放だった・・・。
いったい何の役に立つのかいまだにわからん。
もちろん、プリント基板などの応用、
ほかに基礎研究として重要なのはしっている。
ただ、実社会において役に立っているのか？？
- 62 名前：名無しさん＠３周年 mailto:sage [03/06/08 01:27]
- >>61
どこからどこまでを「実社会」だと思っているのかがわからん。
「プリント基板」は実社会じゃないのだろうか。
- 63 名前：山崎 渉 mailto:（＾＾） [03/07/12 12:39]
-
__∧＿∧_
|（ ＾＾ ）| ＜寝るぽ（＾＾）
|＼⌒⌒⌒＼
＼ |⌒⌒⌒~| 山崎渉
~￣￣￣￣
- 64 名前：山崎 渉 mailto:（＾＾） [03/07/15 12:45]
-
__∧＿∧_
|（ ＾＾ ）| ＜寝るぽ（＾＾）
|＼⌒⌒⌒＼
＼ |⌒⌒⌒~| 山崎渉
~￣￣￣￣
- 65 名前：山崎 渉 mailto:（＾＾）sage [03/08/02 02:32]
- ∧＿∧
（ ＾＾ ）＜ ぬるぽ（＾＾）
- 66 名前：ぼるじょあ ◆yBEncckFOU mailto:（＾＾） [03/08/02 03:07]
- ∧＿∧ ∧＿∧
ﾋﾟｭ.ｰ （ ・３・） ( ＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
＝〔~∪￣￣￣∪￣￣〕
＝ ◎――――――◎ 山崎渉&ぼるじょあ
- 67 名前：名無しさん＠３周年 [03/08/06 20:07]
- ☆ ☆ ☆ www.gals-cafe.com ☆ ☆ ☆
まみでっす！みんな元気ぃ？夏だねーーー！
あたしね、今どこにいると思う？えへっ、実はアメリカなんだぁ。
でもアナタに逢いたくて、こーんなバイト始めちゃった♪
まみに逢いに来てくれたら、なんと7日間会費無料サービスだし、
しかもしかも10分間も無料なんだよ〜〜！すごいでしょ！
見てくれたアナタにだけの特別サービス！今すぐきて！
二人っきりで楽しいことしようよ！まってるね！
☆ ☆ ☆ www.gals-cafe.com ☆ ☆ ☆
- 68 名前：_ mailto:sage [03/08/06 20:31]
- homepage.mac.com/hiroyuki45
- 69 名前：_ mailto:sage [03/08/06 20:49]
- homepage.mac.com/hiroyuki45/hankaku05.html
- 70 名前：山崎 渉 mailto:（＾＾） [03/08/15 17:57]
- (⌒V⌒)
│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
⊂| |つ
（＿）（＿） 山崎パン
- 71 名前：名無しさん＠３周年 [03/09/08 06:02]
- age
- 72 名前： [03/09/08 11:27]
- www.ro-ch.net/bijou/source/20030908060239_a.jpg
- 73 名前：名無しさん＠３周年 [03/09/08 16:10]
- 【不幸のレス】
このレスを見た人間は七日以内に死にます。
※あなたに訪れる死を回避する方法が一つだけあります。
それはこのコピペを一時間以内に７つ、別のスレに貼り付ける事です。
- 74 名前：名無しさん＠３周年 [03/12/01 19:19]
- >>1
どういうルートを回るのが最短かっての。
でも、実際は、会う順番がある。
最短ルートを取らないケースが多々。
- 75 名前：名無しさん＠３周年 [03/12/06 16:02]
- EAX：催促計算手法
- 76 名前：名無しさん＠３周年 [04/01/18 18:59]
- SOM 使えばかなり高速に近似解得られるよ
- 77 名前：名無しさん＠３周年 [04/01/28 01:08]
- シミュテーティッドアニーリング法で、解決できると聞いたので、
もう終わっていないの?
- 78 名前：名無しさん＠３周年 [04/01/28 01:35]
- それより新シャア板言ってみな、糞スレ乱立でかなりすごいことになっている。
糞スレ祭りですよ！！マジ凄い！他板からも糞スレ立てに大勢来ているもよう！
マジ凄いからすぐにこい！！板が閉鎖される前に早く早く！！！！
- 79 名前：名無しさん＠３周年 [04/02/22 08:11]
- 巡回距離は最小に近いのに、経路の様子が全然違うパスがたくさんあるね。
- 80 名前：名無しさん＠３周年 [04/02/22 20:39]
- TSP・・・それは幾人もの偉人達が挑み続け、誰一人勝つことの出来なかった壁
- 81 名前：名無しさん＠３周年 [04/03/22 00:56]
- この前、別分野の学生からの話で、ant colony optimizationっての
きいたんだけど、TSPにつかってるみたい。
これが、経路探索でうねうねするっていってたやつ？
- 82 名前：名無しさん＠３周年 mailto:sage [04/03/22 08:06]
- >>81
大勢のアリたちがうねうねするやつ。
- 83 名前：名無しさん＠３周年 [04/03/22 20:17]
- 巡回セールスマン問題に限らず、NP困難問題をDNAコンピュータで解く手法があるよね。
理屈はわかるんだけど、なんかしっくりこないんだよなぁ…。
- 84 名前：名無しさん＠３周年 [04/03/26 02:06]
- ユークリッド平面の巡回セールスマン問題は
多項式時間で最適解にいくらでも近づけることができる
アルゴリズムが存在する
- 85 名前：名無しさん＠３周年 [04/04/24 02:52]
- アナログコンピュータならNP問題が簡単に解けるなどという妄説をはくひとが
いるが、それはまったくの間違い。連続体は物理的な実在ではないし、熱的ゆらぎ
に相当するノイズが常に伴うことを理解していない。精度無限大のアナログ
的実在は妄想に過ぎない。液体のようなものも、どこかで分子性が姿をあらわす
ときがある。
NP困難な問題をアナログ方式ガジェット(計算機)で高速に解けるという
ことが間違っていることと、物理の非可逆の起源とは相通じるものが
ある。量子コンピュータも、巨視的量子現象を用いない限りは、
アナログ性から来る、確率分布の拡散によりコヒーレンスを急速に
失って、その高速な計算は夢物語になる公算が大きい。
- 86 名前：名無しさん＠３周年 [04/04/24 07:17]
-
ド―――――――――――――――――――――――ン！
- 87 名前：名無しさん＠３周年 [04/04/25 17:30]
- 最近は中国人郵便配達問題といったほうがいいのかな？
- 88 名前：名無しさん＠３周年 [04/04/25 20:59]
- 中国人郵便配達問題とは違うはずです。
セールスマン：全ての点を通過する
中国人：全ての道を通過する
- 89 名前：名無しさん＠３周年 [04/05/02 01:32]
-
セールスマン：全ての点を通過する
中国人：全ての道を通過する
文化大革命中大学から追放された教授がハケーン。
実際の郵便屋がどうやって経路を決めるかついて歩いた。
- 90 名前：昔、名無しありけり [04/05/07 00:32]
- たとえばこれって中央出版とかモデル？
- 91 名前：名無しさん＠３周年 mailto:sage [04/05/07 21:35]
- >>83
DNAコンピュータってのは要するに並列度が極端に高い並列計算機だと
思えばよく、問題の探索空間のサイズ＜＜プロセッサ数ならば非決定性
アルゴリズムが適用できてるのと同じ。
非決定性アルゴリズムが適用できれば、定義によりNP困難問題が線形時間で
解けて当然。
・・・という解釈はどう？ちょっと強引？
- 92 名前：外務員 mailto:sage [04/05/09 09:38]
- 「巡回セールス」で検索したら
２ちゃんねるの、しかも、こんな辺境の、糞スレに迷い込んでしまった。
- 93 名前：名無しさん＠３周年 mailto:sage [04/05/28 03:05]
- pu
- 94 名前：名無しさん＠３周年 [04/07/04 09:15]
- TSPLIBにある例題ってどう読むの？？対称TSPで書かれている数字は
都市の座標と距離なんですか？？マジわからないのでお願いします。
- 95 名前：名無しさん＠３周年 [04/07/30 00:00]
- >>94
単純に左から「都市番号」「都市のx座標」「都市のy座標」では。
ちなみに都市間距離の計算には気をつけるべし。小数点以下の扱いを
注意しないと最適解が違ってくる可能性がある。
- 96 名前：名無しさん＠３周年 mailto:sage [04/11/22 02:11:16]
- カオスニューロを使えば楽勝でとけるよ
- 97 名前：名無しさん＠３周年 [2005/08/26(金) 14:33:44 ]
- >>94
英語嫁
- 98 名前：ひま人 [2005/08/26(金) 14:35:41 ]
- 難しい話してんねぇ〜
- 99 名前：名無しさん＠５周年 [2005/09/07(水) 23:14:19 ]
- シミュ板ってこーゆー2３年前のスレがたくさん残っているから、
好きだよ♥
- 100 名前：名無しさん＠５周年 [2005/09/09(金) 01:07:33 ]
- >>88
＞セールスマン：全ての点を通過する
＞中国人：全ての道を通過する
それって双対グラフに過ぎないのでは？
- 101 名前：名無しさん＠そうだ選挙に行こう [2005/09/11(日) 11:10:58 ]
- 「ハミルトンとオイラー」「セールスマンと中国人郵便配達」は
おおむね相対関係にある。
ハミルトン回路：すべての点を一度ずつ通れるか？
オイラー回路：すべての道を一度ずつ通れるか？
セールスマン：すべての点を一度ずつ通る最短経路は？
中国人郵便配達：すべての道を通る最短経路は？
(ただし、同じ道を何度通ってもよい)
- 102 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2005/09/11(日) 14:36:03 ]
- >100
そりゃ平面グラフで考えるからだろ
これらの問題は，一般の有向・無向グラフで定義されており，
平面上で定義されているわけではない．
- 103 名前：名無しさん＠そうだ選挙に行こう [2005/09/11(日) 16:08:16 ]
- 双対グラフは点⇔領域または辺⇔辺の双対であって、点⇔辺の双対ではないにゃ。
- 104 名前：名無しさん＠５周年 [2005/09/22(木) 13:08:04 ]
- Lee-Kernighan法って、現時点でのTSPチャンピオンプログラムでしょ？
1970年頃に考えられたアルゴリズムなんだ・・・
こりゃー、敷居が高い罠
- 105 名前：名無しさん＠５周年 mailto:sage [2005/09/23(金) 22:14:45 ]
- >104
LeeじゃなくてLinだぞ･･･
- 106 名前：名無しさん＠５周年 [2005/09/27(火) 11:53:23 ]
- Annals of operations research
- 107 名前：名無しさん＠５周年 [2005/10/26(水) 00:37:09 ]
- or-optだよ
- 108 名前：名無しさん＠５周年 [2005/11/06(日) 23:41:00 ]
- その前に
P=NP
が成り立つか証明してくれ
- 109 名前：名無しさん＠５周年 [2007/06/14(木) 23:22:38 ]
- 全く理解ができない件
- 110 名前：名無しさん＠５周年 [2008/04/15(火) 20:30:21 ]
- 笑ゥせぇる済まん
- 111 名前：名無しさん＠５周年 [2008/04/16(水) 00:02:06 ]
- >>104
これ本当なんでしょうか？
本当としたらこれ研究している人ってずっと何もやってないということか。
いろんな知見が得られたというかもしれないけど、
それは1970年代にすでに気づかれていたことなんじゃないかな。
- 112 名前：名無しさん＠５周年 [2008/04/19(土) 20:18:44 ]
- 解ではなく、手法
- 113 名前：名無しさん＠５周年 [2008/05/25(日) 01:21:06 ]
- 気合いが足りないのは完全なセールスマンが巡回するのですか？
数学が問題の理解が足りませんか？1。
- 114 名前：名無しさん＠５周年 mailto:sage [2008/05/25(日) 20:09:49 ]
- お〜れのチンポのマッスルが〜♪
- 115 名前：名無しさん＠５周年 [2008/07/21(月) 20:49:13 ]
- 巡回セールスマン問題についての感想を書く問題があるのですが、どのように書いたらいいんですか？
|
 |
