アルゴリズム解説
このページでは、リバーシプログラムThellの思考エンジン"spot"で使われているアルゴリズムについて解説します。リバーシプログラミングについてある程度の理解と経験があることを前提としていますので、初めての方は参考文献にあるような文書を参照することから始めるとよいでしょう。 2005/10/01 PVSとalpha-betaの性能比較を掲載。 2005/09/30 置換表の項目を独立。ハッシュキーの生成について追記。 2005/09/23 「関連リンク」を「参考文献」として分離。 2005/07/19 評価関数について気まぐれで書いた文書 2005/07/17 Thell 3.0.2リリースにあわせ、反復深化について追記。 2005/07/06 図を追加。評価関数学習について若干追記。 2005/07/04 置換表について追記。擬似コードを掲載。 2005/06/26 リンクに探索アルゴ
羊の人工知能研究 ～将棋AI開発の日々～
あぁ前回からまた相当な時がたってしまいました(ﾉ´･Д･)ﾉﾐ(m´_ _)m カナリ前の話になってしまうんですが、11月上旬にあったACM/アジア地区予選(横浜大会)に『Hanafuda Shuflle GIVEUP orz』というチーム名で出場した時の話です。何と、今までリバーシのAIについて相当勉強させてもらった、国内でもトップクラスと言われているThellとvsOthaの作者が偶然参加されておられたのです！！これにはカナリの衝撃がありました。自分の卒業研究の研究内容とか話している時に、リバーシのの話題になりThellには勉強させてもらったよ～とか話していると・・・・。 Aさん：「コイツがThellだよ！」 俺：「えっ！？」 Aさん：「vsOthaもいるよ」 俺：「・・・」 この後はかなりリバーシの話題で盛り上がってしまいました（汗。今まで生きてきた中でこれほども世界は狭いものかと感
Yahoo!のAPIを利用してマルコフ連鎖で文章生成(php)
形態素解析→マルコフ連鎖で文章生成のサンプル2007です。 前に書いたやつはchasenを使ってましたが、今回はYahoo!のAPIの 日本語形態素解析Webサービスを利用するサンプルコードです。 幅広い環境で使えるようにPEARのライブラリとかバージョン依存する関数とか使ってません(多分) あと、応用しやすいように冗長に書いてる部分とか、Errorチェックが抜けてる部分がありますが気にしないで下さいｗ 実行結果が見れるサンプルもおいときますね // 解析したい文章 $text = "はじめまして、こんにちは、わたしはLanタソです\nこんにちはこんにちは！！ぼくはまちちゃん！"; $text = str_replace("\n", "。", $text); //改行を適当に。にでも変換しる //API用パラメーター $params = array( 'appid' => '**
ボゴソート - Wikipedia
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。 英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。 トランプを順に並べる場合を例にすると、次のようになる。 トランプ52枚の束を放り投げて、ばらばらにする。 1枚ずつ無作為にすべてを拾い集める。 ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよ
矢沢久雄の早わかりGoFデザインパターン(1) | 日経 xTECH（クロステック）
今回は、パターンを1つだけ紹介します。「Mediatorパターン」です。GoF本では、それぞれのパターンの「目的]「背景」「効果」などが明示されています。私も、ちょっと真似をしてみましょう。複数のオブジェクトを組み合わせてプログラムの機能を実現するという目的において、オブジェクト間の関連がゴチャゴチャになってしまうという背景（問題）があり、Mediatorパターンの採用によって関連をキレイに整理できるという効果があります。説明だけでは、何のことだかわからないと思いますので、具体例をお見せしましょう。 図1[拡大表示](1)をご覧ください。これは、UML（Unified Modeling Language、ユーエムエル）と呼ばれる表記法で記述されたプログラムの設計図です。UMLでは、四角形の中に下線付きで名前を書いてオブジェクトを表し、関連のあるオブジェクトを矢印で結んで示します。ここで関連
Newton's method in Ruby. | Ryan Smith
PRECISION = 0.0001 def newtonian_guess( guess,fx,fdx ) loop do better_guess = guess - ( fx.call( guess ).to_f / fdx.call( guess ).to_f ) return better_guess if ((better_guess - guess).abs <= PRECISION) guess = better_guess end end def sqrt( num ) guess = num/2 return newtonian_guess( guess, lambda {|x| (x**2)-num } , lambda {|x| 2*x } ) end class Float def to_sqrt sqrt( self ) end end p 2.0.to_sqr
Practical Scheme
Shiro Kawai 7/3/2000初出、3/29/2002更新 まあとりあえずカッコは我慢しよう。ラムダとやらも、関数ポインタ＋環境データ ということで納得しよう。しかし、Schemeのループ構文(do)は許せないなあ。 ごちゃごちゃしてるし、途中で脱出できないし。 CやPerlのforやwhileの方がずっと使いやすいね。 え? doなんて使わない? じゃあどうやってループを書くんだ? 消えるループ 簡単だけど、よくありそうな例として、こんなのを考えてみよう。 入力テキストの行数を数える関数count_linesを書きたい。 Cで書くとすれば、こんな感じだ。 /* 例1 */ int count_lines(void) { int count = 0, c; for (c=getchar(); c!=EOF; c=getchar()) { if (c == '\n') count+
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
1時間でわからせたコンシステントハッシュで仮想ノードが必要な理由 - 西尾泰和のはてなダイアリー
ConsistentHashing - コンシステント・ハッシュ法 とあるチャットで聞かれて図まで書いて解説したのでもったいないからエントリー化。ちなみにチャットが1時間弱だったのでこういうタイトルにした。 で、Bが消えるとBの責任範囲が全部Dに押し付けられてDがかわいそうでしょ。 Dの仕事が増えるでしょ。Cとか暇そうじゃん！サーバを複数用意しているメリットが薄れてる。みんなが同じくらい働くのが望ましい。 で、Bが1個の点で表現されているから「Bの手前」もDの1個だけで、そのせいで全部Dが引き受けるはめになった。つまり、仕事が細かく分割されてなくて1個の塊だから引き継ぐ人も1人だけで引き継いだ人涙目。あらかじめ仕事を100分割しとけばみんなで分担して肩代わりできて幸せだよね。 だからサーバが5個だけど点は5個じゃなくて500個打とう。それが仮想ノード。 実装はどうするの？という質問に対して
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
自己参照構造体
構造体を新たな型として宣言するときには、一般に、次の形式を使用する。 struct 構造体タグ { 型 変数名, ..., 変数名; 型 変数名, ..., 変数名; ... 型 変数名, ..., 変数名; }; （具体例） struct student { int number; /* 学籍番号 */ char name[32]; /* 氏名 */ int point[5]; /* 演習の点数 */ }; （struct student型のメモリ領域） 【要点】 この形式を「構造体宣言文」と呼ぶ。 構造体宣言文は、複数のデータからなる新たな「型」を定義している。このように定義された型を総称して「構造体型」と呼ぶ。 構造体宣言文は、構造体型を定義しているとともに、その構造体型に対して「struct 構造体タグ」という型名も同時に定義している。このことから、「struct 構造体タグ」を
JavaScript はどのように実行されるか - IT戦記
JavaScript はどのように実行されるか Safari*1 の実装を例に JavaScript はどのようにして実行されているかを書く。自分用のメモ。日本語の出来は気にしない 1. ブラウザを起動して以下のようなページを開いたとする <html> <head> <script> var a = 1; var b = 2; alert(a + b); </script> </head> <body> </body> </html> 2. インターネットからデータが到着する そうすると WebCore::FrameLoader::write という関数に生の文字列が渡される。型は char* だ。 http://trac.webkit.org/browser/trunk/WebCore/loader/FrameLoader.cpp#L990 この関数の中では、到着した文字の文字コードを解
Project Euler - PukiWiki
Project Euler † プログラムで解く数学の問題集です。 公式サイト 適当に和訳してます。我こそはと思う人はライセンスを確認した上で自由に書いてください。 ↑
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
微分積分