＜集大成＞アルゴリズム大辞典

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 403 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 11:21:56 ] 欠点は挿入ソートの欠点がそのままになっていて、データ数が多いときに少ないときに比べて遅くなります。 解決策として、２分挿入ソートが良さそうです。 ただ、さっきも書いたとおり、コムソート(バブルソートの改良)と挿入ソートの組み合わせという 単純なアルゴリズムで結構速し、特に欠点なしという所をアピールしたいので、まぁそのままで。 Javaの標準ライブラリとは同じぐらいの速さですが、興味があれば勝負させて見てください。でわ。 404 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 11:23:25 ] 「他の言語でも」が抜けてました。 405 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 13:01:44 ] 純粋なアルゴリズムの話じゃないけど、 今なら分散処理できるようなデータ構造やアルゴリズムの方が良いかもな。マルチコアだから。 406 名前：デフォルトの名無しさん mailto:sage [2008/06/05(木) 00:41:48 ] >>403 たった1000000個くらいのランダムデータに対しても std::sort() の1/2未満の性能しか出ないよ。 ソーティングの世界では一瞬でも遅いのは大きな欠点。 407 名前：デフォルトの名無しさん mailto:sage [2008/06/05(木) 09:11:39 ] >>406 その通りで。 あれから、VC++をダウンロードしてちょこっと試してみたんですが std::sort()の前にまずはCの標準のqsort()でやったところ qsort()の方が全然速かったです。qsort()の方がstd::sort()よりも速いのかもしれませんが 試す前にやめました。(C++をあまり知らないということもあって) 408 名前：デフォルトの名無しさん mailto:sage [2008/06/05(木) 23:21:04 ] たいていはstd::sortの方が早いんだけどね。 409 名前：デフォルトの名無しさん mailto:sage [2008/06/06(金) 00:23:30 ] STLPort使えよ 410 名前：デフォルトの名無しさん mailto:sage [2008/06/07(土) 17:13:13 ] 比較処理がインライン化される可能性のある std::sort の方が 確実にインライン化されない qsort よりも一般に速い。 411 名前：デフォルトの名無しさん mailto:sage [2008/06/21(土) 23:56:21 ] b+-treeに関する詳しい解説があまり見つからないんだけど、 要はb-treeとなにが違うの？ 突然の話題で申し訳ない。 412 名前：デフォルトの名無しさん mailto:sage [2008/06/22(日) 09:25:03 ] ttp://en.wikipedia.org/wiki/B%2B_tree 413 名前：デフォルトの名無しさん mailto:sage [2008/06/23(月) 00:55:46 ] >>411 葉にデータを集めたり、葉同士をリンクリストで繋げるなど、積め方を 工夫して末端の葉へのアクセスを単純にできるようにしたのがB+木。 (B木でもイテレーションは再帰やスタックでできるが) B+木のノードの追加削除は複雑で、手間の割にうまく実装しても速度は 素のB-Treeに劣る。空間効率は良くなるので外部記憶で使うとか、 構造上範囲検索で有利に働くので、それを多用するなら意味がある。 B木でもキャッシュやファイルマッピングが使える状況だと空間効率を除き 差はほとんどない。 414 名前：デフォルトの名無しさん mailto:sage [2008/07/03(木) 16:37:27 ] red-black-treeにおけるinsertやdeleteはいろいろなサイトに掲載されているのですが、 木の分割についてのアルゴリズムがどこを探しても見当たりません。 バランスを保ちながら木を2つに分割するアルゴリズムは存在しないのでしょうか? 415 名前：デフォルトの名無しさん mailto:sage [2008/07/04(金) 07:19:15 ] insertやdeleteを組み合わせればできるんでは 416 名前：デフォルトの名無しさん mailto:sage [2008/07/04(金) 22:53:42 ] て言うか分割って何？ 417 名前：414 mailto:sage [2008/07/04(金) 23:48:17 ] >>415 ありがとうございます。一応insertとdeleteの組み合わせではできたのですが もっと早い方法が無いのかと思って書き込みました。 もう少し考えてみます。 >>416 木をある値を境にして二つの木に分けたい、という意味です。 一つ一つのノードを木からdeleteして新しい木にinsertしなおせばできるのですが、 もっと単純にやる方法がないかと探しています。 418 名前：デフォルトの名無しさん mailto:sage [2008/07/05(土) 00:55:24 ] >>417 > 木をある値を境にして二つの木に分けたい 任意の値と言うこと？ なんかいい方法ありそうなが気がするが、俺の頭では無理だ...。 419 名前：415 mailto:sage [2008/07/05(土) 13:40:03 ] 順序はできてるんだから、適当に並べ替えるだけかと。 420 名前：デフォルトの名無しさん mailto:sage [2008/07/05(土) 14:48:09 ] その並べ替えるコストを問題にしてるんだが。 421 名前：414 mailto:sage [2008/07/06(日) 00:40:59 ] >>418 そうです、任意の値を境にして二つのred-black-treeに分割したい、という意味です。 >>419 なるべくo(logn)の係数を抑えてやりたいのです。。。 >>420 そうなんです＞＜ いろいろ考えてみてはいるんですが。。。どうしてもバランスがとれなくて 困っています。 422 名前：415 mailto:sage [2008/07/06(日) 01:32:25 ] 平衡2分木は1 2 4 8 16・・と、2のべき乗でノードが増加するのが 判ってるから、分割した要素の総数から大雑把に見積もった 空のツリーを作成しておいて、データの穴埋めをしていけば 線形時間で済むでしょ。 例えば1から10までの要素で平衡木を作るなら1+2+4+8の 15に収まる4階層の平衡木が確定する。 あとは右端からトラバースして埋めていくだけ。 　　　　　　　　7 　　　 4　　　　　　　 9 　2　　　　6　　　　8　　　10 1　 3　　5 423 名前：デフォルトの名無しさん mailto:sage [2008/07/06(日) 07:16:54 ] なんでわざわざ分割操作を赤黒木でやろうとしてるの？ 探索木で分割自体が O(log n) でいくようなものもたくさんあるでしょや。 424 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 23:28:29 ] >>421 平衡木を適当にぶった切ったら、もうそれは平衡木ではない。 バランス取れなくて当前。 比較は必要ないが、結局双方の木でdeleteやinsert相当の 回転操作をやる必要がある。 425 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 14:46:34 ] ドラえもんがポケットから目的の物を見つける時、どんな探索アルゴリズムを使ってるんだろう。 426 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 18:47:51 ] O(1)が基本だろうが語彙が特定しない場合は自己組織化探索も入ってるな 427 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 19:08:03 ] 確かのび太がスペアポケットで、しらみつぶしに探してた気はするｗ 428 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 19:29:59 ] ソートキーは名前以外の可能性が高いな 価格か商品番号か購入順か オレは購入順を推しておこう 429 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 20:01:37 ] 緊急時に限っていらないものが出てくるから購入順ではなさそうだが。 物の名前の一部などであいまい検索で引っかかったのを片っ端から探るとか。 あわててるとクエリの生成が適当になる。 430 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 00:09:11 ] コミックスを見比べたわけじゃないが 緊急時に出る道具ってある程度固定されてる気がする。 夢確かめ機みたいなろくでもないのは毎回出てくるだろ？ ポケットの中身はおそらく、ろくでもない順（＝Fに愛されてる順）にソートされてる。 431 名前：425 mailto:sage [2008/07/25(金) 04:18:33 ] おまえらバカじゃねえの 432 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 09:26:30 ] 425さんの賢いところを見せてください 433 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 10:33:52 ] >>429 たしかドラポケットは「思ったものが出てくる」仕組みなので、慌ててる ときにいらんもんが出てくるのは、そもそもの探索キー(思考)がgdgdなん だと思われ。 434 名前：425 mailto:sage [2008/07/25(金) 13:31:18 ] >>431 お前誰だよｗ 435 名前：424 mailto:sage [2008/07/25(金) 15:24:52 ] >>434 オレオレ、オレだよ 436 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 15:41:23 ] 名無しだよ 437 名前：デフォルトの名無しさん [2008/08/08(金) 02:49:00 ] チャットプログラムを考え中なのですけど、軽く自信がないところがあるので質問させてください。 ブラウザで前回の更新時以降に追加されたログのみを受け取り、 ログ出力に反映させる。という部分を作っているのですが、 サーバのデータを受信する時の形式をどんなふうにしようか少し悩んでいます。 今のところは (受信成功確認用の文字)<>時間<>発言者<>発言<>文字色 ・・・・以降受信が必要な分だけ時間から文字色のデータをループで渡す。 のようなことを考えているのですが、 何となくデータに若干の抜けがあったら結果が変なことになりそうな気がしてるのですが、 問題は無いでしょうか？ 438 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 05:37:58 ] go webprog 439 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 07:50:26 ] アルゴリズムではないな。 440 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 08:53:59 ] <> と発言したらどうなるか見てみたい 441 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 17:59:54 ] &lt;&gt; 442 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 08:06:54 ] >>441 やりはじめはその手の処理忘れるよな 443 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 05:02:14 ] うまい方法が思いつかないので知恵を分けてください。 一定の半径を持つ円の中に点(座標)をランダムに打ちたい。 条件は、中心から一定距離までは打たない、円周になるほど高頻度で打ちたい 使える物は、精度(分解能)のよくないSin(Cos)テーブル 高級ではない言語と低レベルな頭脳なので、できれば数学系ライブラリとかを使わずに 計算や乱数などで済ませたいです。 具体例ではなく考え方でも構いません。 444 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 06:28:21 ] >>443 こんな感じ？ www.dotup.org/uploda/www.dotup.org0569.png 445 名前：443 mailto:sage [2008/08/29(金) 07:05:54 ] >>444 まさに理想形です。 可能な範囲で助言をいただけると嬉しいです。 今更かもしれませんが、補足 中心から方向Xに距離Rで配置すると中心の密度が上がってしまうので困ってます。 446 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 07:29:24 ] >>445 方向X、円周からの距離Rの片側正規分布で一定以上は切ればいい希ガス。 447 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 08:51:36 ] 偏角は一様分布で出して、 中心からの距離を、 一様分布に対して 1/r かけたもので作れば r に比例した分布になる。 1/r^2 とかかけとけば 442 みたいな分布になると思う。 448 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 10:02:34 ] >>443 x=乱数; y=乱数; if(x*x+y*y<r*r) 点を打つ; 449 名前：443 mailto:sage [2008/08/29(金) 11:38:57 ] みなさんありがとうございます。 乱数は一様乱数しか知らなかったので、正規乱数を使う事で解決しました。 ありがとうございました。 450 名前：デフォルトの名無しさん mailto:sage [2008/08/30(土) 07:10:18 ] piece tableのサンプルコード等ありませんでしょうか 451 名前：デフォルトの名無しさん [2008/09/02(火) 14:25:43 ] データベース等に詳しい方教えてください。 B+木を実装する際に、ページに複数のエントリを入れる場合、 ページにできるだけたくさんエントリを入れようとすると、 空間効率は上がるが、木がバランスされなくなると思うのですが、 実際はどのような実装するのが普通なのでしょうか？ ページに入れるエントリ数を固定するのでしょうか？ （その場合は、エントリのサイズが小さい場合は、空間効率が悪くなるし、 大きい場合は、１ページに入らないといった問題がおきて、 実装がややこしくなりそうと思っています。） 452 名前：デフォルトの名無しさん [2008/09/02(火) 14:32:31 ] 451です。 一般的には、 次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる ということは理解していますが、 エントリのサイズが可変の場合は、最大2d個のエントリをどう格納するのかが よくわかっていません。 * ページサイズを可変にする * ページサイズは固定で、入りきらない場合は複数のページを使う この辺があると思っています。 453 名前：デフォルトの名無しさん mailto:sage [2008/09/03(水) 20:16:03 ] ページに入るエントリ数は固定。 バランスされなくなるって、ノードの兄弟を見ながら 2dに収まるように分割してくんだよ。 ほとんど理解できてないみたいだから より単純なB木から学んだ方がいい。 454 名前：デフォルトの名無しさん [2008/09/16(火) 18:38:15 ] ４つの都市A、B、C、Dのそれぞれの距離がわかっている状態で、 xy平面上に正しくA、B、C、Dを配置したいのですが考え方がわかりません。 アドバイスをいただけないでしょうか？ 455 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 19:12:08 ] 回転どうすんだ 456 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 21:57:19 ] >>454 三角関数 457 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 22:07:09 ] >>454 回転が確定しなくていいなら、相対測位とかいうキーワードでぐぐれ。 458 名前：454 [2008/09/17(水) 16:07:09 ] 455様、456様、457様返信ありがとうございます。 余弦定理を用いて半径ACと半径BCの円の交点を考えC点を導いたのですが 次のD点を考えるときに半径AD・BD・CDの円が（当たり前かもしれませんが）１点で交わらないので求められませんでした。 455様と457様が言っている「回転」が必要だなと思い、 B点をA点のまわりで距離ABを保ちつつグルグル回るようにしたのですが、どうも違うみたいで困ってしまいました。 回転についての詳しい説明を教えていただけないでしょうか？ 今は下のような状態になっています。 ttp://www.dotup.org/uploda/www.dotup.org0494.png 赤・青の円は半径AC・BCの円でC点（黄緑）を求めました。 薄い赤・青・緑の円は半径AD・BD・CDの円でとりあえず円AD・BDの交点から仮のD（紫)を導いたところです。 よろしくお願いします。 459 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 17:00:27 ] ４点が平面上にないだけじゃないの？ 分かりやすい座標で１回やってみた方がよさげ。 460 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 22:38:41 ] 3点の位置が決まって距離もわかってて4点目が交わらないってあるのかな？ 各点間の距離データはあってるんだよね？？ 461 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 00:59:48 ] 現実の都市間の距離だったりして・・・ とはいえその場合でも、対称を同一視すれば一意に求まるはず。 462 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 02:23:10 ] >>459,461 そ れ だ。 現実の都市間の距離で、球面上には矛盾無く配置できるけど平面上では矛盾無く配置できないとかな。 とりあえず454はそれぞれの距離を提示するべき。 463 名前：454 [2008/09/18(木) 14:11:16 ] 459様、460様、461様、462様返信ありがとうございます。 まず都市ABCDが現実に存在する都市かどうかですが、この世に存在しない都市を仮定しています。 そのため距離は毎回乱数で定まっています。 最初に断わっておくべきでした申し訳ないです。 4点が同一平面上にない場合があることは考えていませんでした。 今回の考え方を元に、単語同士の非関連度を距離に置き換えてそれぞれを配置するプログラムを作ろうかと思っていたのですが、 平面上のみで考えるのは無理があるのでしょうか。 464 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 14:40:44 ] 4点をa,b,c,d、それらの間の距離6つをab,ac,ad,bc,bd,cdと書くことにする。 距離を何の制約も無しに乱数で作ると、それは4点間の距離と言えないものもできてしまう。 a,b,cで三角形になるのだから、ab+bc>acなどの制約が必要。 a,b,c、a,b,d、a,c,d、b,c,dの各組が三角形になる制約を満たすなら、 4つの点a,b,c,dは4面体を作る。 465 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 17:25:13 ] 何点あっても、二点間の間での距離だけを定義すればうまくいくんじゃね？ 完全ランダムでは無理条件ができるけど 466 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 20:06:30 ] >>465 > 二点間の間での距離だけを定義する という意味がわからないけれど， 『任意の二点間で三角不等式が成立するならば実現可能」 という主張なら，4点で反例が構成できる： d(12) = 1, d(13) = √5, d(14) = √2, d(23) = 2, d(24) = 1, d(34) = 1 467 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 20:25:51 ] これは非常に有名な問題（グラフ実現可能問題）． 以下の事実が知られている． 定義： n×n 行列 D = (d_ij) が EDM であるとは， ある点 p_1, ..., p_n ∈ R^k が存在して， d_ij = |p_i - p_j|^2 が成立することをいう． k を D の埋め込み次元という． I を単位行列，J をすべての成分が 1 の行列とする． 定理(Schoenberg, Young-Householder)： 対称かつ対角成分がゼロの非負行列 D が EDM であることと， G := -V D V / 2 が半正定値であることが同値． ただし V = I - J/n である． また，G = X X^T を コレスキー分解としたとき， X の列ベクトルは D の実現となる． なので，与えられたデータから行列 D を構成して G を計算してコレスキー分解すれば埋め込みが決定できる． もし rank G > 2 だったら平面には埋め込めない． 詳しくはEuclidean Distance Matrixなどで検索してくれ． 468 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 00:48:36 ] 質問させて頂きます。 XY平面上に、その座標データを保持するオブジェクトが複数個あり、 それらの座標はそれぞれランダムだったとします。 それぞれのオブジェクト間の距離が一定以下の場合は、 一定距離の間隔を置けるように引き離し、 さらにオブジェクトの距離の一番近いオブジェクトを探す というようなことをしたいのです。 この処理はリアルタイムループ内で実行するので、 引き離しは1距離だけ離れるだけで十分であるとします。 一応は下記のようなプログラムで実装は出来ているのですが、 オブジェクトの数が増えた場合に処理が急激に重くなります。 この処理の計算量がn^2であるので、 オブジェクトの数が100、200と増えていった場合には とてもリアルタイムループでは遅すぎる速度になってしまうのです。 何とかしてこの計算量を減らす方法はないものでしょうか？ 469 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 00:50:56 ] >>468 簡略 #define n 200 struct Object { 　　double x, y; 　　int near; } op[n]; double dx, dy, dr, drmin; for(int i = 0; i < n; i++) { 　　drmin = 1000000; //とりあえず大きい数 　　for(int j = 0; j < n; j++) { 　　　　dx = op[i].x - op[j].x; 　　　　dy = op[i].y - op[j].y; 　　　　dr = sqrt(dx * dx + dy * dy); 　　　　//一番近いオブジェクトを探す 　　　　if (dr <= drmin) { 　　　　　　 op[i].near = j; 　　　　　　 drmin = dr; 　　　　} 　　　　//一定距離以内の場合は引き離す 　　　　if (dr <= 400) { 　　　　　　op[i].x += dx / dr; 　　　　　　op[i].y += dy / dr; 　　　　　　op[j].x -= dx / dr; 　　　　　　op[j].y -= dy / dr; 　　　　} 　　} } 470 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 01:27:09 ] >>468 動的ボロノイ図を使えば，一反復が O(n + k log n) でできる． ただし k は引き離す必要のあるペアの数． ただ，これは実装が結構しんどいので，現実的には x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て 枝刈りするのが有力だと思う （x 座標が一定距離を超えたら，距離が一定距離以下にはならない等） 計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず． なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると 多少の効率化ができる． 471 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 19:43:55 ] >>470 動的ボロノイ図は調べてみましたがサッパリ理解できませんでした（汗 なので後者のソートして近いところから探す方法を試してみたところ、 オブジェクト800個くらいまでは実用レベルの速度で動くようになりました。 但しやはり位置関係によっては重くなることもあり、 必ずしも安定しているとは言えませんが、 総当りに比べれば桁違いの速度になりました。 ありがとうございました。 472 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 23:01:01 ] 「一定距離」の間隔でマス目に区切って、マス目毎にデータをコレクションで持ち、 引き離し処理をするときには、データとその周囲の9マス分の範囲だけ調べるとか。 □□□□□ □■■■□ □■▲■□ ←▲のところが自分の属すマス □■■■□ □□□□□ データの散らばってる範囲が狭過ぎると密集して役に立たないし、 逆に広過ぎるとマス目の管理を工夫する必要があるけど。 あと、「一定距離」以上でも最も近い点を取得する必要があるなら、これじゃだめかも。 473 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 23:06:33 ] ヒューリスティックだけど、自己組織化で適当に動かしてみるとか。 474 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 11:26:32 ] すまん、図形描画アプリみたいなものを作ってるんだが･･･ 次のようなもので悩んでます。 １．複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか? 場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。 総当たり以外でエレガントな方法というとどんなんざんしょ? ２．同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。 教えてエロイ人･･･ 475 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 12:15:00 ] メモリが許せば、思い切って座標にオブジェクトを持たせるとか。 476 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 12:15:42 ] >>475は>>468にです。 477 名前：468 mailto:sage [2008/09/20(土) 18:05:06 ] お返事ありがとうございます。 >>472 空間分割とかいうやつですかね？ しかしこれは「最も近い点を取得する」という場合に やはりお察しのように問題がありまして、 結局こちらの方法は諦めたのであります。 一応この最も近い点を探す距離も制限されてはいるのですが、 結構範囲が広いのでその表現は省かせていただきました。 >>475 これはその空間分割の究極ですね・・・ しかしこれはまた違う方向で膨大な判定量になりそうな気がします。 478 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 19:00:54 ] >>477 472の亜種だと思うけどＸ，Ｙ軸上でソートして、各軸上の分布をクラスタとして扱うっていうのがGameProgrammingGEMに載っていた。 479 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 21:40:57 ] >>474 問題が明確じゃないのだけれど， (1) 『描画する』条件は，単に『別の矩形に包含されないこと』でよい？ それとも，矩形間に上下関係（例: Windowsのウインドウ）がある？ (2) 『描画する』条件は (1) と共通ということでよい？ それと，曲線はどのような形で与えられる？（例：ベジエ曲線） 何にせよ平面走査型のアルゴリズムが有力に動くと思う． 480 名前：デフォルトの名無しさん mailto:sage [2008/09/21(日) 11:23:34 ] ナップサック問題とは、価値と重量があるものを、入れられる重量に制限がある箱に 一番価値が高くなるように効率よくいれるにはどういれたらよいかの手順を考える問 題ですよね。 これに、価値が高くなることに加えて、入れる順番も重さがあるものから入れる、あるいは 軽い順に入れるなどの制限が加わった場合にどのようにすればよいかという解法は 存在しますか？ 481 名前：デフォルトの名無しさん mailto:sage [2008/09/21(日) 11:59:36 ] >>480 入れるものを決めた後で重量でソートすればいい 482 名前：474 mailto:sage [2008/09/21(日) 12:35:56 ] >>479 不明確ですいません･･･orz 1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。 ２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。 平面走査型ちょっくらぐぐってきます。 483 名前：デフォルトの名無しさん mailto:sage [2008/09/22(月) 00:32:18 ] >>481 書くべき事がたりませんでした。。。 では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？ 484 名前：デフォルトの名無しさん mailto:sage [2008/09/22(月) 02:43:01 ] DP使うしかないんじゃない？ 485 名前：デフォルトの名無しさん mailto:sage [2008/09/23(火) 09:49:23 ] >>480 状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ． 重さが自然数であれば，品数を n，重さの最大値を W としたとき 普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば O(n^2 W) のアルゴリズムが簡単に作れる． 重さが実数であれば，基本的には枝刈り探索しかないのだから， 上の三つ組みを持って適当に探索する． 本気を出すなら，品数や重さなどによって適切な探索法が変わるけど そこまでがんばるかい？ 486 名前：デフォルトの名無しさん mailto:sage [2008/09/23(火) 11:07:05 ] >>482 もうググって見つけたかもしれないけれど， 1 に関しては平面走査型アルゴリズム（plane sweeping）が考えられる： ・y 軸に平行な直線を考える（走査線と呼ぶ） ・走査線を x = -∞ → +∞ に移動させていく． ・走査線に新たな矩形が乗ったら走査線上の矩形とだけ描画判定を行う． 走査線は y 座標でソートされた二分探索木を用いると， 描画判定を行うべき矩形を O(log n + k) 程度で列挙できる． 二分探索木を管理するのが面倒ならリストで持ってもよいが， これだと列挙に O(n) かかる． （矩形がそれなりに散らばっていれば，現実的には相当改善する） こういうのは「線分交差列挙」などで調べると参考になると思う． ちなみに矩形が動的に増えたり減ったりするような状況設定なら， 空間分割木などの幾何データ構造を使うことになる． 2 に関しては，描画の段階でなくて，データの段階でどうなるかが問題． もしデータの段階で「連続した線分の集まり」と思ってよいなら， 1 の平面操作型アルゴリズムに走査線に線分が交わったら云々を追加するだけ． それがダメなら，扱う曲線のデータ構造が分からないと，どうしようもない． たとえば『曲線の方程式 (x(t), y(t)) が与えられる』くらいだと， 曲線と矩形の交差を全チェックするしかない． 487 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 01:27:20 ] ポリオミノ自動生成アルゴリズムって、起点を中心にどんどん成長させていって、 それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。 488 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 19:54:18 ] 自動生成って何？ 指定したサイズのもの全てとか、小さい順とかで列挙すること？ それとも、条件を満たすもののサンプリング？ 489 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 21:02:22 ] nの数を与えて、その全パターンを出すアルゴリズムです。 n=7なら、108通り全部とか。 490 名前：デフォルトの名無しさん [2008/10/19(日) 01:32:31 ] あげ 491 名前：デフォルトの名無しさん [2009/01/18(日) 20:54:29 ] age 492 名前：デフォルトの名無しさん [2009/01/19(月) 19:28:43 ] 良スレの予感 493 名前：デフォルトの名無しさん [2009/01/19(月) 23:10:09 ] DBMについて興味があり、最近書籍やウェブなどをあたっていました。 B-Treeなどのアルゴリズムについてなんとなく理解したのですが、 それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。 C言語で実装されているソースの解説などどこかにあるでしょうか。 もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、 ちょっと敷居が高いです。 494 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 01:02:00 ] いきなりF1に乗ろうとする奴っているよね。 495 名前：デフォルトの名無しさん mailto:sage [2009/03/03(火) 06:57:31 ] >>493 >それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。 互換性が要らないならバイナリでダンプしてもいいし、サイズを優先してバイナリで writeしてもいい。互換性を重視するならテキストでwriteするといい。 速度を優先するならseekしたほうがいい。言語によってはシリアライズ機構がある。 よく分かっただろう？ 496 名前：デフォルトの名無しさん mailto:sage [2009/03/03(火) 08:09:55 ] >>493 自分で実装したC#のソースなら持ってるけど 497 名前：デフォルトの名無しさん mailto:sage [2009/03/04(水) 18:34:35 ] そのseekってなんのこと？ 498 名前：デフォルトの名無しさん mailto:sage [2009/03/05(木) 06:32:12 ] 速いライブラリを自分で探せってこった。 499 名前：デフォルトの名無しさん [2009/03/20(金) 20:01:14 ] 499 500 名前：デフォルトの名無しさん mailto:sage [2009/03/20(金) 20:56:21 ] 500 501 名前：デフォルトの名無しさん mailto:sage [2009/03/20(金) 21:16:26 ] >>493 ISAM 502 名前：デフォルトの名無しさん [2009/03/20(金) 23:09:41 ] page4.auctions.yahoo.co.jp/jp/auction/d91264064 503 名前：デフォルトの名無しさん mailto:sage [2009/04/01(水) 00:32:52 ] 多角形の頂点の座標が配列で与えられている時に その図形の重心を求めるアルゴリズムを教えてください。 頂点の数は３以上。 全ての辺について、他の辺と交差することは無い。 一つの角の大きさは0〜360度。

---

---

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

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