計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 411 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 19:39:16 ] >>409 www.amazon.co.jp/gp/product/476490277X/ www.amazon.co.jp/gp/product/4795263213/ 412 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 20:20:48 ] >>411 ありがとうございます！ 早速買ってこようとおもいます。本当にありがとうございました。 413 名前：デフォルトの名無しさん [2006/11/19(日) 20:44:17 ] shear sort実装してテストしてみたんだが、std::sortに比べて遅い・・・ int型で要素数2^16程度だと何回か繰り返してみたが25倍程度遅く、 2^32程度だと１回のテストで1000倍程度遅かった。 coreが1個だとオーダも悪いね。n個もcoreがあるなら、 quick sortでも順次分けていけるようなきがするし、 メモリを飛び飛びにアクセスして書き換えるから並列処理にも合ってない気がする。 414 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 21:06:23 ] O(n log n) を切れるソートって、かなり特殊な前提がないと使えないんじゃないの？ データの数と同じだけプロセッサがあるなら、 バブルソートでも O(n) でしょ、確か。 その Shear ソートも、そういう前提の下で O(√n) とかではないの？ 415 名前：デフォルトの名無しさん [2006/12/13(水) 12:06:49 ] 「ｍ個の数字集合からｎ(0〜ｍ)個の組み合わせを比較し、指定値Ｘ以上かつ最小の組み合わせを求める。」 こういうプログラムを作りたいのですが、どうアルゴリズムを組めばいいのかわかりません。 どなたかお願いします。 例 インプット 　数字集合：5,7,10,12,15 　指定値：18 　↓数字集合の組み合わせで、『指定値』以上かつ最小の組み合わせを求める。 アウトプット 　最小合計値の組み合わせ：7+12=19 416 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 12:34:57 ] >>415 アルゴリズムを説明すれば自分でプログラム書けるの？ プログラム書いてほしいとか言うのは宿題スレいってくれ 417 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 12:50:26 ] ナップサック問題のバリエーション？ 418 名前：415 mailto:sage [2006/12/13(水) 12:50:50 ] >>416 アルゴリズムによってはプログラムで書けるか分からないので、宿題スレに行きます。 419 名前：429 mailto:sage [2006/12/13(水) 13:26:11 ] 415ではないが移動先はっとく pc8.2ch.net/test/read.cgi/tech/1165943509/22/ 420 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 14:16:15 ] >>417 Subset Sum Problem という有名 NP （の、最適化問題版）。 まあバリエーションといえばそうなんだけど、知ってて損はない名前よ。 421 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 14:37:22 ] 問題から推測すると集合の最大値は指定値をより小さいのかな 422 名前：415 mailto:sage [2006/12/13(水) 15:15:11 ] >>419 お手数おかけしました。 >>417>>420 有名な問題なのですね。 名前自体しらなかったです。 >>421 集合の全合計値より、指定値が小さいという意味ならそうです。 423 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 17:46:53 ] sqrt(O(N^2)の処理)の計算量が知りたいのですが sqrtの計算量わかる人いますか 424 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 19:59:02 ] >>423 sqrt( O(N^2) の処理 ) という記号の意味がわからん。処理の平方根って何。 具体的にどんなことをしているかを書いたほうが正しい解が得られると思われる。 425 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 00:00:12 ] ひょっとして多倍長計算？ ニュートン法なら一回の反復で桁数２倍 426 名前：426 mailto:sage [2007/01/24(水) 15:42:39 ] ttp://www.apple.com/jp/downloads/dashboard/developer/colourmod.html このようなカラーピッカーを作りたいのだけれど、 中心からの位置によってどのようなRGBに変換されるかの式がわかりません。 どうやって計算しているのでしょう？ 427 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 15:46:57 ] >>426 ttp://image-d.isp.jp/commentary/color_cformula/HSV.html Hが円角度 Sが円半径 Vが隣の垂直ﾊﾞｰ　じゃねーかな？ 428 名前：426 mailto:sage [2007/01/24(水) 15:54:15 ] >>427 ありがとう、作ってみます 429 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 16:01:43 ] >>428 変な色マップになったら　同サイトの HLS変換も試してみてね 430 名前：426 mailto:sage [2007/01/24(水) 16:58:12 ] >>429 おかげさまで出来ました。atanの戻り値[-pi/2,pi/2]を[0,360]に変換するのにミスったのと 427さんに紹介してもらったページのFの式が間違っていた（正しくはF = H/60 - I）ので ちょっとだけ手間取りましたが、無事きれいなカラーサークルになりました。 ありがとうございました。 431 名前：デフォルトの名無しさん [2007/01/24(水) 17:14:29 ] 強欲アルゴリズムについて分かる人はいますか？ 432 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 17:32:15 ] 貪欲とかgreedyとかで検索したらどうだろう。 433 名前：デフォルトの名無しさん [2007/01/24(水) 17:36:37 ] それがなくて… 434 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 19:08:19 ] 俺はだいたいのところは分かっていると思うぜ 435 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 19:27:16 ] >>430 atan2使えばいいんじゃね？ 436 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 06:11:36 ] 長さが同じint配列が2個ある。 一つの配列内で重複する数は無い。 同じ数がそれぞれの配列で同じ位置にあるとは限らない。 で、一方の配列内に入ってる数が全て他方の配列にも入っているかを確認したい。 こういう場合で配列をそれぞれソートして 先頭から最後まで一致するかを調べる以外に何かいい方法ある？ 437 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 07:12:23 ] それは set equality problem という問題で， O(n log n) が計算量下界であることが知られている． よって，計算量的には 436 のソート比較は最適． ハッシュとか確率的アルゴリズムとかで実用的な速度は 上がるかもしれんが，ソート比較が簡素で良いと思うよ． 438 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 09:06:29 ] >>437 なるほど。 ありがとう。 439 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 09:26:09 ] >438 データの範囲が狭ければ有無の配列(データが添字)を使ってO(n)で可能 データに対して有効なハッシュ関数があれば広くても同上 440 名前：デフォルトの名無しさん mailto:sage [2007/01/27(土) 00:38:31 ] データの個数があんまり多くないからソート比較でも十分速くできた。 >>439 >>437でハッシュと聞いてピンと来た。 機会があれば今度その方法も試してみるよ。 ありがとう。 441 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 14:13:28 ] 有無なら配列じゃなくてビットマップにしろや 442 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 11:48:52 ] >441 もしかして：ビットの［配列］ 443 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 14:05:22 ] >>441 アルゴリズムと実装は区別しような 分からなかったらスレッド名も見てくれ 444 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 23:26:47 ] >>443 言葉遊びがしたいのか？ アルゴリズムと実装でいうならどう実装をしようが配列は配列 最適化の話がしたいならアセンブラスレでも逝け 445 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 00:44:54 ] >>444 444=441 ? とりあえず君の配列の定義が知りたい。 アルゴリズム論の文脈では、実装における配列と理論における 配列はまったく対応しない可能性があるけど、それは大丈夫？ 446 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 10:54:45 ] え〜い面倒くせえ ビットマップ＝ビットの配列 でFAだろ 447 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 12:10:45 ] まぁ、普通そんなこと言わんがな。 448 名前：デフォルトの名無しさん mailto:sage [2007/02/08(木) 15:47:29 ] ある会計（０円〜９９９円）を行う際に 一回の硬貨のやり取り（渡す枚数+受け取る枚数）を最小にするアルゴリズム 考えているんだけど思いつかない・・・助けてくれ 449 名前：デフォルトの名無しさん mailto:sage [2007/02/08(木) 16:32:47 ] void minimumExchange(int account) { 　　int pay = account; 　　int min = getCount(account); 　　for (int i = account + 1; i < 1000; i++) { 　　　　int c = getCount(i) + getCount(i - account); 　　　　if (c < min) { 　　　　　　pay = i; 　　　　　　min = c; 　　　　} 　　} 　　System.out.println("account=" + account + " pay=" + pay + " min=" + min); } int getCount(int n) { 　　int c = n/500; 　　n %= 500; 　　c += n/100; 　　n %= 100; 　　c += n/50; 　　n %= 50; 　　c += n/10; 　　n %= 10; 　　c += n/5; 　　n %= 5; 　　return c + n; } 450 名前：デフォルトの名無しさん mailto:sage [2007/02/08(木) 17:16:55 ] ちょっと修正 ＞　　for (int i = account + 1; i < 1000; i++) { を 　　for (int i = account + 1; i <= 10000; i++) { ＞int getCount(int n) { を int getCount(int n) { 　　n %= 1000; アルゴリズムを考える時はまず、最も分かりやすい方法（しらみつぶしとか）を考えるといいと思います。 それでダメならそれから工夫する事を考えればいいのですが、大抵はそのままでも大丈夫です。 ＃「硬貨のやり取りが最小」とは別に紙幣を払ってもいいのですね。 451 名前：デフォルトの名無しさん mailto:sage [2007/02/09(金) 22:24:47 ] 1円札から999円札まで1円単位の紙幣を使ってもいいんですよね 特に条件が指定されてないので 452 名前：デフォルトの名無しさん mailto:sage [2007/02/09(金) 22:28:43 ] 999円札なんて無いだろ 常識で考えれ 1円札を999枚使うんだ 453 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 08:59:48 ] >>452 >1円札を999枚使うんだ 現在有効なお金 ttp://www.boj.or.jp/type/list/yuko/okane.htm 一円券は今でも有効だから使用は違法ではないし 常識で考えて不可能というわけではないな。 つまり「現在発行されている」という条件がない限り、 硬貨のやり取りは常に0が最小というわけだ。 一本取られたな。 454 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 14:08:01 ] でも一円札とかって１円より価値あるよな 455 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 14:24:42 ] 貨幣として使う分には１円だ。 456 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 14:26:34 ] そこでコイン商やオクだな 457 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 15:35:02 ] 買いたい人が*いれば*ね。 はっきり言わせてもらうと、一円札程度なら、札束で無いと誰も買わないよ。 458 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 20:53:26 ] 金融恐慌時の裏面がすってないお札なんかは高かったりするのだろうか 459 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 22:02:58 ] 刷られた数 使用された期間 現存数 等は少なければ少ないほど良い どんなにいらなそうな物でもコレクターにとっては価値がある 460 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 03:28:54 ] そういえばうちの親父が記念硬貨とか集めてたな。 天皇陛下御在位６０年1万円硬貨とか。 461 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 10:21:21 ] 売りたい人は山のようにいるから。 462 名前：デフォルトの名無しさん [2007/03/03(土) 14:04:36 ] 質問よろしいですか。 ２次元空間上に重複して平面が沢山（簡単のため長方形で）ありました。 ある点を選んだとき、その位置を含む平面の集合が欲しいのですが、 どんなアルゴリズムがいいでしょう？ よくある問題っぽいですね、もし問題に名前がついてたら、それだけでも 教えていただけると助かります。 463 名前：デフォルトの名無しさん mailto:sage [2007/03/03(土) 15:16:32 ] ん？ たとえばＡ４用紙の束かなんかを床に撒き散らしてから、ピンを一本床に突き刺す。 ピンが刺さっている紙を全部調べよう って問題？ 464 名前：デフォルトの名無しさん mailto:sage [2007/03/03(土) 17:58:17 ] >>463 ピンを横に置くんじゃないの？ 465 名前：デフォルトの名無しさん [2007/03/04(日) 09:59:17 ] 長方形と点のコリジョンだね。元データをグリッドに分割しておくのが 普通かな？２次元だと正方形や可変サイズのグリッドとか ツリー状（検索を対数的なオーダーに減らす）にしておくとかいろいろ種類はあるよ。 466 名前：デフォルトの名無しさん mailto:sage [2007/03/04(日) 10:41:11 ] 重複していない空間の分割なら、もっと簡単なのだから 平面を全部領域別けして、その領域にリンクリストで平面を割り付けるのが簡単じゃないのかな 467 名前：デフォルトの名無しさん [2007/03/04(日) 11:15:36 ] 六十周年金貨はあったけど 五十周年金貨ってなかったよね？ 468 名前：462 [2007/03/04(日) 18:16:51 ] そうです、紙をピン止めみたいな奴です。 3次元に拡張するために、かなりの広さで使うため、グリッドにするのは無理なもので、木にできると嬉しいです。 実装は難しくてもかまいません。 469 名前：デフォルトの名無しさん mailto:sage [2007/03/04(日) 19:08:06 ] 長方形は固定で点がいろいろ与えられるって考えていいのかな 今適当に考えただけだけど 最初に排他的な長方形の集合を探してR1とする (多い方がいいけど最大独立点集合問題はNP困難なので適当でいい） R1に含まれてない長方形の中から排他的な集合を探してR2とする。 これを再帰的に繰り返す。 点が与えられたらR1から順番にどの長方形に入ってるか調べればいい。 全部の長方形が重なってたらそれぞれ1つの要素からなる集合になるから 結局全部チェックしなきゃいけなくなってしまうのでダメ。 もっといい方法があるのかもしれん。 470 名前：デフォルトの名無しさん mailto:sage [2007/03/04(日) 19:10:09 ] 空間を超平面で切って平面集合を2つに分ける。 両方に属する平面があってもよいが、できるだけ2分するような超平面を選ぶ。 探索は点がどちらの超空間に属するかを調べて属するほうの平面集合を総当りで調べる。 これで全部の平面を総当りよりおよそ1/2の計算量になる。 あとはこれを再帰で最終的に完全二分木に近い形で分割できればOK。 471 名前：462 [2007/03/05(月) 01:18:32 ] 空間を超平面で切るってのは、いわゆるBSP木みたいなもんですよね。 その場合平面が両方の空間に属すると、両方の枝に平面を登録することになるわけで。 例えば一番最後に全部を覆う大きさの平面が入ってきたら、その平面を分割しまくら なくちゃいけなかったり、データ量が問題になるかな、というのが現在の悩みです。 472 名前：デフォルトの名無しさん mailto:sage [2007/03/05(月) 03:30:57 ] 閾値より大きな領域は、別段そのツリー内に入れなければいいのでは？ 単一の構造にする必要性も無いし、BSPは静的なものだけにすればいいし。 473 名前：デフォルトの名無しさん mailto:sage [2007/03/05(月) 20:42:16 ] 空間を平面で切るときに ・一方の空間に完全に属する領域の集合（２つ） ・断面と交わる領域の集合 の３つに分けてみるのはどうか．こうすれば各領域は必ず一箇所に属する． 探索するときは，断面上の領域と点の落ちる空間内の領域の２つを調べる． 断面と交わる領域の格納は 数が少ないとき（多分，n < (log(n))^d'（d'は断面の次元）のとき）は単純なリスト 数が多いときは１つ次元を落とした同様の構造にする よくわからないけど最終的には (log(n))^d （dは次元）←適当 あたりになりそうな気がする． 474 名前：デフォルトの名無しさん mailto:sage [2007/03/05(月) 21:19:27 ] >470-471 >473 なぜ一般次元に拡張を… 応用が利くのは良いっちゃあ良いんだけど微妙 475 名前：462 [2007/03/06(火) 01:07:58 ] >>472 大きいというか、重複が多い場合に結構問題になるんです。 今回は空間全ての領域で少なくとも３枚は被さっているのを想定してるんで、 必要な記憶領域がかなり大きくなってしまうという。 >>473 あ、そうか、２つとも探索すればいいんですね。 １次元で紙に書いてみたら、いけそうな感じです。 記憶領域はO(n)ですね、計算量もちょい大き目のlog(n)っぽい。 よーし、明日の夜にでも組んでみます。 476 名前：デフォルトの名無しさん mailto:sage [2007/03/06(火) 20:33:21 ] こーいうのって全くの別人が同時期に同じ解法を求める事ってないよな。 特定(ry 477 名前：デフォルトの名無しさん mailto:sage [2007/03/06(火) 21:20:05 ] 空間を分けるってちゃんと図形の配置を考えてやるの? そうじゃないならどこかで打ちきるわけだから計算量は何分の一かになるだけ それに重なってるところは分割できないので結局全探索になる 478 名前：462 mailto:sage [2007/03/07(水) 00:33:13 ] 473氏の方法をちょっと変えた物で、無事実装完了しました。今のところい い感じに動いています。ありがとうございました。 479 名前：デフォルトの名無しさん [2007/03/07(水) 23:42:48 ] 高卒でしかも数II？とか勉強いたことない俺にはまったく理解できないんだが どうすりゃいい？ 480 名前：デフォルトの名無しさん mailto:sage [2007/03/07(水) 23:44:26 ] 絵を描いてみる 諦める 481 名前：デフォルトの名無しさん mailto:sage [2007/03/08(木) 00:10:43 ] >>479 余り気付かれていないが、高校生ではなくても高校レベルの数学を 勉強することはできる。 482 名前：デフォルトの名無しさん mailto:sage [2007/03/08(木) 07:00:17 ] >>477 おまえ他人の言ってる事理解してないよ でしゃばるなカス 483 名前：デフォルトの名無しさん mailto:sage [2007/03/09(金) 00:58:56 ] >>482 理解できてないといって理由を書かない 484 名前：デフォルトの名無しさん [2007/03/10(土) 23:39:52 ] 自然科学なんかだと、実測データをグラフにプロットしたあと、なめらかな曲線でつないだりしますが、 そういう曲線を計算するアルゴリズムはありますか？ 485 名前：デフォルトの名無しさん mailto:sage [2007/03/10(土) 23:47:55 ] つ[Excel] 一般的なところで、一次回帰とその応用である対数回帰指数回帰冪乗回帰、それと二次回帰程度知ってればなんとでもなる。 486 名前：484 mailto:sage [2007/03/10(土) 23:49:18 ] ググってたらcurve fittingと呼ばれている問題だと分かりました。 すれを汚してすいませんでした。 487 名前：デフォルトの名無しさん mailto:sage [2007/03/10(土) 23:50:07 ] >>485 キーワードありがとうございます。 調べてみます。 488 名前：デフォルトの名無しさん mailto:sage [2007/03/11(日) 02:21:41 ] 最小二乗法とかね 489 名前：51 mailto:sage [2007/04/15(日) 21:22:27 ] SHA-1のハッシュを求めるプログラムを作ろうと調べていて ttp://homepage2.nifty.com/bkclass/doc_sha1.html のサイトを見ていたのですが、 他に参考になるサイトはありませんか？ 490 名前：デフォルトの名無しさん mailto:sage [2007/04/15(日) 21:54:51 ] Wikipedia(EN) 491 名前：デフォルトの名無しさん mailto:sage [2007/04/24(火) 04:03:28 ] 計算アルゴリズムには限界があり、結局は全部探索したほうが良いって結論？ 492 名前：デフォルトの名無しさん [2007/04/26(木) 00:56:22 ] そーでもないと思う。問題が大規模な場合はアルゴリズム使わないと無理だね。 でも、ノイズなんかの問題で理論的に最適な解が微妙な場合だったり、 問題が小規模で全探索で十分満足できる結果が得られるなら、全探索が 安定してるし実装が楽だからいいね。木構造はメモリリークよくやっち ゃうし。 493 名前：デフォルトの名無しさん [2007/04/26(木) 01:28:59 ] ２４シーズン�Xで解析に、独自のアルゴリズムを使って出す、とか言ってた。 494 名前：デフォルトの名無しさん mailto:sage [2007/04/26(木) 05:30:17 ] OR 495 名前：デフォルトの名無しさん [2007/05/01(火) 21:40:37 ] 今日専門の方でアルゴリズムの授業が行われたんですがその際この3問だけどうしてもわかりません 何方かこの3問のフローチャートがかける方が居ましたら教えてください 1問目：成績判定１ アルゴリズムの点数を入力して、80点以上のとき「Ａ」、60点以上80点未満の時「B」、60点未満の時「Ｃ」 と出力するフローを答えなさい 2問目：成績判定２ 英語と数学と国語の点数を入力して英語の点数が80点以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力するフローを答えなさい。 なお、数学と国語の点数がどちらも80点以上の時を一つの選択処理にすること 3問目：成績判定3 2-12.成績判定2の選択処理の部分を一つにまとめなさい 選択処理部分 英語の点数が80以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力する 496 名前：デフォルトの名無しさん [2007/05/01(火) 21:50:36 ] アルゴリズムじゃない。 そんくらいのフローチャートは基礎中の基礎だろ。本見ればわかるだろ。 497 名前：デフォルトの名無しさん [2007/05/01(火) 22:19:41 ] それが問題集しかもらってなくてわからないんですよ 498 名前：デフォルトの名無しさん mailto:sage [2007/05/01(火) 22:34:38 ] >>495 ttp://www.cs.takushoku-u.ac.jp/caed/kisosemi/k7/FlowChart.html これみりゃ大体わかるだろ。 いまどきフローチャートを書かせる問題ってのも、どうかと思うけれど。 スレ違いsage 499 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 14:45:41 ] 問題集しかもらってなくてわからないとか言うんだったら、 2chで質問する前にググれよ。っていうか授業ちゃんと聞いた上で わからないのであったら講師や友達に聞け。 500 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 19:47:24 ] ぐぐれる香具師 友達いる香具師 は 2chで質問しない 501 名前：デフォルトの名無しさん mailto:sage [2007/05/04(金) 00:08:57 ] 友達の作り方を教える本でも買った方がいいと思う。 502 名前：デフォルトの名無しさん mailto:sage [2007/05/04(金) 18:07:54 ] おとうさんはネットで調べても作れなかったけど 503 名前：デフォルトの名無しさん [2007/05/09(水) 01:56:23 ] グラフ探索でダイクストラやA*より良いのない？ それはそうとA*探索はぐぐるのが難しい。 504 名前：デフォルトの名無しさん mailto:sage [2007/05/09(水) 10:12:59 ] >>503 「Astar探索」とかでググってみたら？ ちなみにA*の場合、heuristicsがadmissible（各ノードから目的地までの予測コストが実際のコストを決して上回らない）でconsistent（いわゆる三角不等式が成立）なら、必ず最適解を返すよ。 それよりも良いってのは、heuristicsを設計できない場合ってこと？ 505 名前：デフォルトの名無しさん mailto:sage [2007/05/10(木) 07:32:41 ] どんな探索かわからんし、「良いの」って意味もわからんなあ。 506 名前：sage [2007/05/11(金) 04:14:25 ] >>504 そうですね、良いヒューリスティックを設計できない時です。 近似解法含め、良いのを探してます。 >>505 たしかに「良い」ってのはアバウトでした＾＾； 主観的にでも、よさげなアルゴリズムがないかなぁと。 検索してもダイクストラばっかり引っかかるもので。 507 名前：デフォルトの名無しさん mailto:sage [2007/05/11(金) 04:15:48 ] すみません、間違えて名前欄に書いてしまいました・・・ 508 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 10:47:07 ] 最短路探索ってことでいいの？ だとしたら、厳密最短路はたぶん理論的には Dijkstra が最良で、 実用的にはヒューリスティックに頼るってのが現在の理解だと思う。 （現在行われてるコンテストでもそんな調子だよね） 近似最短路はヒープ操作を手抜いたり、三角不等式を気にせずに ヒューリスティックを突っ込んだりするくらいだけど、 グラフが何の性質も持たない場合は性能評価が難しいところ。 509 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 16:40:43 ] ヒルス達がやってる６４個のソート問題ってどんな問題？ 510 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 16:44:37 ] クイックソート問題 511 名前：503 mailto:sage [2007/05/13(日) 18:40:21 ] つまりのところ、厳密解を求めるなら、あまり良くないヒューリスティック を用意した時、A*（と色々な改良版）が最速ってことですか。 というか、授業で習ったダイクストラとA*しか知らない物で＾＾； 近似についても、微妙な改良版くらいしかないって事ですね。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef