経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた
A* ではゴールへの経路が判明した段階で処理は終了です。 A* はダイクストラ法に比べてゴールに到達するまでに調べるマス目が少ないのが印象的です。 ダイクストラ法と同じように水で例えると、A* では水が少し意思を持っていて、なるべくゴールに近いほうに流れようとするようなイメージです。ここがまさに A* のキモです。ゴールへの近さを加味して、探索するノードの数をなるべく減らそうとします。 A* では、スコアとして f* = g* + h* を用います。各ノードの f* を調べて、f* の値が小さいノードから先に探索していきます。g* はスタート地点からの距離であり、ダイクストラ法で用いるスコアと同じです。h* がゴールへの距離なのですが、実際の最短距離は途中の段階では分からないので、ゴールへの直線距離やマンハッタン距離を利用して計算します。 この、h* の部分がゴールへの近さを加味する部分で
コンプガチャの確率マジックを中学生にも分かるように説明するよ
コンプガチャが話題になっています。 コンプガチャにハマりやすい理由として「最初は当たりやすいが、だんだん確率が低くなる」という指摘があります。 なぜ「確率が低くなる」という現象おきるのでしょうか。 この記事ではコンプガチャの裏側にある確率マジックを分かりやすく解説します。 サイコロの面を全部そろえるゲーム いちばん身近な確率といえばサイコロです。 サイコロを使ったこんなゲームを考えてみます。 サイコロ コンプのルールサイコロを 1 回振るには 10 円が必要。6 つの面をすべてを出せば、500ml のペットボトル飲料をプレゼント。 「サイコロの 6 つの面をすべてコンプしよう」というゲームなので、シンプルな「コンプガチャ」といえます。 このゲーム、あなたなら参加しますか？ 6 つの面を全部だせばよいので、運がよければ 6 回（60円）でペットボトルが手に入ります。なんだかお得そうです。 た
Node.js 0.12 では yield が使えるのでコールバック地獄にサヨナラできる話
Node.js の次のメジャーバージョン 0.12 で yield が使えるようになります。 そのおかげで、JavaScript のコールバック地獄に光が差し込むのです。ああ、さようなら、コールバック地獄。 7 年ごしで実現した yield 2006 年、Firefox 2 のリリースと同時に yield は JavaScript 界に登場しました。随分と前の話ですね。 登場した当時は JavaScript 界隈でけっこう話題になっていました。 JavaScript 1.7 の yield が凄すぎる件について - IT戦記 Latest topics > JavaScript 1.7のyield文ってなんじゃらほ - outsider reflex JavaScript 1.7 の新機能: Days on the Moon 登場したときにはインパクト大きかったものの、結局 Firefox
GitHub で clone するときは SSH じゃなく HTTP を使ったほうが高速
GitHub には clone するための URL として [HTTP]、[SSH]、[Git Read-Only] の 3 つが用意されている。 いままで、SSH に慣れているという理由だけで [SSH] を利用していたのだけど、「SSH は転送速度が遅い」という問題がある。 SSH だとこんなに遅い… さっき、[SSH] で clone してみたら 20～60 KiB/s 程度の速度しか出なかった。 $ git clone git@github.com:nitoyon/tech.nitoyon.com.git Cloning into 'tech.nitoyon.com'... remote: Counting objects: 8856, done. remote: Compressing objects: 100% (2125/2125), done. remote: Total
俺の最強ブログ システムが火を噴くぜ
ブログを「はてなダイアリー」から、自分のサーバーに移転しました。 せっかく移転するなら、2012 年の流行を取り入れた挑戦的なブログにしてみたい！と思い、構想から半年、ついにこの日を迎えることができました。 せっかくなので、凝ったところを自慢させてください。 これが俺史上最強のブログ システムだ ブログ システムとして Jekyll を採用 Jekyll のプラグインを自作 (はてな記法対応、英語ブログとの統合) 履歴管理は GitHub を利用、git push で自動でデプロイ コメント欄には DISQUS を採用、旧ブログへのコメントはインポート済み HTML5 マークアップ、CSS3、レスポンシブ Web デザインでのモバイル対応 盛りだくさんですね。 詳しく説明していきます。 ブログ システムとして Jekyll を採用 最近では WordPress を選ぶのが普通でしょう。Wo
Git で複数ブランチを同時に扱いたいなら git-new-workdir が便利
Git で管理してるレポジトリーで、いくつかのブランチを別々の場所にチェックアウトしたいことがある。 たとえば GUI なツールでブランチ間の比較したい 同時に実行して比較しつつテストしたい ブランチ間でファイルをコピーしたい ドキュメントの生成結果を別ブランチで管理したい といったときに、必要になる。 ブランチの個数だけ clone しちゃえば用は足りそうなんだけど、でかいレポジトリーだったら時間もディスク容量ももったいない。 git-new-workdir を使うべきでしょう！ 先日、「git-new-workdir を使えばワーキング ディレクトリーを複数を作れて便利」と書いてあるブログを読んだ。 git-new-workdir が便利 - #生存戦略 、それは - subtech git-new-workdir の usage を見てたら、別ブランチのワーキング ディレクトリー作成
jQuery の配列系のメソッドをメモ - てっく煮ブログ
JavaScriptjQuery は機能が豊富なので、しばらく使わないと忘れてしまう。ここでは、jQuery と配列の関係に絞って目的別に逆引きできるようにしておく。配列から jQuery オブジェクトを作成$ 関数に渡せばOK $([1,2,3]) NodeList のような配列っぽいものを渡しても解釈してくれる。 $(document.getElementsByTagName("div")) // $("div") と同じ ※内部的には setArray メソッドが呼ばれてるが、外から使うことは稀。jQuery を配列のように扱う要素数を取得するlength プロパティを使えばOK。 $("div").length // document.getElementsByTagName("div").length と同じ jQuery のメソッドを使って操作する限りは、適切に length
はてな記法ワープロ
*はてな記法JavaScript はてな記法ワープロは JavaScript ならではの利点を生かしたダイナミックなワープロです。 試しに色々入力してみてください。即座に出力画面が反映されます((Windows 版 IE6 および Firefox 1.0 でのみ確認しています))。 はてな記法の変換は <a href="http://search.cpan.org/dist/Text-Hatena/">Text::Hatena</a> を JavaScript に移植した "text-hatena.js" を活用しています。 **変更履歴 |*2005/12/1|ソース機能追加 (HTMLソースを表示できます)| |*2005/11/21|はてな記法ワープロ完成| |*2005/11/13|text-hatena.js 移植開始|
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
ベジエ曲線の仕組み (1) - 昔話 - てっく煮ブログ
asドローソフトなどでもお世話になることが多いベジエ曲線について解説していくシリーズ。小学生のころ、BASIC で本のサンプルを入力して遊んでいたのですが、あまりのきれいさに衝撃を受けたプログラムがありました。それはこんな絵を出力するプログラムでした。左上と左下の点をそれぞれの x 座標、y 座標を少しずつ増やしながら、直線を引いています。いくつもの四角形が端に行くにしたがって変形していくところが、いかにも近未来風の CG に見えました（当時は）。しかも、この絵は直線だけで構成されているのに、カーブして見えるところが不思議でなりませんでした。さて、15年のときを経て、このプログラムを ActionScript で実装してみました。点をドラッグして曲線の変化を楽しんでみてください。前置きが長くなりましたが、実はこのカーブして見える曲線の部分は２次ベジエ曲線になっています。３つの黒い点がベジエ
Google Gears の使い道 - てっく煮ブログ
Google Gears (BETA) が発表されました。Google Gears はウェブサービスにオフライン機能を付け加えやすくするためのフレームワークです。フレームワークが提供するのは次の３つの機能です。LocalServerオフラインになったときにも HTML や JavaScript、CSS にアクセスできるようにする。ブラウザのキャッシュ（一時ファイル）を強化したイメージ。Databaseオフライン時に行った動作を記録しておく。SQLite ベース。ブラウザの Cookie を大容量化したイメージ。WorkerPoolCPU を消費する機能をバックグラウンドで実施する機能。setTimeout で無理やり細切れに実行していた部分を任せることができる。スレッド機能とも考えられる。開発者は、これら３つの機能を駆使して、オフライン機能を実装することになります。ありがちな実装パターンは
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
