060108 Locality-Sensitive Hashingの実装が一段落 - 飛行船通信
飛行船通信 飛行船通信MLの主催者(few01)が気になった事を記録するWIKI トップページページ一覧メンバー編集 × 060108 Locality-Sensitive Hashingの実装が一段落 最終更新： few01 2006年01月11日(水) 00:43:46履歴 Tweet 昨年末からプログラミングを始めたLSH: Locality-Sensitive Hashingの開発がやっと一段落した。今日の昼に何とか動くようになった。まだ細かなバグ修正や、処理速度の向上は必要だろうが、大きな山はこえた。 LSHというのはハッシュテーブルの一種である。 ハッシュテーブルというのは、ハッシュ関数を使った索引のことだ。 2006/1/10 ミスを修正 ハッシュ関数とは ハッシュ関数h()というのは、入力の値 x に対して、h(x) の値が、 近い x の場合にぶつかりにくく 一定の範囲に
Locally Linear Embedding (LLE) Homepage
(Notes, e.g. [a] appear below) Input X: D by N matrix consisting of N data items in D dimensions. Output Y: d by N matrix consisting of d < D dimensional embedding coordinates for the input points. Find neighbours in X space [b,c]. for i=1:N compute the distance from Xi to every other point Xj find the K smallest distances assign the corresponding points to be neighbours of Xi end Solve for recons
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
3行でできる超お手軽全文検索 - mixi engineer blog
梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。 使い方 テーブルデータベースについてまずおさらいしておきましょう。PerlやRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。 require 'tokyocabinet' include TokyoCabinet # データベースを開く tdb = TDB::new tdb.open("casket", TDB::OWRITER
A*アルゴリズム (山本隆の開発日誌)
前回の「分岐限定法」の続きです。 『Javaによる知能プログラミング入門』の「2.探索とパターン照合」にあるA*アルゴリズムのソースコードをPythonで実装してみました。 本では分岐限定法の後に山登り法と最良優先探索を説明して問題点を明らかにし、その後でA*アルゴリズムが説明されています。 有向グラフとして表現されている状態空間の、初期状態から目標状態までの探索を行います。 ノード間の□の中の数字は、各ノード間のコストを表します。 各ノートに添付された○の中の数字は、そのノードのヒューリスティックな値を表します。 #! /usr/bin/python # -*- coding: Shift_JIS -*- def printNodes(nodes): """ Nodeのリストの出力用文字列を作成する nodes Nodeのリスト """ return map(str, nodes) cl
経路探索アルゴリズムA* - gan2 の Ruby 勉強日記
RTSや防衛ゲームでよく見るキャラが障害物を避けて通る移動方法って どういうアルゴリズムなんだろう？と気になったのでちょっと調べてみた。 そしたら、たぶんこれだっていうのが見つかったのでメモしておきます。 その名もA*(エースターって読むらしい)。 自分でFlash使って実装してみたい。 以下は参考ページ。 A*（A-star：エースター）探索アルゴリズム 概要の説明はここがすごく分かりやすい。WikipediaのA*の項を見たときは( ゜д゜)ポカーンって感じだったけど、ここの説明を読んだらすっきりした。 A*アルゴリズム、ActionScriptで。 Flashでの実装。ソース(コメントつき)あり。これを読んで勉強かなぁ。 http://torus.jp/memo/x200606/shibuya-js.rd.htmlと合わせて読むのがいいかも。 2007-07-12 C++での実装。ソ
幅優先探索→深さ優先探索でした＞＜ - yasuhisa's blog
バックトラックとかしなくていいので、結構簡単にできた。 # -*- coding: utf-8 -*- require 'pp' class Graph def initialize(edges) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} end def add_edge(edge) @edges.push edge unless @edges.index(edge) end def add_node(u, v) if @edges.index(u).nil? @edges.push u elsif @edges.index(v).nil? @edges.push v end unless @nodes[u].index(v) @nodes[u].push v end end def breadth_first_search(sta
ALGORITHM NOTE 深さ優先探索 Depth First Search (DFS)
001 #define MAX 1000 002 int size; 003 int adjMatrix[MAX][MAX]; // graph structure 004 bool visited[MAX]; 005 006 void dfs( int currentNode ){ 007 visited[ currentNode ] = true; 008 009 // perform some activities here 010 011 for ( int nextNode = 0; nextNode < size; nextNode++ ){ 012 if ( !adjMatrix[ currentNode ][ nextNode ] ) continue; 013 if ( !visited[ nextNode ] ){ 014 dfs( nextNode ); 015 }
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
BWT と PPM - naoyaのはてなダイアリー
Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。 BWT のあら
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://dl.acm.org/citation.cfm?id=997817.997857
Multidimensional Scaling, Second Edition
Multidimensional Scaling
Pheenix - Buy this domain today. | tmps.org is for sale.
サービス終了のお知らせ
サービス終了のお知らせ
カンガルーハウス：テキストライブラリ：2007年7月 A*（A-star：エースター）探索アルゴリズム
サービス終了のお知らせ
深さ優先探索 (山本隆の開発日誌)