計算幾何学セミナー 第3回 5章 直交領域探索 データベースの検索
2004 / 05/ 11 計算幾何学セミナー 第３回 ５章 直交領域探索 データベースの検索 Orthogonal Range Searching 岡野原 大輔 Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld, Mark Overmars Springer-Verlag, 2nd rev. ed. 2000 直交領域探索とは 軸並行なd次元のボックス内部にある点を 全て求めるという問題 d個のフィールドを持つデータベースのレコー ドはd次元中の点として表現され、問い合わせ は直交領域探索に変換可能である。 XMLなどのtree構造に対する操作も、直行領 域探索に変換される Treeの直行領域 への変換 Treeも、範囲の
K-meansアルゴリズムの導出 - nokunoの日記
引き続き東大の「創造情報学連携講義VII」より栗原さんの課題2を解きました。創造情報学連携講座 問題個のデータをk個のクラスタにクラスタリングしたい。このとき番目のクラスタの中心をとして、minimize: となるような各データからクラスタへの割り当てとクラスタ中心を求めるためのアルゴリズムとして以下のk-meansクラスタリングが導出できることを示せ。 クラスタ中心をランダムに初期化する 収束するまで以下を繰り返す ステップ1：それぞれのデータ点に最も中心が近いクラスタを割り当てる ステップ2：それぞれのクラスタの中心をクラスタ内のデータ点の平均によって計算する 回答 ステップ1ステップ1では、 を固定して を更新する。minimize: for all これの最小化は全てのに対し、データ点に最も中心が近いクラスタを割り当てることで達成される。minimize: for all iよって
今すぐフォローすべき競技プログラミング界のスーパーエンジニア - chokudaiのブログ
今すぐフォローすべきnode.js界のスーパーエンジニアの便乗です。 競技プログラミングは、最近ようやく書籍化されたものの、やはり殆どの知識はインターネットに頼ることとなります。解けない問題を独力で解決するのは非常に難しく、特にリアルタイムのコンテストなどに出場される際には、こうした人々をフォローし、考え方・解法を徐々に身に着けていくことで、様々な問題を解決できるようになるでしょう。 筆者の主な活動場所がTopCoderなので、TopCoderの人がメインになっちゃうかと思われます。あと無断で紹介してるので、マズかったら教えてください。 紹介前の補足 実績を書く際に、TopCoderのRatingを引用するので、TopCoderのレーティング分布を紹介しておきます。 この分布における、Rating 2200以上の赤い人が、RedCoderと呼ばれる人達です。 Algorithm部門において
単語と文字の話 - Preferred Networks Research & Development
4月からPFIで働いてます。海野です。 今日は単語の話をします。読み物的な話なので軽く読んでください。 テキストデータなどの自然文を機械処理するときには、まず最初に単語に分割するということをよく行います。一般的にはMeCabやChasenといった形態素解析エンジンに投げて行います。形態素と単語の区別という話もあるのですが、ここでは大雑把に「連続した文字列の単位」くらいの意味で話します。 検索という文脈ですと形態素インデックスという言葉がありますが、これは検索の最小単位を文字単位ではなくて形態素の単位にするということです。例えば「東京都」は「東京」「都」に分かれるため、「京都」というクエリに対して見つかるのを防ぐなど、精度を上げる効果があります。反面、深刻な検索漏れを引き起こす可能性があるため嫌われることが多いです。こうした漏れは検索に限らず、テキストマイニングなどの文脈でも問題となることが
JavaScriptの乱数の精度の話 / LiosK-free Blog
2010-06-03 カテゴリ: Client Side タグ: JavaScript Tips アルゴリズム 前回の記事で予告したとおり、今回はJavaScriptのMath.random()で生成できる乱数の精度の話。 前回の記事で、JavaScriptでは2^53未満の正整数を扱うことができるということがわかったから、今回の記事では2^53未満のランダムな正整数を生成してみる。 具体的には↓のようなコード。 var ub = Math.pow(2, 53), list = []; for (var i = 0; i < 16; i++) { list[i] = Math.floor(Math.random() * ub).toString(2); while (list[i].length < 53) { list[i] = "0" + list[i]; } // padding }
指数関数を使ったお手軽イーズ・アウト
（この記事にはProcessing.jsによるスケッチがいくつか組み込まれています。環境によっては正しく再生されないかもしれません。Chrome, Safari, Firefox等の使用をおすすめします。） 「丸が１秒おきに左右に滑らか動く」というプログラムを書いてみよう。いちばん簡単なのは、線形移動を使う方法だ。 まあ、これでも十分っちゃ十分なんだけれど、動きとしてはちょっと味気ない。 いわゆるイーズアウト(ease out)を使えば、これを滑らかにすることができる。 上のスケッチでは、漸化式を使ったイーズアウトを実装している。こんな感じの式だ。 pos += (target - pos) * 0.1; pos は現在座標、 target は目標の座標。この式を1回の描画毎に評価する。目標座標までの差分を1割づつ詰めていくような感じ。差分は毎回少なくなっていくから、最初は早く、徐々に遅く
Super Technique 講座〜再帰関数の技
Ｃ言語初心者が戸惑うものとして、「再帰」に関する技法がある。まあ、今時の言語で「再帰関数」を書けないのは、COBOL と FORTRAN, 古典的BASIC くらいのものだが、一般的な言語解説書での説明は大変おざなりなものである。だから、これは意識して憶えないことには、やはり身に着かない。 そこで「Super Technique 講座」では、再帰の技法を、再帰という発想の親玉である Lisp(Scheme) を利用して理解する、という無謀な企てをしてみることにする。「ある言語を理解するのに、何で別な言語を勉強するの？」という当然の疑問が湧くことだろう。しかし、しかし、「それがハッカーというものである」。筆者は MS-DOS の時代に、UNIXのテキストツールの使い方を理解するために、それらを自分で実装した。一見「無駄」に見える技術投資は、ことプログラマにとっては決して「無駄」ではない。Li
ALGORITHM NOTE こだわり
入力例 3 9 500 300 800 200 100 600 900 700 400 4 3 1000 1000 1000 0 0 出力例 1800 1000 解説 Partition Problem といいます。 [この問題では、本の厚さの制限が緩いので、力任せ(本棚の幅を少しづづ厚くしていき貪欲に解く)で解けたのかもしれませんが、点数から察して、悲しいことに設定ミスか、または意図的に難易度を下げたか、または実行時間の制限を厳しくしているのでしょうか。力任せで解けないのであれば難易度はさらに高くなります。] 出題者が求めた解法は、動的計画法または二分法だと思います。 ここでは、動的計画法でこの Partition Problem を解きます。 Partition Problem とは、n 個の数からなる数列 S = {s1, ..... sn} を k 個の部分に分割するときに、各部分
A*アルゴリズムについて整理 - yasuhisa's blog
辞書を参考にしながら。NAISTのI期辺りでやったはずなんだが、かなりすっ飛んでいる。 デジタル人工知能学事典 [CD-ROM付] 作者: 人工知能学会出版社/メーカー: 共立出版発売日: 2008/05/16メディア: 単行本購入: 1人 クリック: 6回この商品を含むブログ (6件) を見る A*アルゴリズムとは?グラフ探索アルゴリズムの一つ。「開始ノードから現在位置に至るまでのコスト」と「現在位置からゴールまでの推定コスト」の2つのコストを用いてadmissibleな条件(後述)の元でコストが最小であるような経路を効率的に見つけることができるアルゴリズムである。1960年代に開発されたアルゴリズムであるが、50年経った今でもばしばし使われている。 現在いるノードをp、開始ノードからpまでの最小コストをg(p)、pからゴールまでの最小コストをh(p)と書くとすればpを経由して開始ノード
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
ソートアルゴリズムを映像化してみた - jsdo.it - Share JavaScript, HTML5 and CSS
よくあるやつです。ぼんやり眺めてると、とても癒されます。 2014/2/25 追記: 全面的に書き直しました。 // https://github.com/norahiko/sort-visualize var helper = { range: function(min, max) { var res = []; for(var i = min; i < max; i++) { res.push(i); } return res; }, shuffle: function(ary) { for(var i = ary.length - 1; 0 <= i; i--) { var rnd = Math.random() * (i + 1) | 0; helper.swap(ary, i, rnd); } }, swap: function(ary, a, b) { if(a < 0 ||
探索 - Wikipedia
探索（たんさく、英: search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。 何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。 一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（英: search）も参照。 探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。 まず解くべき問題を状態（英: state）と状態変化（行動、英: action）に分ける。 最初に与えられる状態を初期状態（英: initial state）といい、目的とする状態は最終状態（ゴール、英: final state, goal）と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並び
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Frequency analysis - Wikipedia
dfltweb1.onamae.com – このドメインはお名前.comで取得されています。
画像処理 第1回 補間
Home - Make: DIY Projects and Ideas for Makers
プログラミングコンテストでのデータ構造
JOI合宿 問題と解説
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development
How to Implement World Fastest Grep.