経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
DO++ : 部分文字列の話
ここしばらく、部分文字列の統計量を利用した機械学習やデータマイニングをやっている。そこの話からちょっと抜粋。 長さnの文字列T[1,...,n]が与えられた時、T中に出現する部分文字列T[i...j] (1≦i≦j≦n）の数はn個の中からiとjの2箇所を選ぶのでO(n^2)個ある。例えば、n=10^6(1MB)だったら、部分文字列の数は約10^12個(1T)と非常に大きい。 しかし、これらの部分文字列の出現位置は同じである場合が多い。例えばT="abracadabra"であれば、"abra"と"abr"の出現場所は1番目と8番目であり、全く同じである。 では出現位置（部分文字列の左端を出現位置とする）が全く同じであるような部分文字列をまとめてグループにした場合、グループの数はいくつになるのだろうか。 これは接尾辞木（wikipedia 授業の資料）を知っているなら簡単に説明できる。 Tに対
大規模データを基にした自然言語処理 - DO++
人工知能基本問題研究会 (SIG-FPAI)でタイトルの題目で一時間ほど話してきました。 発表資料 [pptx] [pdf] 話した内容は - 自然言語処理における特徴ベクトルの作り方と、性質 - オンライン学習, Perceptron, Passive Agressive (PA), Confidence Weighted Learning (CW) 確率的勾配降下法 (SGD) - L1正則化, FOLOS - 索引を用いた効率化, 全ての部分文字列を利用した文書分類 で、スライドで70枚ぐらい。今までの発表とかぶっていないのはPA CW SGD FOLOSあたりでしょうか オンライン学習、L1正則化の話がメインになっていて、その両方の最終形の 確率的勾配降下法 + FOLOSの組み合わせは任意の損失関数に対してL1/L2正則化をかけながらオンライン学習をとても簡単にできるという一昔前
レコメンド, LSH, Spectral Hashing - DO++
WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。 内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。 個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。 レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル（数百万次元とか）で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積（各ベクトルは長
大規模データ処理のための行列の低ランク近似 -- SVD から用例ベースの行列分解まで -- - 武蔵野日記
id:naoya さんのLatent Semantic Indexing の記事に触発されて、ここ1週間ほどちょくちょく見ている行列の近似計算手法について書いてみる。ここでやりたいのは単語-文書行列(どの単語がどの文書に出てきたかの共起行列)や購入者-アイテム行列(どの人がどの本を買ったかとか、推薦エンジンで使う行列)、ページ-リンク行列(どのページからどのページにリンクが出ているか、もしくはリンクをもらっているか。PageRank などページのランキングの計算に使う)、といったような行列を計算するとき、大規模行列だと計算量・記憶スペースともに膨大なので、事前にある程度計算しておけるのであれば、できるだけ小さくしておきたい(そして可能ならば精度も上げたい)、という手法である。 行列の圧縮には元の行列を A (m行n列)とすると A = USV^T というように3つに分解することが多いが、も
ランダムソート(笑)とは - 西尾泰和のはてなダイアリー
誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。 たとえばソート関数が下のような「リストの先頭の値をピボットにしてそれより大きいものと小さいものに振り分けるクイックソート」だったとする。比較関数の所はランダムにしてある。 >>> def quicksort(xs): from random import random if len(xs) < 2: return xs pivot = xs[0] left = [] right = [] for x in xs[1:]: if random() < 0.5: left.append(x) else: right.append(x) return quicksort(left) + [pivot] + quicksort(right
東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。 使ったのは東京メトロ＋都営＋山手線 駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に
クラスタリング (クラスター分析) - Toshihiro Kamishima
クラスタリング (clustering) とは，分類対象の集合を，内的結合 (internal cohesion) と外的分離 (external isolation) が達成されるような部分集合に分割すること [Everitt 93, 大橋 85] です．統計解析や多変量解析の分野ではクラスター分析 (cluster analysis) とも呼ばれ，基本的なデータ解析手法としてデータマイニングでも頻繁に利用されています． 分割後の各部分集合はクラスタと呼ばれます．分割の方法にも幾つかの種類があり，全ての分類対象がちょうど一つだけのクラスタの要素となる場合(ハードなもしくは，クリスプなクラスタといいます)や，逆に一つのクラスタが複数のクラスタに同時に部分的に所属する場合(ソフト，または，ファジィなクラスタといいます)があります．ここでは前者のハードな場合のクラスタリングについて述べます．
Firebugで探索アルゴリズムを見ていこう
Firebugで探索アルゴリズムを見ていこう：コーディングに役立つ！ アルゴリズムの基本（6）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 今回紹介するのは探索のアルゴリズムです。探索もアルゴリズムのテーマとしてはメジャーなもので、とても重要な用語や考え方が出てきます。 あるデータの集合があったとします。それぞれのデータには、個々を識別するためのIDが付いています。このIDをキーと呼びます。このキーに対応するデータを探すのが探索です。 データベースを知っている方なら主キーで検索する動作だと思ってください。例えば、商品のリストがあり、それぞれの商品に商品コードが付いています。商品コード「7100」に対応する商品データ「トマト」を検索するプログラム
新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
はてなブログ | 無料ブログを作成しよう
セメントドリンク、ブラウン管、吊るされた収納、OMORIカフェ、くり抜き、どや顔の初音ミク パチミラ福岡に出演する縁で博多に行きました。 楽しかったのでその時の写真をアップロードします。 博多駅のハートポスト 手描きのグリッチ カニの丸揚げ(おいしかった) フレッシュセメント という名前の飲み物(おいしかった)ごま+バナナスムージーっぽかった？ 泡系…
当たり判定 - ゲームプログラミングWiki
解説 本来当たり判定は格闘ゲームとかにも応用できて共通で書こうとも思いました。 ですが、当たり判定といったらシューティングゲームというくらいに重要性が高いのでここで書きたいと思います. この当たり判定はシューティングゲームにおいて最重要とされる話題です。 今回説明する内容は毎週金曜日にある C3 ゼミで発表した内容です。 尚、今回説明する当たり判定は数学が結構出てきます。気を引き締めましょう。 ↑ 二点間距離を用いた方法 多分誰もが最初に考え付くのがこの方法ではないでしょうか？ 二点間距離と円の半径を用いて当たり判定を実装します。 自分も最初この方法を使いました。 敵の弾の座標を(X1,Y1),弾の半径をR1、自機を(X0,Y0)、自機の半径をR0とします。 半径R1、R0の和が距離に等しいときにちょうど円同士が触れ合い、和が距離以下のときにHITするということです。 bool IsHit
1日で作る全文検索エンジン - Building a full-text search engine in "ONE" day - - とあるはてな社員の日記
最近、「Introduction to Information Retrieval」というStanfordの大学院向け教科書のドラフトを読んでいます。id:naoyaあたりが勉強会で読んでいる教科書です。この教科書には、効率のいい全文検索システムを作るにはどうすればいいか、という(まさに)教科書的手法が網羅的に書いてあり、そのあたりに興味がある人には、非常に興味深く読めるお勧めの本です。 ただ、面白い面白いと言っているだけでは、エンジニアとしては価値半減ですので、GW中にrubyで一日かけて実装してみました。 さすがに実装は、一日で作ったものですから、非常に素朴です。マルチバイト文字はbi-gramで、シングルバイトはスペースなどの区切り記号で認識しています。インデックスは、rubyの処理系のHashやArrayで保持しており、外部にMarshallで書き出す、というものです。検索エンジン
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
moved
Mikio Hirabayashi（平林幹雄）
はてなブログ | 無料ブログを作成しよう
はてなブログ | 無料ブログを作成しよう