SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
漢字を類似度検索可能にする (polog)
アイデアとしては単純で、画像情報に落としたあとで全漢字pairに対して全pixelの一致数をカウントするだけ。 これの時にはリアルに全漢字でやろうとしてたんだけど、2万字=>4億ペアなので断念した。常用漢字1945文字を対象とする。 ActiveRecordやら何やら使いたかったけど、普通にやると結構面倒だったのでrailsでプロジェクト作ってscript/runnerした。 ファイル rake db:migrateで create_table :chars do |t| t.column :char, :string t.column :byte, :integer end add_index :chars, :char add_index :chars, :byteこんなのと create_table :similarities do |t| t.column :c
グレゴリオ暦／ユリウス暦 ⇔ ユリウス日 (または一般の通算日数) 変換アルゴリズム
●お知らせ グレゴリオ暦／ユリウス暦計算用Ｃ言語のソースコード・ ライブラリ Calendrier を販売しています． (\1,000 (個人用ライセンス) ほか) Calendrier リファレンス (Ver.1.0) 公開しました． このページの主な更新は Blog でお知らせします． このページでは， グレゴリオ暦またはユリウス暦の日付と，ユリウス日などの通算日数 (通日) を相互変換するアルゴリズムについて説明する． これらは1989年頃に自分で考えたアルゴリズムを再度整理したものである． 一応「ユリウス日」と書いてはいるが，これは通算日数の代表として挙げているだけであり， 基準日注１ (通算日数の第０日とする日付，epoch) は自由に選択できるので，ユリウス日 (Julian Day，JD) や 修正ユリウス日 (Modified JD, MJD) 以外にもさまざまな通算日数を
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
経路探索アルゴリズムA* - gan2 の Ruby 勉強日記
RTSや防衛ゲームでよく見るキャラが障害物を避けて通る移動方法って どういうアルゴリズムなんだろう？と気になったのでちょっと調べてみた。 そしたら、たぶんこれだっていうのが見つかったのでメモしておきます。 その名もA*(エースターって読むらしい)。 自分でFlash使って実装してみたい。 以下は参考ページ。 A*（A-star：エースター）探索アルゴリズム 概要の説明はここがすごく分かりやすい。WikipediaのA*の項を見たときは( ゜д゜)ポカーンって感じだったけど、ここの説明を読んだらすっきりした。 A*アルゴリズム、ActionScriptで。 Flashでの実装。ソース(コメントつき)あり。これを読んで勉強かなぁ。 http://torus.jp/memo/x200606/shibuya-js.rd.htmlと合わせて読むのがいいかも。 2007-07-12 C++での実装。ソ
「圧縮新聞」を作った - phaの日記
僕は昔からロボットがロボットなりに変な文章を生成して喋ったりする人工無脳とかそういう仕組みが好きで、最近はそのへんの仕組みを勉強していました。それで大体仕組みの基本はわかったので簡単なスクリプトを書いてみたよ。 圧縮新聞 このスクリプトはウェブ上にある新聞社とかのニュースの文章を元にして、バラバラにして圧縮してまとめた文章を作るので、ざっと眺めるだけでその日起こった事件の全体が何となくわかるかもしれません。リロードするたび文章は変わります。 生成例 しょうゆ・みそ業界大手のＮＯＶＡ（大阪市）が入った郵便小包は、北朝鮮の鉄道網を連結する計画だったらしいことが２１日、わかった。タンクに灯油を補給した。検案の結果、財政難などをほとんど与えずに６者協議の外相会議の早期再開に期待を表明した国と製薬会社に賠償を求めた。その後、死亡した。 しくみ こういった人工無脳みたいな文章生成をするには形態素解析と
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog（ブログ）
こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日本語版の解説
Class::C3, Algorithm::C3 を勉強したよ！ - IT戦記
DBIx::Class を少し使ったことがあったので Class::C3 をなんとなくで理解していたんです。（ふーん幅優先版の NEXT モジュールでしょ？みたいな感じで。） でも、これは絶対にちゃんと細かい挙動まで勉強しといたほうがいいと思いました。 多重継承とか mixin とかに強くなりたいなと C3 C3 というのは Python 2.3 のドキュメントに書いてある MRO(Method Resolution Order 多重継承したときにどんな感じでメソッドを探索するかという順番) を決めるアルゴリズムで。Algorithm::C3 っていうのがそのアルゴリズムの Perl 実装なんです。 それに！ Parrot でも使えるみたいだし！ ちなみに MRO ってこんな感じね A には add というメソッドがある B にも add というメソッドがある C は A と B を多重継
Hough変換による画像からの直線や円の検出：CodeZine
はじめに Hough変換は、画像から直線や円を検出する技法として知られています。通常の直交座標上の画像を、極座標の二次元空間（直線検出の場合）に変換したり、三次元の空間（円検出の場合）に変換したりして、そこで最も頻度の高い位置を求め、それを逆変換して、直線や円を検出します。 Hough変換は数学的に興味深く、プログラムの対象として面白いため、多くの論文が見られますが、実用化には多くの問題点もあります。 ここでは最初に、一般的なHough変換の基本プログラムを紹介し、次に交通標識認識への応用に特化したプログラムについて述べます。 基本図形認識版アプレットを見る 交通標識認識版アプレットを見る 対象読者 画像から直線や円を検出する方法に興味を持ち、その一つであるHough変換の仕組みを学びたい人。 必要な環境 J2SE 5.0を使っていますが、J2SE 1.4.2でも大丈夫で
BREW 文字認識アプリ "Recog" - パターン認識入門 -
BREW C++ ライブラリ & GUI フレームワーク & XML ミドルウェア / 携帯 Java アプリ圧縮ツール : 株式会社 ソフィア・クレイドル English FAQ パターン認識入門 1. カラー画像からグレースケール画像を作る方法 カメラに限らず、昨今コンピュータで取り扱われる画像は一般的にはカラー画像です。 パターン認識においてカラー画像をそのまま用いる場合もありますが、単にコンピュータに形を認識させたりあるいは今回のアプリケーションのように文字を認識させたりしたい場合には、カラー画像をそのまま使うよりもグレースケール画像を認識に用いた方がアルゴリズムが簡単になります。ここで言うグレースケール画像というのは、明るさの度合いのみによって構成された画像のことです。 この明るさ l は、赤、緑、青の各色成分の明るさをそれぞれ r、g、b とすると、 で表せます。ここで Wr
サポートベクターマシン入門
次へ: はじめに サポートベクターマシン入門 栗田 多喜夫 Takio Kurita 産業技術総合研究所 脳神経情報研究部門 Neurosceince Research Institute, National Institute of Advanced Indastrial Science and Technology takio-kurita@aist.go.jp visitors since Jul. 19, 2002. 概要: 最近、サポートベクターマシン(Support Vector Machine, SVM)と呼ばれるパター ン認識手法が注目されており、ちょっとしたブームになっている。カーネルトリッ クにより非線形の識別関数を構成できるように拡張したサポートベクターマシン は、現在知られている多くの手法の中でも最も認識性能の優れた学習モデルの一 つである。サポートベクターマ
なんか3(仮名): TinySVM で足し算のテスト
svm関係は日本語のドキュメントが少な杉。 わけのわからない数式とかはいっぱいあるけど。 どうやって遊べばいいの? 実態(いったい)。 と、はてなマークが点滅しまくります。 一応、こんな風にしたら遊べました。 もしかしたら、間違っているかもしれませんけど、闇の中で迷っているよりはマシかな。 ぱくりインスパイヤ先 SVMlight MySVM に関する Tips TinySVM: Support Vector MachinesのサイトのBinary package for MS-Windowsからバイナリをダウンロードします。 んで、解凍すると、bin というディレクトリの中にプログラムが入っています。 svm_learn.exe 学習プログラム svm_classify.exe 分類プログラム 学習データを用意します。 svm.learn.dat というファイルに以下をコピペしてください。
Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)
Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し（実際にはそれより小さくすることができるのですが、まあ話のイメージとして）、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない（わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう）。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
Perlでニューラルネットワーク - Shanghai.LOG - 上海ログ
今回も大学のレポートネタ。ニューラルネットワークを用いたパターン認識 をPerlに移植してみた。バックプロパゲーション法って、意外とシンプルなやり方なんだなぁ。 動かし方 Perlのソースを保存して起動すると、学習を始めます。しばらくするとプロンプトが出てくるので、 □□■■■□□ □■□□□■□ ■□□□□□■ ■□□□□□■ ■□□□□□■ ■□□□□□■ ■□□□□□■ ■□□□□□■ ■□□□□□■ □■□□□■□ □□■■■□□の様に、横7×縦11の■□でできた数字のパターンをコピー&ペースト等で入力してあげると、0〜9のどの数字かを判定してくれます。 ソースコード use strict; use warnings; use utf8; use Data::Dumper; $Data::Dumper::Terse = 1; $Data::Dumper::Indent = 1; b
ニューラルネットワークを用いたパターン認識
はじめに ニューラルネットワークの主要なアルゴリズムであるバックプロパゲーション法を、車両のナンバープレートの自動読取りへの応用例で紹介します。完成版のアプレットを見る 対象読者 パターン認識に興味を持ち、特にニューラルネットワークを用いる方法に関心のある人。必要な環境 J2SE 5.0を使っていますが、これより古いバージョンでも、本稿のコードをコンパイルし、実行することができます。ただし、添付のコンパイル済みアプレットの実行には、J2SE Runtime Environment 5.0が必要です。また、CPUパワーが足りないと、学習に時間がかかります。 パターンには、音声、画像、図形、文字などがあります。これらが何であるかを認識することを「パターン認識」と呼び、音声認識の応用は音声入力装置に、画像認識の応用は顔や指紋の照合に使われます。文字認識は、大別して、手書き文字の認識と、印刷文字の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SQLで木と階層構造のデータを扱う――入れ子集合モデル
原稿・資料 ― ありえるえりあ