トライは抽象的なデータ構造であり，実際に構築する場合， 具体的なデータ構造を考える必要があります． 以降の説明では，具体的なデータ構造のことを， 単純にデータ構造と記述するものとします． トライの単純なデータ構造として，配列構造とリスト構造があります． 文字通り，配列構造はトライを配列により実現し， リスト構造はトライを連結リストにより実現します． また，配列構造の利点は高速なことで，リスト構造の利点はコンパクトなことです． 配列構造とリスト構造の説明では，以下に示すトライを例として使います．
Trie Structures
トライは抽象的なデータ構造であり，実際に構築する場合， 具体的なデータ構造を考える必要があります． 以降の説明では，具体的なデータ構造のことを， 単純にデータ構造と記述するものとします． トライの単純なデータ構造として，配列構造とリスト構造があります． 文字通り，配列構造はトライを配列により実現し， リスト構造はトライを連結リストにより実現します． また，配列構造の利点は高速なことで，リスト構造の利点はコンパクトなことです． 配列構造とリスト構造の説明では，以下に示すトライを例として使います．
Sorting algorithms: quite boring until you add sound effects - Geek.com
This site may earn affiliate commissions from the links on this page. Terms of use. Anyone who has ever done a programming course or tried to learn to code out of a book will have come across sorting algorithms. Bubble, heap, merge, there’s a long list of these methods of sorting data. The subject matter is fairly dry. Thankfully someone has found a way to not only make sorting more interesting, b
ベルマンフォードのアルゴリズムで実行される結果も逐次表示 - yasuhisa's blog
離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃんということでやってみた。 pngファイルをアニメーションgifに変換するのはこんな感じで。この辺を参考に。 convert -geometry 320x500! -delay 150 -loop 0 bellman_ford_example_a_uniq*.png bellman_ford_example_a.gif 俺はRubyで書いたわけだけど、こんなことをやってるid:mickey24に「それRでできるよ!!」と言われそうである。 単一始点最短路問題に対するその他のアルゴリズムベルマンフォードのアルゴリズムは単一始点最短路問題に対する
Damn Cool Algorithms: Levenshtein Automata - Nick's Blog
Posted by Nick Johnson | Filed under python, tech, coding, damn-cool-algorithms In a previous Damn Cool Algorithms post, I talked about BK-trees, a clever indexing structure that makes it possible to search for fuzzy matches on a text string based on Levenshtein distance - or any other metric that obeys the triangle inequality. Today, I'm going to describe an alternative approach, which makes it p
Gallery of Processor Cache Effects
Most of my readers will understand that cache is a fast but small type of memory that stores recently accessed memory locations. This description is reasonably accurate, but the “boring” details of how processor caches work can help a lot when trying to understand program performance. In this blog post, I will use code samples to illustrate various aspects of how caches work, and what is the impa
スネークゲームの経路探索アルゴリズム(解決編) - MugiCha
もはやなにもいうまい 長方形のフィールドの場合、どちらかが偶数長ならすべての辺を通る一筆書きでOK. 奇数長＊奇数長なら、2マスの分岐があるが、ここをうまく処理すればOK.
スネークゲームの経路探索アルゴリズム - MugiCha
スネークゲーム、ある領域内に蛇と餌があって、蛇は上下左右に移動でき、餌を食べると長さが1ずつ長くなっていく。蛇が壁にぶつかったり、自分自身にぶつかったら終了。 餌はここでは、蛇が餌を食べる度に、空いた空間のどこかに等確率で出現するとする。 このゲームを自動で行うようなアルゴリズムを考えていたのだが、意外に難しい。 まず前提として、最終的に詰まるまでの長さを最大化することを目的とし、餌の位置は、出現するまでは全くわからないものとする。 一番初めはbkzenさんのこれ。 これはよくわからないアルゴリズムを使っているが、割合はやく詰まってしまう。それも非常に哀れな詰み方で・・ これを改良して自分がつくったのがこれ。 A*を用いている。これで寿命は少し延びたが、餌を食べた時点で蛇の頭がある空間と次の餌のある空間が連結でない場合、経路を作れず詰む。これを防ぐために、できるだけ壁伝いに行くとか実装して
グラフの自動レイアウトに挑戦
2012-08-12 13:37:12 追記 (2022/8) もともとは、Windowsアプリケーション（.NET Windows Formsアプリケーション) として実装していましたが、再公開を機にJavaScriptに移行しました。 きっかけ Nintendo DSのパズルゲーム「レイトン教授と最後の時間旅行」で出題された問題に、複雑に絡まったトンネルが出てくる。 これを解くときに、道が絡まったままだと頭がこんがらがるので、交点に番号を振り、 位置を入れ替えて見やすくした。 これをコンピュータにやらせたら面白いのでは？というのがこの連載記事のきっかけだ。 目次 #1 グラフ構造をSVGで表示 ノード（節点）とエッジ（線）のデータをSVGで表示する。 #2 ばねモデル Eadesのばねモデルをオイラー法を使って実装し、アニメーションさせる。 #3 ノードをドラッグできるようにする ばね
【SEOリサーチ】本文のテキストが鍵を握る！ Yahoo!検索アルゴリズム2009年12月更新分の調査レポート
『MarkeZine』が主催するマーケティング・イベント『MarkeZine Day』の 最新情報をはじめ、様々なイベント情報をまとめてご紹介します。 MarkeZine Day
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
ぺんてるランド
現在将棋界ではボナンザというフリーソフトがなにかと有名です。 フリーソフトでありながらプロ並みの棋力をもっている優れたプログラムで保木 邦仁さんという東北大学の先生が開発されたようです。 従来、プログラムがプロの棋譜や定跡といった知識ベースであったものを、どちらの差し手の方が勝ちやすいかという確率重視へ移行したことが功を奏したようです。 こちらのasahi.comの記事がとてもわかりやすい。 ボナンザに関する著書もありそちらに詳しく掲載されていると思いますが、そのの強さの所以であるモンテカルロ法について触れてみたいと思います。 モンテカルロ法で円周率を求める】 右図は一辺が２Rの正方形の各辺に接する半径Rの円の図。 この正方形の図上にランダムに点を打ち込み、 正方形と円の面積の比により円周率を求めます。 ・正方形に打ち込まれた点の数m ・円の内側に打ち込まれた点の数n とすると （2×R）
続: パーフェクトシャッフルは何回で元に戻るか - 西尾泰和のはてなダイアリー
半年前に作ったパーフェクトシャッフルは何回で元に戻るかの を円形にしたい。 できた。 30枚のカードに「半分に分けて互い違いに組み合わせる」というシャッフルを5回すると元の並びに戻る、という図。 abcdefって6枚のカードがあったら、まず半分に分けて abc, def それから交互に組み合わせて daebfc にする、というシャッフルね。 シャッフルのたびに、1枚目は2枚目になり、2枚目は4枚目になり、4枚目は8枚目になり、8枚目は16枚目になり、16枚目は半分に分けたときに後半の1枚目なので次のシャッフルで1枚目に戻ってくる。5回。 3枚目は6枚目になり、6枚目は12枚目になり、12枚目は24枚目になり、24枚目は後半の9枚目だから17枚目になり、17枚目は後半の2枚目だから3枚目に戻ってくる。やはり5回。 他のカードに関しても同様に成り立つんだけども説明は省略。 Q&A @atusi
ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
二進木の置換表現
図のような二進木があるとする. ノードの番号は中順序で付けてある. 二進木だから左リンクと右リンクがある. つまり k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 LLINK[k] 0 0 1 0 0 4 0 0 8 0 7 6 0 13 0 RLINK[k] 2 0 12 5 0 11 9 0 10 0 0 14 0 15 0 この2組のリンクを1組に圧縮する方法がTAOCP V4F4にあった. permutation representation of binary treeという. ノードがn個あれば, 左と右でリンクは2nあるわけだが, 意味有るリンクは1を子にするもの, 2を子にするもの, (3はルートだから, 子にするものはない,)4を子にすもの,... という n-1個しかない. あとは子なしのnilのリンクだ. n=15の上の表でも, 0 は16
禁断探索法をpythonで
ヒューリスティクスは割と好きだ。スパッととけないものをなんとか現実と折り合いを付けながらよりよい解を見つけるみたいな、なんとも煮え切らない美しさのなさがたまらん。インフォマティクスも似たような香りはする。 特に、「シミュレーションできない学問は学問として未成熟である」という言葉に従うのであれば、創薬研究は（学際領域）と言われている割には未成熟な学問の組み合わせのために発見的な手法の割合が増えすぎるし、精度の高い予測法の誕生もまだまだ先であろう。というわけで、発見的な探索手法は当分有用だし、学際領域故に融合部分での応用が期待されるため、アルゴリズムとしてきちんと押さえておくと色々役に立つ。 メタヒューリスティクスの数理の4章はpythonのコードが載っているので、勉強になる。 第4章 応用 4.1 グラフ分割問題 4.2 最大安定集合問題 4.3 グラフ彩色問題 4.4 巡回セールスマン問題
American Mathematical Society :: Feature Column - Voronoi Diagrams and a Day at the Beach
Introduction Suppose that you live in a desert where the only sources of water are a few springs scattered here and there. For each spring, you would like to determine the locations nearest that spring. The result could be a map, like the one shown here, in which the terrain is divided into regions of locations nearest the various springs. Maps like this appear frequently in various applications a
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
レンダリングサンプル3 - ブレゼンハムのアルゴリズム（直線） - Windows Live
sortvis.org - sorting algorithm visualisation
平面分割アルゴリズムテスト | fladdict
Binomial Heap