モンテカルロ木探索法 (Commutative Weblog)
モンテカルロ木探索とは、聞きなれない用語であるが、なんでも最近、コンピュータ囲碁プログラミングの分野で使われている手法らしい。情報処理という雑誌の２００８年６月号の、美添一樹氏の記事に従い、紹介してみる。 最近、コンピュータ将棋の進境が著しい。渡辺竜王対ボナンザの対戦が示すように、トッププロでも、気合を入れてかからないと簡単には勝てないほどである。 一方、コンピュータ囲碁ではどうか。ちょっと前まで、やっとアマチュア三級くらいかも、と言われた。どうしてコンピュータ将棋に比べて弱いのか。一番分かりやすい説明は、１９路盤だと、探索空間が膨大すぎる、というものである。しかし、探索空間だけの問題でもないようである。例えば、９路盤だと、探索空間は、チェスよりも狭い。しかし、旧来のアルゴリズムでは、９路盤でも、アマチュア初段に勝てない。どうも、探索空間だけではなく、評価関数に問題があるようなのである。
乱数の質って、どうやって測るんですか？ - 乱数の検定は 米国... - Yahoo!知恵袋
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1168999531 乱数の検定は 米国政府機関 NISTの SP800-22 の規定に従って調べるの正統派らしいです。 NIST SP800-22 ： http://csrc.nist.gov/groups/ST/toolkit/rng/index.html 一様乱数の性質を検定するときに確認するときによく使うものとして 1) 出現確率(等出現性）のチェック 出現分布の検定 2) 独立性（無相関性）のチェック i番目の乱数とj 番目の乱数の間になんらか規則性がないか (xn,yn)=(i番目の乱数,i+k番目の乱数) のプロット 相関関数(ラグk) の分布の検定 連（同じ数が続く場合の長さ）の分布の検定 3) 周期性 検定には χ^2 分布を使います。 2)では、 yn =
あらゆる数独パズルを解く
Peter Norvig / 青木靖 訳 このエッセイでは、 あらゆる数独パズルを解くという問題に取り組む。制約伝播と探索という2つのアイデアを使うと、ごく簡単に解けるということがわかる(主要なアイデアはコードにして1ページたらずで、補足的なコードが2ページある)。 数独の記法と予備概念 最初に記法をいくつか決めておこう。数独パズルは81個のマス(square)からなる盤面を使う。数独ファンの多くはカラムを1-9で、行をA-Iでラベル付けしており、カラム、行、ボックスのような9個のマスの集まりをユニット(unit)と呼び、ユニットを共有するマスをピア(peer)と呼んでいる。パズルではマスのいくつかが空いており、他は数字が入っている。パズルの目的はこうだ。 それぞれのユニットのマスが1から9の数字の順列によって埋められるようにする。 つまり、1つのユニットに同じ数字が2度現れてはならず、そ
TimeComplexity - Python Wiki
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n). Generally, 'n' is the number of elements current
就活分析録 『数独プログラミング』 ~~「解答が1通り」の数独の問題を自動生成するプログラムの実装と性能評価 ~~
就活・インターンのための情報サイト。Webテスト・ES・志望理由・OB訪問・会社説明会・面接・TOEIC・英語の勉強など 【プログラミングのトピックとしての数独】 数独は9×9のマス目に1~9の数字を単純なルールに基づいて埋めていくパズルです。 http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC 2005年頃から雑誌のパズル欄に登場して以来、世界的に有名になりました。最近では、数独のパズルだけを数百個収録した本も売っているくらいです。電車で数独を説いている人を見たことのある人も多いのではないでしょうか。 数独はプログラミングのトピックとしてとても興味深いです。ルール自体は誰でも1分で理解できる単純明快なものですが、 ・「問題を解くための戦略が複数種類存在する」 ・「解答が1通りになるような数独の問題を生成する時に許される『空白マス数の最大値』が問
数独の高速化 - Cybozu Inside Out | サイボウズエンジニアのブログ
「サイボウズ・アドベントカレンダー」の4日目です（これまでの記事一覧）。どうやら三日坊主は免れたようです（笑）。 (0) はじめに こんにちは。サイボウズ・ラボの川合秀実です。私は主にサイボウズ製品の高速化のお手伝いをしています。しかし先日、製品とは関係ないものを高速化したので、今日はそれを発表します。 サイボウズには社内勉強会がいくつかあって、その中にはC++の勉強会もあります。私はサイボウズの勉強会に参加するのが好きなので、このC++の勉強会に参加してみました。この勉強会では、「数独」というパズルを解くプログラムをC++で書いてみよう、というのが最初のテーマでした。参加者各自がプログラムを書き、翌週にお互いにレビューしあうということが行われました。 ここで私はやらかしてしまいました。ええ、そうです、高速化してしまったのです！ 言うまでもないですが、誰もこんなことは望んでいません。そもそ
グラフ理論（Graph theory） - kanetaiの二次記憶装置
(無向)グラフの要素 要素が頂点(vertex), 点(point), 節点(node)の集合 辺(edge)と呼ばれる頂点の順序対の集合 隣接(adjacent) : 辺(u,v)が存在するとき頂点は隣接するという。 接続(incident) : が辺の端点(endpoint)であるとき、はに接続するという。 多重グラフ(multigraph) : 多重辺(multiple edges)または自己ループ(roop)を含むグラフ ※多重辺やループのない多重グラフをグラフと定義している。 部分グラフ(subgraph) : induced subgraph : 両端点がにある辺を全てが含むならば、をによって生成された(generated)部分グラフと呼ぶ。 次数(degree) 次数(degree) : に接続する辺の個数 孤立点(isolated vertex) : 次数0の頂点 の倍数
三分探索と黄金分割探索 - naoya_t@hatenablog
はい、毎度おなじみのグラフ描きたいだけのエントリですw 今回のお題は「三分探索（ternary search）」。 二分探索（binary search）は割とおなじみかと思うのですが、二分探索が単調増加(減少)関数fについてf(x)=kとなるxを求めるのに対し、三分探索（とか黄金分割探索）は凸関数の極値を求めるのに用います。 詳しくは http://d.hatena.ne.jp/ir5/20090630/1246349028 http://d.hatena.ne.jp/nodchip/20090303/1236058357 辺りを見て頂くとして。 三分探索 探索領域(x0,x3)を三等分するx1,x2を選びます。(x0,x1,x2,x3) で、f(x1)とf(x2)を比べ、f(x)が下に凸な関数なら値が大きい方、上に凸な関数なら値が小さい方の外側（x1ならx0-x1, x2ならx2-x3
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
高速な文字列マッチング - 気ままなブログ
最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。 http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。 AC法については、日本語だと 情報検索アルゴリズム 作者: 北研二,津田和彦,獅々堀正幹出版社/メーカー: 共立出版発売日: 2002/01メディア: 単行本購入: 6人 クリック: 552回この商品を含むブ
シャッフルアルゴリズム - Negative/Positive Thinking
はじめに 配列が与えられたとき、それをバラバラに並び替えたい。 C++のSTLのrandom_shuffle関数を実現したい。 Fisher-Yates shuffle http://en.wikipedia.org/wiki/Fisher-Yates_shuffle 一番使われていると思われるシャッフルアルゴリズム。 n個の配列のうち、n番目の数字と、1番目からn番目のどれかをswap。n番目はもう決定したので、これを除いたn-1個の配列 について同様のことを繰り返す。O(N)。 //http://www.cplusplus.com/reference/algorithm/random_shuffle/ template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle ( Rand
.htm)
「ロボットの運動学と力学」
「詳説ロボットの運動学」補足説明１ ロボットの運動解析に必要な数学と力学 ２００８．４．１ １． ベクトル演算 ２． ロボットの運動解析によく使う関数 ３． 剛体の運動 ４． 剛体の静力学 ５． 剛体の動力学 ロボットの運動を論じることは，幾何学的な運動解析をすることと静力学・動力学解析をすることである．ここで述べるのはロボットの解析に必要な基本的なベクトル演算と力学である． ロボットの解析を理解するためにもっと必要なことは専門書を参照して戴きたい． １． ベクトル演算(vector analysis)と図形のベクトル表現 ロボットの運動で扱う数学は３次元ベクトル演算が大半である．ここではベクトル演算の基本を述べる． ３次元ベクトルを (1.1) と置く．ただ
TopCoder SRM 584, Division 1, Level 1 ( Division 2, Level 2 ) : Egalitarianism - torus711 のアレ
概要 N 人の市民がいて、それぞれの友達関係が与えられる。 友達同士であるような二人の市民について、その所持金の差が d 以内になるようにしたとき、任意の二人の市民（友達同士でなくてもよい）の所持金の差の最大値はいくらになるか求めよ。 解が無限大になる場合は -1 で示せ。 解法 友達関係をグラフとして考えます。 このとき、全体が連結でない場合は異なるグループ間で所持金をいくらでも離すことができるので解はありません。 解が存在する状況下で解を得る方法について考えます。 辺の重みを 1 とすれば、距離 1 について d だけ所持金の差を広げることができます。 また、ある市民からある市民へのパスが二つ以上存在する場合、最短でないものを採用すると最短パスで辿ってきた場合の所持金の差が d を超えてしまうので、採用されるパスは最短経路のみであることがわかります。 最低の所持金額をもつ市民を一人仮定
拡張ユークリッド互除法について
「(省略) これは、a * x + b * y = 1 となる(x, y)を求める問題に他ならない。この式から明らかなようにgcd (a, b) != 1のときは、整数解(x, y)は存在しません。」
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
コンピュータ囲碁におけるモンテカルロ法 ~理論編~ 美添一樹
一段階在庫管理（single stage inventory control）
就活分析録 Sudoku(数独)の問題自動生成アルゴリズム第2弾
WUPC2nd E問題
三角形の面積を外接円の半径を使って求める
グラフ理論の紛らわしい言葉
