Rediscover the Monte Carlo - 西尾泰和のはてなダイアリー
僕個人はゲームの思考ルーチンを作ることなどには興味があるので、みんな知っていることだと思っていたのですが、意外と「現在世界最強の囲碁の思考ルーチンはモンテカルロ」ってのは知られてないみたいですね。うっかりすると「そんなわけないだろー」とか言われてしまう。その根底には「モンテカルロはとても収束が遅くて使いものにならない」という過去の記憶があるのかなー。ちょうどJavaScriptが使いものにならないおもちゃ言語だと思われていたように。 囲碁の思考ルーチンを著しく進化させた新しいモンテカルロが昔の単純なモンテカルロとどう違うかというと、UCB1という評価関数で「もっと探索するとヨサゲな局面」を判断して、ヨサゲな局面から優先的に探索するという点なんだけど、そういう定性的な話をしてもピンと来ないよね。同じ発想をモンテカルロで円周率を求めるプログラムに適用したら収束の速さが定量的にはっきり見えて面白
機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう！〜 - EchizenBlog-Zwei
最近の論文で The Learning Behind Gmail Priority Inbox D.Aberdeen, O.Pacovsky & A.Slater というのがある。これはGmailの優先トレイで使っている機械学習のアルゴリズムについて解説したもの。というと難しそうな印象があるが、この論文で紹介されているPassive-Aggressiveという手法は実装がとても簡単。なので今回はこれについて解説するよ。 参考資料: Gmail - 優先トレイ Online Passive-Aggressive Algorithms K.Crammer et al. The Learning Behind Gmail Priority Inbox読んだメモ - 糞ネット弁慶 わかりやすい日本語解説 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBl
ALGORITHM NOTE 最長増加部分列 Longest Increasing Subsequence
東西に並んだ高さの異なるｎ本の木があります。あるキコリがこれらの木を、西から東の方向へ木の高さが小さい順に並ぶように、いくつかの木を切り倒すことにしました。木の数を最大にするにはどの木を切れ（残せ）ばようでしょうか？ このような単純な（くだらない）問題でも、考えられる組み合わせを全て調べようとすると、それは各木を選ぶか選ばないかの組み合わせになるので、計算量はO(2n)となってしまいます。 この問題は、与えられた数列の最長増加部分列 Longest Increasing Subsequence (LIS) を求めることに帰着します。 最長増加部分列とは、与えられた数列 S S = a1, a2 , , , an の増加部分列 （ すべてのi, j (i < j)について ai < aj を満たす部分列 ） の中で長さが最大のものをいいます。 例えば、 S = 4 1 6 2 8 5 7 3
Common Subsequence 解説
問題名：Common Subsequence (PKU) 出典：Southeastern Europe 2003 難易度：☆☆☆ 問題の種類：DP 解法：LCS (Longest Common Subsequence) 解答ソースコード： 1458-deq.cpp アルゴリズムの概略 DPの四天王（？），LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など，通常はこれをひねった問題が出てきます。 LCSとは，二つの値の列（この問題では文字列）が与えられて，最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが，順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが，この問題ではその長
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
2009年12月27日:釣り師的アルゴリズム
Wikipediaによると 長いのでめんどくさい方は読まないでください。 歴史 [編集] 記録に残る最古のアルゴリズムは、エウクレイデスの原論に載っているユークリッドの互除法であるといわれている。これは、二つの整数の最大公約数を求めるアルゴリズムである。 「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル・フワーリズミー (al-Khwarizmi、الخوارزمي) の名前から来ているといわれている。825年に書かれた彼の著作『インドの数の計算法』が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorumアルゴリトミ・デ・ヌーメロ・インドルム』（直訳すると「インドの数におけるアルゴリトミ」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書とし
「Radeon HD 6800」徹底分析。HD 5800から何が変わったのか？
2010年10月22日，AMDはDirectX 11対応GPUの第2世代モデルとして，Radeon HD 6000シリーズを発表した。 第1弾として市場投入されたのは，「Radeon HD 6870」（以下，HD 6870）と「Radeon HD 6850」（以下，HD 6850）の2モデル。製品概要やベンチマークテスト結果はすでに掲載済みだが，今回は，現地時間19日に台湾で開催されたAMD主催のイベント「Technical Forum & Exhibition 2010」（TFE 2010）における事前技術説明会「Northern Islands Architecture Deep Dive」の内容を中心に，これら新GPUシリーズのアーキテクチャについて，もう少し詳しく見ていくことにする。
ORWiki
OR学会50年の歴史の中で，OR事典の編纂・改訂は通算３度目となる．いろいろな理由からOR事典編集委員会は，「OR事典」をWebに公開するという手段をとることになった．前回はCDによる出版であった． 資料編だけは「OR事典」から切り離して，OR学会の通常のホームページの中に移すことになった．これは逆瀬川浩孝委員長のアイディアである。内容の性格上，資料追加も間違いの訂正も広報委員会の責任で簡単に出来るようになる． 前回までの学会の歴史資料はそのまま残してある．今回はデータ追加作業を基本に多少の資料追加を行った．前事務局長の藤木秀夫さんには，その後の学会活動全般にわたる記録をまとめて原稿を作成してもらった．学術会議関係も藤木さんが前回の形式に習って資料原稿を作成し，FMES会長の高橋幸雄さんに目を通していただいた． 各支部から増補追加の原稿が送られてきた．Webのサンプルを見てくださいと言って
qsortを撃墜し(最悪ケースを与え)てみた。 - 簡潔なQ
glibcのqsortをターゲットに、クイックソートの最悪ケースO(n^2)を与えてみた。 先日の記事の通り、glibcのqsortはマージソートだが、非常に大きいデータのときはクイックソートを利用するので、そのように仕向けてみた。 実行した結果、約5億バイトの配列が確保され、ソートにかかった時間は以下のようになった。 マージソート(非アタック用データ)：37126ミリ秒 マージソート(アタック用データ)：46724ミリ秒 クイックソート(非アタック用データ)：39189ミリ秒 クイックソート(アタック用データ)：中断(507514ミリ秒以上) 明らかに最悪ケースである。 環境は OS: Debian GNU/Linux (sid/unstable) Compiler: gcc version 4.3.3 (Debian 4.3.3-8) C Library: glibc version
木の回転 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "木の回転" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年10月) 木の回転（きのかいてん、英: tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。 なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていな
クラスカル法 - Wikipedia
クラスカル法（クラスカルほう、英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 このアルゴリズムは、1956年にジョゼフ・クラスカル（英語版）が Proceedings of the American Mathematical Society で発表した (pp. 48–50)。 クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、逆削除法、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」（それぞれの連結部分の最小全域木の集合）を求められる。 クラスカル法の手順は次の通り。 グラフの各頂点がそれぞれの木に属するように、森（木の集合） F を生成する（つまり頂点1個だけからな
Tutorial "Algorithms for Nearest Neighbor Search" by Yury Lifshits
© COPYRIGHT FREE! Slides and TeX sources including pictures are provided for reuse without any restriction. If you like, you can mention that it was taken from tutorial by Yury Lifshits from http://simsearch.yury.name/tutorial.html. But you are not obliged to do this! Relevant reading For lectures 1-2: P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity Search - The Metric Space Approach, Springe
Oit And Indirect Illumination Using Dx11 Linked Lists
The document discusses using DirectX 11 linked lists and per-pixel linked lists to implement order-independent transparency (OIT) and indirect illumination. It describes how linked lists can be used to store transparent fragments and then sort and blend them for OIT. It also explains how to trace rays through linked lists to compute indirect shadows for indirect illumination. The techniques open u
Risan Suugaku - 一筆書き
一筆書き えっと、小学校ではですね、漢字の書き順を習うわけですよね。 書き順っていうのは、まあ昔の習字の影響もあると思うんですけども、非常にリーズナブルな書き方なわけです。やっぱり書き順と違う書き方をすると、何かおかしいわけですね。あるいは単にそれは、昔トレーニングされてておかしいと思うのかもしれないですけど。 で、これ、「口」なわけです。ちなみに「口」という字をこういう風に書くと、やっぱりおかしいとぼくらは思うように教育されているわけですが、まあ、そう書いてもいいわけです。まあ、これは、「口」っていうのは例えばこういう風なグラフだと思ってもいいわけです。 ここに要するに点があって、その間を枝で結ばれているグラフだと思ってもいいですね。 で、もう既にさっき僕が「口」を縦長に書いたのから、もう分かっている人もいるかも知れないけど、まあこれ、ロ(ろ)でもいいんですが、今度はですね、 (カキカキ
nabokov7; rehash : 意外に奥が深いシャッフルアルゴリズム
October 25, 201014:30 カテゴリプログラミング 意外に奥が深いシャッフルアルゴリズム 前の記事に引き続き，ブログチームの「シャッフルのお時間」の話をします。 毎週の進捗ミーティングのあと，次の週の監視(レビュー)相手を決めるためにシャッフルを行うのですが，ここはプログラマ集団。くじ引きとかではなく，ワンライナーでさらっとシャッフルのプログラムなどを走らせて決めたいものですよね。 ということで，進捗ミーティングの最後はシャッフルのお時間と呼ばれ，誰かひとりがプロジェクタにつながったマシン上でライブコーディングをし，その出力結果によって次週の監視相手が決まる，という儀式の時間になりました。 シャッフルの基本のきまりは以下の通りです。メンバー名の配列を入力とし，「見る人→見られる人」の組み合わせを出力するプログラムを書く。「自分自身を担当する人」が発生してはダメ。その場でコー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
algorithms
実践的アルゴリズム
アルゴリズム - フレッシュアイペディア
プログラミングコンテストでの動的計画法
slidefinder.net