最短経路問題におけるアルゴリズム【ウォーシャル・フロイド法】の調査
最短経路問題におけるアルゴリズム【ウォーシャル・フロイド法】の調査 佐藤 史隆, 廣安 知之, 三木 光範 ISDL Report No. 20040716001 2004年 4月 8日 Abstract 1 はじめに 本研究では, 効率の良いネットワークを遺伝的アルゴリズムにより作成することを目的としている. 最適化を行う際に, ネットワークの効率の良さを求めるために, ノード間の最短経路長を求める必要がある. 最短経路長を求めるアルゴリズムには, 全ての2点間の最短路・最短距離を求める方法であるウォーシャル・フロイド法（Warshall-Floyd法）, 特定の2点間の最短路・最短距離を求めるダイクストラ法（Dijkstra法）などがある. 本研究では, 全ての2点間の最短路・最短距離を求める必要があるため, ウォーシャル・フロイド法（Warshall-Floyd法）が有効で
自然言語処理における類似度学習(機械学習における距離学習)について - 武蔵野日記
Twitter でグラフ理論に関する話題が上がっていたので、最近調べている距離学習(distance metric learning)について少しまとめてみる。カーネルとか距離(類似度)とかを学習するという話(カーネルというのは2点間の近さを測る関数だと思ってもらえれば)。 この分野では Liu Yang によるA comprehensive survey on distance metric learning (2005) が包括的なサーベイ論文として有名なようだが、それのアップデート(かつ簡略)版として同じ著者によるAn overview of distance metric learning (2007) が出ているので、それをさらに簡略化してお届けする(元論文自体本文は3ページしかないし、引用文献のあとに表が2ページあって、それぞれ相違点と共通点がまとまっているので、これを見ると非
ALGORITHM NOTE 隣接行列
行列という名の通り、グラフを２次元配列で表現します。配列のインデックスが各ノードの番号に対応します。例えば、この２次元配列を M とすると、M[i][j] がノード i とノード j の関係を表します。 無向グラフ ノード i とノード j の間にエッジがある場合、M[i][j] と M[j][i] の値を 1 とします。エッジがない場合は 0 とします。隣接行列は右上と左下が対照になります。 有向グラフ ノード i からノード j へ向かってエッジがある場合、M[i][j] の値を 1 とします。エッジがない場合は 0 とします。 重みつき無向グラフ ノード i とノード j の間に重さ w のエッジがある場合、M[i][j] と M[j][i] の値を w とします。エッジがない場合は、問題上有り得ない値に設定します。例では∞としていますが、プログラムでは非常に大きな値に設定しておくと
Spaghetti Source - 全点対間最短路 (Floyd Warshall)
説明 Floyd Warshall は隣接行列形式で与えられたグラフの全点対間最短路を求めるアルゴリズムである．負閉路が存在する場合はそれも検出する． アルゴリズムは次の通り．これまでに得られている始点 i から終点 j までの最短路を d[i][j] とするとき，ある頂点 k が存在して d[i][j] > d[i][k] + d[k][j] のとき d[i][j] を更新する．これを k を 1 から n まで増加させながら実行する．これにより，k 番目のループにおける d[i][j] は高々 k 番目の頂点までを中継点に用いる最短経路となって，動的計画法に基づくアルゴリズムが完成する．なお，d[i][i] < 0 のときは i を含む負閉路があることがわかる． このアルゴリズムは，本質的にはグラフの二点対 i,j について，その間のすべての経路にわたる経路積の和を計算するものである．
グラフライブラリ
グラフを扱うためのオープンなクラスライブラリにはBGL(Boost Graph Library)を筆頭に優れたものがたくさんありますが，本ライブラリは 導入が容易：簡単な機能は簡単に記述できること． カスタマイズが容易：ソースコードの一覧性が高いこと． ソコソコの機能でソレナリのパフォーマンス という点を目標に作成しています．特徴は以下の通りです． ノードとエッジの追加（定数時間） ノードとエッジへのインデクスを用いたランダムアクセス（定数時間） 任意のノードとエッジの削除（定数時間） ノードに隣接するノード群とその接続を媒介するエッジ群へのランダムアクセス（定数時間） ノードに隣接する特定のノード，あるいはエッジの検索（線形時間） エッジの両端に接続するノードの検索（定数時間） 有向グラフとして動作（無向グラフとしての利用も可能） 自己ループエッジ（両端が同一ノードのエッジ）と多重エッジ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
PHPにおけるグラフ描画とアルゴリズム
c3-02.PDF