「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」:最強最速アルゴリズマー養成講座(1/3 ページ) 典型的なアルゴリズムをたくさん知っている人間が最強か――? いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。 アルゴリズマー養成講座と銘打ってスタートした本連載。もしかすると読者の方の興味は、はやりのアルゴリズムや汎用的なアルゴリズムを知ることにあるのかもしれません。しかし、今回は、いわゆる「典型的なアルゴリズム」を用いずに進めていきたいと思います。 なぜ典型的なアルゴリズムを用いないのか。それは、典型的なアルゴリズムばかりを先に覚え、それだけでTopCoderなどを戦っていこうとした場合、それに少しでもそぐわない問題が出た場合に、まったく太刀打ちできなくなってしまう
クラスタリングツール bayon がとてつもなく素晴らしいです! 2009-06-10-5 [Algorithm][Software] mixi の fujisawa さんによる、C++ で書かれたクラスタリングツール bayon がシンプルイナフで猛烈に素晴らしくてクールです。 - 軽量データクラスタリングツールbayon (mixi Engineers' Blog) http://alpha.mixi.co.jp/blog/?p=1049 - チュートリアル(Tutorial_ja - bayon) http://code.google.com/p/bayon/wiki/Tutorial_ja 詳細は上記URLを見てもらうとして、 たまたま手元に250万件のデータ(ラベル+特徴語リスト)があったのでさっそく試してみました。 ドキュメント数250万件。 各ドキュメントの特徴を現すキーの平
出力と状態が1対1に対応していなくて、状態を直接知ることができないようなものを隠れマルコフモデル(HMM:Hidden Markov Model)といいます。 で、その隠れマルコフモデルで遊ぶために、とりあえず状態遷移と出力文字候補を作ってみます。 この隠れマルコフモデルで適当に確率を設定して実行したときの結果は、こんな感じになりました。 状態遷移:31 32 33 31 32 33 0 31 32 33 0 21 22 0 21 22 0 21 22 31 32 33 31 32 33 0 31 32 33 31 出力:serrar rer te rr rrsertah reht public class HiddenMarkovModel { public static void main(String[] args){ String[] Q = {//状態 "0", "1", "21
動的計画法(Dynamic Programing)は、国内予選レベルではおそらく知らなくてもだいじょーぶです。しかし、4問以上を目指しているのなら、おさえておいた方がいいかもしれません。 というか、あまり上手く説明できないかも。 ここで言う動的計画法は、簡単に言うと、いつ計算しても同じになる値をどこかにとっておいて いつでも呼び出せるようにすることで、重複計算を避けようという考え方です。 私の経験から言わせてもらえば、次のような問題に適応することで効果的な場合が多いです。 ・元の問題を小さな部分問題に分割できる。 ・その部分問題の答えからもとの問題の答えを導ける。(小さいほうから順番に計算できる) ・一番小さな部分問題はすぐに解ける。 ・小さいほうの部分問題は何回も呼び出される。 ・状態数がそんなに大きくない。(大きくないの基準は問題による。) これについては後で述べるとして、例を見てみま
ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基本 テンプレート グラフ
A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent (or "hidden") Markov process (referred to as ). An HMM requires that there be an observable process whose outcomes depend on the outcomes of in a known way. Since cannot be observed directly, the goal is to learn about state of by observing By definition of being a Markov model, an HMM has an addition
問題を解く有効な手法の1つが、最終的な解を求めるために、その問題の小さな部分問題の解を用いることです。一般的に小さな問題はより容易に分析・解決できるものです。この手法の代表的なものに、分割統治法(Divide and Conquer)と動的計画法 (Dynamic Programming: DP)があります。 分割統治法では問題を2つ(またはそれ以上)に分け、それらをそれぞれ解き、元の問題を解くためにそれらの分割して解かれた問題を統合して利用する、という処理を再帰的に行います。マージソートが分割統治法のよい例です。 一方動的計画法は、小さな部分問題を計算して得られた解をメモリに記録し、さらに大きい問題を解くためにそれら記録された結果を有効に使うことによって問題を解きます。 どちらも重要なプログラミング手法ですが、動的計画法は多くの問題の最適な解(最大値や最小値)を求めることができ、様々な問
//// dp.cpp //// DPマッチング: 動的計画法による文字列類似度計算 //// (C) Toru Nakata, toru-nakata@aist.go.jp //// 2004 Oct 19 //// 原典:Needleman, S. B. and Wunsch, C. D. //// "A general method applicable to the search for similarities in the amino acid sequence of two proteins," //// Journal of Molecular Biology, vol.48, pp.443-453, 1970. //// //// DPマッチングとは、系列になってるデータ同士の類似度を比較する方法です。 //// //// 原理は至極簡単で、一致や不一致に応じて、罰金や得
だいぶ前にはじめてのAIプログラミングという本を読んで、N-Gramを作ってみた。 N-gramしてみた - hitode909のダイアリー 今日少し時間があったからマルコフ連鎖もやってみた。 はじめてのAIプログラミング―C言語で作る人工知能と人工無能 作者: 小高知宏出版社/メーカー: オーム社発売日: 2006/10メディア: 単行本 クリック: 85回この商品を含むブログ (23件) を見る マルコフ連鎖を使った文の生成 ある文章を解析して、ある単語が出現した次にどの単語が出現することがあるかを調べる 文の開始となる単語を1つ選ぶ その単語に続く単語を確率的に選択していく 3をしばらく繰り返す こうすると、文っぽいものができるらしい。 あまり覚えていないけど、マルコフ連鎖というのは、次の要素が直前の要素のみによって決まる、という性質がある言語で、その性質を使って、文を作ることができ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く