双方向ダイクストラ - tshitaの備忘録Ⅱ
・（追記）2015年11月3日：Mi_Sawaさんとtmaeharaさんのソースコードへのリンクとtmaeharaさんのプログラムとの比較 [概要] 双方向ダイクストラを初めて実装したので備忘録としてまとめておきます． 時間がないのでざっくりとしか書いてません． 双方向ダイクストラ法を知らなかったのでMi_Sawaさんに教えていただきました．有り難うございます． 無向グラフ上で始点sと終点tが与えられたときのsからtへの最短路を求める問題を考えます．この問題は2頂点対最短経路問題と呼ばれています．グラフの上で最短経路を求める問題は一般的に最短経路問題と呼ばれておりいろいろな種類があります． 最短経路問題 - Wikipedia 特にsから各頂点への最短経路を求める問題は単一始点最短経路問題と呼ばれており，その問題を解く有名なアルゴリズムにダイクストラ法（ダイクストラ法 - Wikipedi
リバーシのビットボードの操作アルゴリズムのDiagramsを使った可視化
作成日時 2013年12月22日 06:06 JST 最終更新日時 2015年09月08日 22:27 JST タグ Haskellアルゴリズム この記事は Haskell Advenct Calender の17日目の記事です。遅れてしまって申し訳ありません。svg画像が表示できるブラウザで閲覧してください。 学科の課題で夏休みにHaskellで リバーシAIの実装 を行ったのですが、その際に考えた盤面処理のアルゴリズムを画像として可視化したいなと思っていたので、Haskellで図形描画をするライブラリである Diagrams を使って行いました。 ビット演算を駆使してビットを並び替えるようなアルゴリズムは好きなのですが、そうしたアルゴリズムは概して暗号じみています（ビット反転 などが例）。その手のアルゴリズムを上手く画像で表現する、めずらしい試みかと思います。 ビットボードとは リバー
最近傍探索2011 - Preferred Networks Research & Development
こんにちは、二台目のmbaを買うのをためらっている岡野原です。 アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。 アイテムが低次元（例えば2, 3次元）の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元（数百万次元）中の点であったり、アイテム間の距離のみが定義されている場合（カーネル関数など）です。アイテム数は数万から数億ぐらいを想定しています。 最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、 「アイテム集合X = x1,
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
