第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
VList - Wikipedia, the free encyclopedia
In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.[1] Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
統計的に正しいランキングを行う方法をJavaで書く - バイオインフォマティクスって何ですか？
Java | 統計的に正しいランキングを行う方法を見たのでちょっとJavaで書いてみる。はじめになにがしたいかというと、「レイティング」というのをご存じでしょうか。Amazonとかで商品を購入者が星つけて評価したりしてるやつ。ああいうので「良かったランキング」というのを作りたい。みんなが「購入して良かった」という評価をつけてる商品は、他の人にとっても「良かった商品」になる可能性が高い。いい商品だということがわかるわけです。問題点じゃあどういうふうにランキングをつければいいの？ということを考えると、次の問題にぶちあたる。評価してる人の数の違い。例えば、Aという商品は100人が評価していて、平均の星の数は 4.8 だとする。一方、Bの商品は1人が星5つで評価していたとする。このとき、Aの商品とBの商品ではどちらをランキング上位にすればいいだろうか？あなたならどちらを買いたい？Aはたくさんの人が
北海道を落とすとどう跳ねるのか？の裏側 - てっく煮ブログ
asおかげさまで大好評の 北海道を落とすとどう跳ねるのか？ ですが、どのように作ったか、製作過程を紹介することにします。1. 地図の素材を取ってくるまずは地図の素材が必要です。以下のサイトから拝借しました。白地図、世界地図、日本地図が無料pdf や eps 形式の地図データを無料で配布してくれているありがたいサイトです。2. 都道府県ごとに分割する上記の素材は県境もベクター形式で提供されていて大変ありがたかったのですが、島がどの都道府県に属しているかの情報がありませんでした。そこで、Google Maps と見比べながら、島を都道府県ごとに分類していきました。無事、全ての島を分類し終わって、こんな感じになりました。とても地味な作業でした…。3. 都道府県ごとに SVG で出力する次に、Illustrator 内で分類したデータをプログラムで扱える形式にしなければなりません。ここでは XML
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
Perlでアニメ顔を検出＆解析するImager::AnimeFace - デー
というのを作ったので自己紹介します。 2月頃から、コンピュータでアニメ顔を検出&解析する方法をいろいろ試しつつ作っていて、その成果のひとつとして、無理やり出力したライブラリです。 はじめに はじめにざっとライブラリの紹介を書いて、あとのほうでは詳細な処理の話を僕の考えを超交えつつグダグだと書きたいと思います。 Imager::AnimeFaceでできること Imager::AnimeFaceは、画像に含まれるアニメキャラクター的な人物の顔の位置を検出し、さらに目や口など顔を構成する部品位置や大きさの推定、肌や髪の色の抽出を簡単に行うことができるライブラリです。 これらが可能になると、 画像から自動でいい感じのサムネイルを作成できる 動画から自動でいい感じのサムネイルを作成できる 自動的にぐぬぬ画像が作れる 自動的に全員の顔を○○にできる 顔ベースのローカル画像検索 など、最新鋭のソリューシ
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる 2009-02-26-2 [Programming][YahooHacks] あらかじめ用意された単語セットがあり、それぞれの単語同士の近さを検索ヒット数とそれによるシンプソン係数で求める手順について。 使用している Web API の提供が終了となったため、現在動作しません。ご了承ください。 Yahoo!デベロッパーネットワーク (YDN) のウェブ検索 API を用いる。 - Yahoo!デベロッパーネットワーク http://developer.yahoo.co.jp/ - Yahoo!デベロッパーネットワーク - 検索 - ウェブ検索 http://developer.yahoo.co.jp/webapi/search/websearch/v1/websearch.html ロジック やってることは、下記で書かれ
K-means法によるクラスタリングのスマートな初期値選択を行うK-means++ - kaisehのブログ
K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不適切な初期値選択をすると間違った解に収束してしまいます。 以下は、Introduction to Information Retrievalの16章に出てくる例です。 {d1, d2, ..., d6}をK=2でクラスタリングする場合、{{d1, d2, d4, d5}, {d3, d6}}が大域最適解ですが、初期クラスタの中心をd2, d5で与えると、{{d1, d2, d3}, {d4, d5, d6}}という誤った解に収束してしまいます。 この問題を改善するK-means++という手法を見つけたので、試してみました。 K-means+
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
人工無脳は考える
人工無脳は気軽に「らしさ」を楽しむことができる、知能を持たない会話プログラムです。しかし人工無脳との会話はときとして、論理で固められた人工知能が持ち得なかった人間らしさ ― 即興、いたずら心、感情 ― を私たちに感じさせてくれます。その意味では知能の本質を追求するための別の切り口なのかもしれません。このようなロマンを追い求めて日頃とりとめもなく考える雑談的トピックをまとめてみました。 最近の記事より 厳選おすすめ＆人気書籍 2008/09/28■自我状態を考慮した人工無脳 - 追記 人工無脳は会話の中でユーザに不自然さを感じさせ、会話が続かなかったり、拒絶されるという点が課題となっている。この原因の一つに人工無脳の印象やムードがでたらめに変化し安定していないことが挙げられる。一方、人は通常意識することなく相手に不適切なメッセージが伝わることを避けてうまくコミュニケーションをはかっている。
マルコフ連鎖による自動文章生成 - dogmap.jp
hiromasaさんが作成した WordPress プラグイン WordPress Related Post for Japanese が生成する形態素解析の結果を利用して、マルコフ連鎖による自動文章生成をやってみました。 「Yahoo!のAPIを利用してマルコフ連鎖で文章生成(php)」と「人工無脳は考える:学習ブロック入門編」を参照させていただきました。 マルコフ連鎖についての詳しい説明はリンク先をご覧ください。 今回は、形態素解析された結果を元に三階のマルコフ連鎖で生成してみました。 ただし、単語のつながりだけを見ていて接続はランダムなので、生成された文章は変です。 ちゃんと使用するにはチューニングが必要ですね。 # 素人がちゃちゃっとつまみ食いしても、精度の高いものはできませんね (^^; スカイ・クロラ The Sky Crawlers を食わせてみて生成された文章がこちら。 戦
マルコフ連鎖による文章の自動生成 - Kentaro Kuribayashi's blog
「PEAR::Net_SmartIRC を使って、一定間隔でニュースを配信する IRC BOT を作成する」で作成したごく簡単な BOT はしかし、外部のリソースをひっぱってきて、それを単にそのまま流すことしかできません（RSS をパースする処理はあるけど、本質的には垂れ流してるだけ）。通常 IRC BOT というと、チャンネルのメンバが喋った言葉を憶え、それらをアレンジしたデータを用いて、時には当意即妙に会話に介入することもあればまるで的はずれな発言で場を微妙な雰囲気に陥れることもあるといったものですし、また、なかには日記や Blog を書くすごい BOT さんもいます。 そうなると当然、次の目標は「おしゃべりをする、あるいは日記を書く BOT を作成する」というものになるわけですが、まぁ僕の頭ではいきなりそんなことを実現することは不可能ですし、また、そのような方向で BOT を作成する
人工無能を作ろう〜マルコフ連鎖(2接頭語と1接尾語の場合)
すると、上記のようなテーブルが出来あがります。 マルコフ連鎖のアルゴリズムに当てはめる為に、とりあえず文章の出だしの「酢/鶏」を接頭語として選択します。 で、ここからがマルコフ連鎖のメインの部分です。 作成した参考テーブルから、接頭語が「酢/鶏」に当てはまるものを探し、そこから接尾語を選択します。 上記テーブルには「酢/鶏→は」しかありませんので、接尾語は「は」になります。 これで「酢鶏は」と言う文章がとりあえず出来ます。 同じように、前回の接頭語後ろの「鶏」と接尾語の「は」を組み合わせたもの「鶏/は」を新しい接頭語とし、参考テーブルから次に来る接尾語を探します。 すると「鶏/は→好き」と「鶏/は→嫌い」と言う二つの結果が見つかります。 何らかの方法(ランダムなど)でどちらかを選択します。 今回は「鶏/は→嫌い」を選択します。 すると「酢鶏は嫌い」と言う文章が出来ます。 同じ
人工無能開発メモ - プロジェクト名募集中
人工無能開発メモ - プロジェクト名募集中 目次 名前と方針 動機 うずら欲しいいい 知性とは何かという個人的考察を深めるため 現在のTODO 利用するもの Perl Text::ChaSenを利用して形態素解析 アイデア 環境を理解させる 時系列に関する考察 会話生成の始点となるキーを、環境情報（少し前の会話情報等）を反映した形で表現する 隠れマルコフモデル（HMM）型の辞書を構築する 字句解析と同時にリアルタイムで行う推測と、ストレス値 設計メモ 参考リンク 人工無能 勉強用 謝辞 コメント プロジェクト名募集中 名前と方針 すくすく育つようにする。 プロジェクト名：募集中 設計方針：使えるものは使う。 公開方針：会話可能になったら公開する。 動機 うずら欲しいいい でもソースは公開されてないので、いろいろ参考にして作ってみることにする。 知性とは何かという個人的考察を深めるため 現在
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.ccad.sist.chukyo-u.ac.jp/~mito/syllabi/enshu/rand/index.htm
Yahoo | Mail, Weather, Search, Politics, News, Finance, Sports & Videos
