| 講演名 | 2005-11-10 動的最短経路問題アルゴリズムの性能比較(グラフ, ペトリ, ニューラルネット及び一般) 井口 貴志, 高藤 大介, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 辺重み付き有向グラフをネットワークと呼び, 辺重みの増減という辺操作を考える.なお辺重みを無限から有限に減少(それぞれ, 有限から無限に増加)させることは, 辺の追加(辺の削除)に対応する.動的最短経路問題(DSPPと略記)は次のように定義される: "任意のネットワーク, ソースと呼ばれる指定頂点s, 任意の辺操作系列が与えられたとき, 各辺操作の実行後のネットワークにおける最短経路木を再構成せよ".DSPPの応用として, OSPFやIS-ISのようなリンクステート・アルゴリズムに基づいたルーティングプロトコルにおいて, DSPPを効率良く解くことが必要となる.大規模なネットワークと非常に長い辺操作系列に対する実験結果では, Narvaez(2000年)らがで提案したNST(BF)が, 我々が試した現在の10種類の解法の中で最も高速に解を求めることを示した.また, DSPPを解くには, 静的な解法を繰り返して解くよりも, 動的な解法の方が高速に解を求めることも示した. |
| 抄録(英) | A network in an edge-weighted directed graph and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from an infinite value to a finite one or increasing an edge weight from a finite value to an infinite one, respectively, corresponds to addition or deletion of an edge. The dynamic shortest path problem (DSPP for short) is defined by "Given any network, with a specified vertices, and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires efficiently solving DSPP. Based on experimental results on networks of large size and a lot of edge operations, the paper shows that NST (BF) proposed by Narvaez et. al in 2000 is the fastest among 10 existing algorithms that we have tried. Also shown is that dynamic algorithms are faster than repeating a static algorithm in solving DSPP. |
| キーワード(和) | ネットワーク / 最短パス問題 / 動的アルゴリズム / 静的アルゴリズム |
| キーワード(英) | networks / shortest path problems / dynamic algorithms / static algorithms |
| 資料番号 | CAS2005-56,CST2005-25 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2005/11/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 動的最短経路問題アルゴリズムの性能比較(グラフ, ペトリ, ニューラルネット及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Experiment-based Performance Comparison of Dynamic Shortest Path Algorithms |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ネットワーク / networks |
| キーワード(2)（和/英） | 最短パス問題 / shortest path problems |
| キーワード(3)（和/英） | 動的アルゴリズム / dynamic algorithms |
| キーワード(4)（和/英） | 静的アルゴリズム / static algorithms |
| 第 1 著者 氏名（和/英） | 井口 貴志 / Takashi IGUCHI |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 高藤 大介 / Daisuke TAKAFUJI |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 4 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 4 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2005-11-10 |
| 資料番号 | CAS2005-56,CST2005-25 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 387 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |