経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
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+
ACO (Ant Colony Optimization)
注意: このページは「XHTML 1.1 plus MathML 2.0」で書かれていますが、IEではMIME typeが「application/xhtml+xml」だと表示できないようです。Mozillaの場合は数式も表示できるのでapplication/xhtml+xmlバージョンをご覧ください(ただし、まだ書きかけですが)。 ACOとは 都市を選択する確率 時点tにおけるエージェントkが都市iから都市jへ移動する確率は次式で定義される。 p i j k ( t ) = [ τ i j ( t ) ] α [ η i j ] β ∑ l ∈ N i k [ τ i l ( t ) ] α [ η i l ] β ∀ j ∈ N i k (書き途中) いろいろなACO ACOとはフェロモンコミュニケーションを利用して最適化問題を解くアルゴリズムの総称です。ここではTSPに対するACOを
Ibaraki Lab. (Kwansei Gakuin Univ.)
茨木研究室の研究ターゲット 組合せ最適化問題 アルゴリズムの開発とその効率化 メタヒューリスティックによる近似アルゴリズム 問題解決エンジン 現実問題への応用 著作権 copyright©茨木研究室 カウンタ since June 2004 巡回セールスマン問題とは 平面上の n 点を一巡する最短巡回路を求める問題。困難な組合せ問題 の代表例として知られている。このデモは、225点の例であるが、最適解が 得られると“TSP”という文字が浮かび上がる。計算では、ランダムに初期解を発生 したのち、局所探索に基づく改良操作によって局所最適解を得ている。 反復のたびに異なる計算過程をたどるところに注目。
経路探索アルゴリズム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++での実装。ソ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
