幅優先探索で迷路の最短経路を探す
幅優先探索で迷路の最短経路を探す 2010-01-14-4 [Algorithm][Programming] 迷路の最短経路を探すプログラムを作成するという問題について。 - 人材獲得作戦・４ 試験問題ほか (人生を書き換える者すらいた。) http://okajima.air-nifty.com/b/2010/01/post-abc6.html これは単なる幅優先でOKですね。 足跡を記録していき、すでに別の子が通った道にぶつかるか（足跡の有無で判定）、行き止まりに到達したら枝狩り。 幅優先なんだからこれで見つかるのが最短経路。 後からの「最短性のチェック」は不要です。 「アルゴリズム知らないとできない」とか以前の問題で、正式にプログラミングの基礎を学んだ人ならできて当たり前の問題です。ピンと来ない人は、ポインタわからない、再帰わからない人と同列かなあ。 バリバリプログラミングからは一線
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
Alcor の Abbreviation Scoring - steps to phantasien(2009-09-12)
同僚の生産性ツール愛好家が熱に浮かされて言った. "QuickSilver の検索がすごいんだよ!" どう凄いのかというと, たとえば "Skype を検索するのに <sp> でいい!" らしい. それは凄いのかも. 私もいちおう QuickSilver を使っているけれど, 素敵機能の類はまったく活用していない. だいたい私の使うアプリケーションはどれも一文字で特定できる. Firefox, Emacs, iTerm, Activity Monitor... そういえば iTunes は iTerm と被ってる. ためしに <iu> と打ってみたら iTunes にマッチする. なんとなく凄い気がしてきた. 同僚はこのアルゴリズムが気になるらしい. 編集距離の仲間かとも思ったけれど, 違う気がする. とりあえずぐぐってみたところ, QuickSilver は 2007 年に オープンソー
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
人工無能の作り方
書いた人 INA 人工無能とは？ 人間っぽく話すプログラムのこと。会話を理解しているというよりは、なんかそれっぽいことを話すだけのものが多い。 今回は「日本語のようなものを話す人工無能」を作ってみたので、その簡単な仕組みと工夫した点について少し書いてみることにする。 動機 うちのサークルのメンバーがよく集まってるチャット。とてもマニアックな どうしようもない 会話が繰り広げられているわけだが、ちょっと物足りない。 そうだ！ 萌キャラがいないじゃないか！ 「ないなら作ればいいじゃない？」 材料 MeCab 形態素解析エンジン 難しいことは知らなくても問題ない。 「私は変な人ではない」 ↓ 私 名詞,代名詞,一般,*,*,*,私,ワタシ,ワタシ は 助詞,係助詞,*,*,*,*,は,ハ,ワ 変 名詞,形容動詞語幹,*,*,*,*,変,ヘン,ヘン な 助動詞,*,*,*,特殊・ダ,体言接続,だ,
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
アルゴリズムを知るとプログラムが豊かに書ける | こえむの編集後記
アルゴリズムを学ぶと、プログラムの幅が広がるよ！それも言語に囚われずに。というお話。 最近作った『シムエントリ』。 自然言語処理(テキストマイニング)の知識を学んだことで、初めて開発できたサービスです。 しかし、ほんの1ヶ月前まではこれらの知識なぞさっぱりありませんでした。たまたま、現在スポットで勤めている某研究所でプログラムの助手をしていたのがきっかけで、学ぶ機会に恵まれました。 さて、日々プログラムに触れられている皆様、アルゴリズムに純粋に触れる機会はどの程度でしょうか？ 現在よく使われている高級言語(Java, Perl, Python, etc…)には様々なライブラリが揃えられていて、そのライブラリが動くアルゴリズムを知らなくても、存在を覚えさえすればプログラムが書けてしまいます。例としては、配列のソートや、ハッシュテーブルなどでしょうか。 そして、巷でよく見かけるプログラム技術は
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
Mostly-Concurrent Mark & Sweep GC のアルゴリズム
目次 1. 前置き 2. HotSpot VM 1.4.x の GC の種類 3. Mostly-concurrent Mark & Sweep 4. 応用 4.1 世代別 GC との組み合わせ 4.2 カードマーキング (Card Marking) 4.3 並列化 (Parallel GC) 4.4 ビットワイズ・スイープ (Bitwise Sweep) 4.5 インクリメンタル・コンパクション (Incremental Compaction) 5. 参考文献 脚注 コメント 1. 背景 ガーベージコレクション(GC) には色々なアルゴリズムが存在するが、大雑把に言って Stop-the-World (STW) 型 GC と On-the-fly 型 GC に大別される。 STW 型の GC はプログラムの実行中にはガーベージの回収を行わず、メモリが枯渇した時になって始めてガーベージの回
[を] Blowfish アルゴリズム
Blowfish アルゴリズム 2006-06-02-3 [Algorithm] Blowfish はブルース・シュナイアー（Bruce Schneier）による暗号化 アルゴリズム。特許は取ってないとのことで、自由に使えて安心。 Dr. Dobb's Journal での解説(1995)が分かりやすいです。 http://www.schneier.com/paper-blowfish-oneyear.html P-array と S-boxes の初期化に使っているのは、円周率を16進数で あらわしたもの。 解説では "the hexadecimal digits of pi(less the initial 3)" と 説明があります。 下記URLに16進表記がありました。 http://www.super-computing.org/pi-hexa_current
これだけは知っておきたいアルゴリズム〜共通鍵暗号編 ― ＠IT
実際に運用中の情報システムで利用されている暗号アルゴリズムを移行することは、大規模なシステムであるほど、大変な労力とコストが必要となる。従って、規模が大きく、また長期運用が前提となっているシステムほど、暗号の選定には慎重になるべきである。 その意味で、「システム性能要求上問題がない範囲内であれば、現時点における最も高い安全性が確認されている暗号の中から選択するのが望ましい」というところに、暗号技術の2010年問題【注】の本質がある。いい換えれば、現在のデファクトスタンダードだからとの理由だけでその暗号を採用することは必ずしも勧められない。 【注：暗号技術の2010年問題とは】 米国は、現在利用されているすべての米国政府標準の暗号技術を2010年までにより安全な暗号技術へ交代させていく方針を明確に打ち出している。現在、世界中で使われているデファクトスタンダードの暗号技術は、そのほとんどすべて
これだけは知っておきたいアルゴリズム〜ハッシュ関数・公開鍵暗号・デジタル署名編 ― ＠IT
これだけは知っておきたいアルゴリズム ～ハッシュ関数・公開鍵暗号・デジタル署名編：デファクトスタンダード暗号技術の大移行（4）（1/3 ページ） 前回の共通鍵暗号の紹介に引き続き、安全性・処理性能ともに優れていると国際的に認められ、米国政府標準暗号、欧州のNESSIEや日本のCRYPTREC（Cryptography Research ＆ Evaluation Committees）での推奨暗号、ISO/IEC国際標準暗号、インターネット標準暗号などで共通して選定されているハッシュ関数・公開鍵暗号・デジタル署名について紹介する。 共通鍵暗号ではアルゴリズムそのものを代替わりさせることによって、より安全でより高速なものへと移行することが可能である。これに対して、ハッシュ関数、公開鍵暗号、デジタル署名ともに、アルゴリズムそのものを代替わりさせるというよりも、基本的にはほぼ同じ構成のままハッシュ
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
hnwの日記 - PHPの奇妙なround関数
(2012/11/01追記) 4年ほど前の記事「PHP5.3.0alpha3のround関数の実装がPHP5.2.6と変わった - hnwの日記」でお伝えした通り、PHP 5.3.0から別の実装が採用されており、本ページで指摘しているような挙動のPHPは既に絶滅危惧種です。念のため。 さて、プログラミングの話題もたまには書いてみます。今回はPHPのround関数の挙動が変だ！という話題です。 round()は浮動小数点数を四捨五入する関数で、大抵の言語に同じ名前で実装されているかと思います。ではPHPのround関数の何が問題なのか、ちょっと試してみましょう。 $ uname -sro Linux 2.6.9-42.0.10.plus.c4smp GNU/Linux $ php --version PHP 5.1.6 (cli) (built: Feb 23 2007 06:56:38)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://yimado.s-lines.net/algo_and_ds/