BDD, ZDD, フロンティア法, Graphillion - iwiwi 備忘録
詳しい資料へのポインタを示しつつ，自分が読んで理解した範囲の簡潔なまとめを書きます． BDD 入門 湊先生の授業が詳しく分かりやすい． http://www-alg.ist.hokudai.ac.jp/~minato/alg2013.html 概念自体 図を一個見れば一発で理解できる DAG で，各中間ノードは変数で，その変数の値に応じて次に進む子を選ぶ．終着点が答え． 構築法 順序付き既約 BDD (ROBDD) を普通作るらしい．重要な性質を持つらしい． 順序付き ＝ 変数が出現してくる順番が全順序 以下の 2 つのルールを適用し続けていれば既約になる（適用順関係なし） 冗長な接点を全て削除 等価な接点を全て共有 実際には，BDD の間の二項論理演算を繰り返して構築する BDD 同士の演算 (Family Algebra) and, or, xor, not, ... みたいな色々な
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
ALGORITHM NOTE グラフ 最短経路
All Pairs Shortest Path (APSP) problem (全対最短経路問題) は、グラフ G(V, E) に対して、G に含まれるノードの全てのペアの最短経路（距離）を求める問題です。G に負の重みのあるエッジがなければ、この問題は各ノードを起点として Dijkstra's Algorithm を |V| 回行うことによって解くことができます。この方法のオーダーは O(|V|3) または O(|V|(|E| + |V|)log|V|) となります。 Floyd's algorithm は APSP 問題を O(|V|3) で解くことができます。しかも Floyd's algorithm は、G に負の閉路がない限り、G に負の重みを持つエッジが存在しても正しく動作します。負の閉路とは、その閉路を成すエッジの重みの合計が負となっている閉路です（負の閉路をもつとき G に
JavaServer Faces 2.0仕様のメモ
jruby-users MLでJavaBeansのクラスを簡単に生成する方法はない？という質問が出ていました(http://www.ruby-forum.com/topic/1398824)。Groovyだと、def book = new Book(title: "Foo", author: "Bar") でできるみたいだ。GroovyはJavaのためのスクリプティング言語だから、このあたりはやはり便利にできていますねぇ。で、JRubyの場合。Nick Sieger氏が書いていますが、特にビルトインされているラッパのようなものはありません。ただ、Rubyはフレキシブルだから、そんな感じでインスタンスを生成できるようにする方法はいろいろとあるはずです。Sieger氏が提案していたのは*new*という名前のメソッドを定義したモジュールを作って、*extend*でそのモジュールを既存のクラスに追
点と線の部屋
平成１６年２月２３日 第一部 第五十四章 「アフィン平面と射影平面」 新規公開 平成１６年１月４日 第一部 第五十二章 第三節 「4次のアフィン平面」 追加 第一部 第五十三章 「麻雀の組合せの問題（ラテン方陣とアフィン平面）」 新規公開 第二部 第三十三章 「有限体クラスの拡張」 新規公開 平成１５年２月１１日 第二部 第三十二章 「有限体クラス」 新規公開 平成１５年２月３日 第一部 第五十二章 「体とアフィン平面」 新規公開 平成１５年１月１３日 第一部 第三十一章 第三節を不備訂正のため大幅に変更し、また一部を第四節に分離独立させた 平成１４年１１月３日 第一部 第五十一章 「再構成問題 その１」 新規公開 平成１４年７月１５日 第一部 第五十章 「最短経路問題」 新規公開 平成１４年５月１３日 第一部 第四十九章 「弦グラフ その１」 新規公開 平成１４年２月４日
グラフ理論用語 英和対訳表
参考 Graph Theory - From MathWorld Wikipedia: Glossary of graph theory This document was generated through CMS which extended PukiWiki.
ryamadaの遺伝学・遺伝統計学メモ
列挙してみる 遺伝生殖関係 メンデル メンデルの遺伝の法則 集団遺伝学 木村資生 進化解析 系統樹 連鎖不平衡 遺伝的多様性 家系解析 連鎖解析 ゲノム特化事項 オミックス マルチオミックス 時空間離散化(個人・細胞) 量的生物学 統計関係 フィッシャー 離散変数 カテゴリカル変数 連続変数 多変量解析 離散確率過程 多重検定 多段階解析 統合解析 QC 量子確率論 尤度 ベイズ流 ゲノム疫学 データサイエンス関係 大規模データ解析 機械学習 深層学習 ゲーム理論 量子計算 量子計算機 情報関係 マルチバンディット ボルツマンマシン エントロピー 個人情報 数学関係 微分積分学 線形代数学 グラフ理論 情報幾何 多様体 確率微分方程式 物理学関係 波動関数 量子力学 医療関係 臨床ゲノム学 リスク遺伝子 責任遺伝子 リスクコミュニケーション 遺伝子診断 予防医学 出生前診断 個別化医療 倫
無閉路有向グラフ - Google 検索
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフとは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺からなり、辺は頂点同士をつなぐが、ある頂点vから出発し、辺をたどり、頂点vに戻ってこないのが有向非巡回グラフである。 有向非巡回グラフは様々な情報をモデル化するのに使われる。 ウィキペディア
http://tnt.math.metro-u.ac.jp/labo/grad/2004/masa/graph/4.html
上のグラフは有向閉路（すべての辺が同じ向きに連なる閉路）のない有向グラフである. このグラフを無閉路有向グラフという. 無閉路有向グラフは辺の向きを無視したら閉路となる構造を含むことがあってもよい. また定義により辺を一定の向きに沿って進む限り閉路を作らないという性質をもつ. そしてどの頂点からから眺めても木のように見える.言い換えると,深さ優先探索森は上向辺を持たない. ではさっそく無閉路有向グラフの深さ優先探索森を見てみる. 辺の入力をAG, AB, AC, LM, JM, JL, JK, ED, FD, HI, FE, AF, GE, GC, GH, JG, LG, の順番にすると隣接リストは以下のようになる 深さ優先探索森は下図 １つの基本操作としてxからyへ辺がある時,yはxより後,という条件を満たす順序に従ってグラフの頂点を訪問する.すると次の順序が成立する. J K L
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
)
http://en.literateprograms.org/Dijkstra%27s_algorithm_(Scala)
Shortest Path Problem: Dijkstra's Algorithm
http://www.technobahn.com/cgi-bin/news/read2?f=200803231727&page=2
isocchi.com
Microsoft PowerPoint - algorithm-1106.ppt