グラフ探索ことはじめ - 幅・深さ優先探索 -
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Motivation 人工知能っていうとでぃーぷらぁーにんぐみたいな話になってるのがむかつくのでアンチテーゼにでもなればと思い、思いつきではじめました。たぶん一人でやるのであまり深いところまでは書き/書けません。自分の復習/備忘録的なものでもあります。しかもグラフ理論は自学で学んだぐらいの人間が書いてます。(グラフ理論入門 原著第四版 R.HJ. ウィルソン) 基本は AIMA から引っ張ってきています。 グラフ探索ってなに? カーナビです。つまり、まず、今居る所「スタート」と、目的地「ゴール」があります。通ることの出来る「道路」があっ
/proc/cpuinfo: 全点対間最短路を高速に求める
フィックスターズは今年も ACM ICPC つくば大会 にスポンサーとして協賛しております。今年はコンテスト後の懇親会でクイズを出題しているのですが、その問題準備の際に作ったはいいものの結局使われなかったコードが大量に出てきてしまったため、それらをまとめて簡単な解説とともに公開いたします。 全点対間最短路問題 全点対間最短路問題はN個の頂点を持つ有向グラフにおける任意の2点間の最短路を求める問題です。密なグラフの全点対間最短路を求めるアルゴリズムとしてワーシャル-フロイド法が広く知られており、以下のような非常にシンプルなコードで求めることができます。 // 入力: A[i][j] = 頂点iと頂点jを結ぶ辺の重み // 出力: A[i][j] = 頂点iから頂点jまでの最短路の重みの総和 for(int k = 0; k < N; ++k) for(int i = 0; i < N; ++
近似文字列アルゴリズムのgestalt pattern machingについてメモ
Google 検索でタイポをすると、意図したであろう綴りを教えてくれたり、意図通りの検索結果を返してくれる。 このスペルチェック機能では、入力文字列が本来の文字列とどのくらい似ているのかを評価するアルゴリズムが肝で、編集距離のアルゴリズムはよくしられている。 ふとしたことから、Ratcliff/Obershelp pattern recognition(gestalt pattern maching ともいう) という編集距離とは別のアルゴリズムに出くわした。 このアルゴリズムは1980年代から存在するが、より利便性の良いアルゴリズムが発明されていったからなのか、wikipedia に載っていないくて、手元のアルゴリズム本にもみあたらない。 まだこのアルゴリズムが輝いていた 1988 年に、 Dr. Dobb’s Journal に発表された次の記事(サンプル実装はアセンブリ言語!)を元に
高速な編集距離の計算方法 - Qiita
今日紹介するコードはここにおいてあります。 https://gist.github.com/aflc/6482587 編集距離（levenshtein距離）の計算方法で一番有名なのが動的計画法を使ったもので、これはWikipediaにも載っているお手軽でよく使われているものです。 しかし、この方法は結構時間がかかるので、他にも高速な手法がいくつか提案されています。 NOXさんのブログエントリを読んでいただくのが一番手っ取り早いのですが、ビットパラレル法というのが上手くハマると10倍以上高速です。 ここで紹介されている論文では64文字以上の比較ができないのですが、今回は Heikki Hyyrö, "Explaining and extending the bit-parallel approximate string matching algorithm of Myers", 2001 と
目からウロコ！囚人のジレンマって経済にも繋がる話だったのか！ - 嗚呼、学習の日々
みなさまごきげんよう！ 嗚呼蛙でございます！ 昨日、iTunesのアフィリエイト設定記事を書いたついでにサイドバーにお気に入り楽曲を貼ってみました。 何の役に立つわけでもないですが、なんとなく満足感があるので、今度追記したいですね。 ということで、今日はそんな話とは全く関係ない、職場の営業さんに聞いた面白経済話をご紹介いたします。 囚人のジレンマと経済の関係 囚人のジレンマと経済の関係 みなさんは、囚人のジレンマって話をご存知でしょうか？ 共同である犯罪を行ったA、Bをそれぞれ別室で取り調べをした時、捜査官がそれぞれに対して条件を出して自白を引き出そうとするという話です。 捜査官が出した条件というのが以下の３つになります。 二人とも黙秘したら、二人とも懲役5年。 二人のうち片方だけ自白したら、自白した方は懲役2年、黙秘した方は懲役15年。 二人とも自白したら、二人とも懲役10年。 図にする
キャラソートのアルゴリズムについて調べた - 唯物是真 @Scaled_Wurm
「キャラソート」とは 以下のページのようにキャラ(あるいは人物などの何らかの要素)を2つずつ表示して「どちらか好きか？」という質問に連続で答えていくことで全体のランキングを作るWebサービス(「◯◯キャラソート」、「◯◯ソート」など)が様々な作品について存在している 東方キャラソート どんなアルゴリズムを使っているのかに興味がわいたので調べてみました ソートのアルゴリズム 以下の解説記事を読むとわかるようにマージソートやヒープソートといったソートアルゴリズムを人間にそのままやらせているらしい ただし単純にソートアルゴリズム使うだけではなく、計算量を減らすため引き分けなどの場合にはそのペアのデータを一つにまとめたものとして扱うように工夫している ハロプロ・ソートの解説 咲-saki-キャラソート - 勤々惰々 管理しないsabakan » キャラソートアルゴリズムについて ソートアルゴリズム
とても長い配列の上位M件だけをクイックソートより高速に取り出す - Qiita
というわけで、10倍の差がでた。 当然、配列の長さやソートする長さ、また実装の方法によって性能差は変わってくるが 今回の方法は有効であるということは確認できた。 既存の記事(2015/11/09 20:22 追記) コメント欄でUnordered partial sorting にそれらしきことが書いてあると教えていただいた。 そちらでは、「上位k個を取り出す（ソートは不要）」という問題を考えている。 同様に分割統治法を用いてソートしていきながら、上位k個以内の小区間になったらその区間はソートせずに全て選択して良いとしている。 早い話が、QuickSelectによりk+1番目の要素を探してそれより上位の要素をごそっと抜き出している。 分割統治法で大雑把にソートしていきながら、不要なソートを行わないようにする という同様のアプローチである。 C++のSTLの場合(2015/11/09 22:
HL分解 (Heavy-Light Decomposition) - ペケンペイのブログ
HL 分解 (heavy-light decomposition) についてではなく、パスクエリを複数の列クエリに分解するという考え方について説明する。HL 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。 uv パス上のすべての頂点にxを加算する uv パス上の値の総和を求める 総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が答えになる 木ではなく列であれば segment tree によって効率的に処理できる。HL 分解は木をパスに分解することで、木の問題を列の問題に還元する。木をパスに分解するとはどういうことだろうか。例えば次の図のようなものが木をパスに分解した例になっている。 冒頭で例に出したクエリは次の形に分解できる。 このクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる
Interpolation Search - Negative/Positive Thinking
Interpolation Searchとは 補間探索、内挿探索 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索 探索時間はO(log log n) 二分探索では、O(log n) データに依っては、二分探索の方が速くなる場合もあり得る 計算例 配列vが「1,2,3,5,6,10,12」として、 left = 0, v[left] = 1 right = 6, v[right] = 12 である時、 2分探索では、mid = floor( (left + right) / 2 ) = floor( (0+6) / 2 ) = 3のように決めたりするが、 Interpolation Searchでは、値も考慮し、value=6を探したい場合、 mid
RDB - 実例で学ぶ、JOIN (NLJ) が遅くなる理屈と対処法 - Qiita
"Nested Loop Joinしか取り上げて無いのにタイトルが大きすぎないか" と指摘を頂いたので、タイトルを修正しました。Merge JoinとHash Joinのことはまた今度書こうと思います。 「JOINは遅い」とよく言われます。特にRDBを使い始めて間がない内にそういう言説に触れた結果「JOIN=悪」という認識で固定化されてしまっている人も多いように感じています。 たしかに、JOINを含むようなSELECT文は、含まないものに比べて重たくなる傾向があることは事実です。また、本質的に問い合わせたい内容が複雑で、対処することが難しいものも存在します。しかし、RDBの中で一体どういうことが起きているのかを知り、それに基いて対処すれば高速化できることも少なくないと考えています。 本稿では、JOINの内部動作を解説した上で、Webサービスを作っているとよく出てくるJOIN SQLを例題に
ソートアルゴリズム高速化への道 - kivantium活動日記
先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in
数値計算で必要な数式変形について – はむかず！
@beam2dさんの記事が面白かったのだが、これを読んでよくわからなかった人もそれなりにいるだろうという想定で、補足説明のつもりでこれを書いている。 いろんなところで話をするのだが、「数学≠数値計算」である。数学の知識と数値計算の知識はちょっと違う。方程式の解が解析的に解けて、やった解けた！と思っても、その値をコンピュータで計算して結果を出すまでにさらに工夫が必要なことがよくある。コンピュータ内部での数値表現の特性を理解した上で、コンピュータフレンドリーな数式にさらに変形しなければいけないことがある。 例1: Sigmoid関数の計算 機械学習でよく出てくるSigmoid関数 $$ \sigma(x) = \frac{1}{1+e^{-x}} $$ であるが、これは\( \lim_{x\to \infty} \sigma(x) =1 \), \( \lim_{x\to -\infty} \
ネガマックスの説明がどこもおかしい件 - やねうらおブログ(移転しました)
αβ探索は簡単なコードではあるが直感的には理解しづらい。熟練したプログラマでも慣れていなければ理解しにくい。 「αβ探索ってなんぞや？」って言う人はこの時点でブラウザを閉じてお戻りください。ここから先に腹がよじれるような面白いことは何一つ書いてませんので。 さて、αβ探索が理解できないならMinMax法から勉強しなおすべきで、MinMax法の基本的なコードが次のコードである。 「ミニマックス法」(Wikipedia) http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95 上のMinMax法のコードは自分は局面評価が最大になるものを選び、相手は局面評価が最小になるものを選ぶ。簡単明瞭なコードである。つまり、ここで言う局面評価関数(上記コードの STATIC_VA
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
【リスペクト】マリオメーカーに「65535+65535=131070」を計算させてみた
out of surviceさんの3+3=6動画(sm27235148)を見てすっかり影響され、とうとう動画作成に踏み切るなお動画作成に一番時間がかかったもよう個人的にはかなり小型化出来たと思っていますでももっと頭の回る人が更なる方式、更なる小型化を実現しそう論理回路の解説はリスペクト先の動画やウィキペディアを見てください論理回路はマイクラで少しかじった程度なのでもし間違ったところがあっても生暖かい目で見守ってやってください普段はマリオメーカーで難易度低めのステージ作ってますID:9D1A-0000-0051-3F77ID:C77C-0000-004E-2DE9
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブックマークにおけるアクセス制御 - 半環構造に基づくモデル化
Amazon.co.jp: 並列計算の数理とアルゴリズム: フレデリック・マグレス, フランソワ=グザヴィエ・ルー, 桑原拓也: 本
Amazon.co.jp: ヒラノ教授の線形計画法物語: 今野浩: 本
２円の交点を通る円・直線の方程式
The Unhealthy Obsession with Tree Questions