| 講演名 | 2015-12-01 制約を伴うDAG最短路問題の高速解法 竹内 文登(北大), 西野 正彬(NTT), 安田 宜仁(北大), 秋葉 拓哉(NII), 湊 真一(北大), 永田 昌明(NTT), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では，有効非巡回グラフ (DAG) の最短路問題において辺の間に論理制約が含まれるような場合の最短路問題を取り扱う．この問題は通常のDAG最短路問題と違い，途中の頂点までの最短路はそのノードを経由するグラフ全体の最短路に含まれるわけではない．このため，素朴に解こうとすると指数的な部分パスを候補として取り扱うことになってしまう．西野らは指数的な候補を避けるために，BDD-Constraint Search (BCS) という手法を提案している．この方法は，制約を二部決定図(BDD)で表現し，DAG探索中にBDDを参照することで，複数の経路候補候補を併合するものであった．しかし，この手法では，BDDの状態とDAGのノードのすべての組合せについて網羅的に探索するため，制約の種類によってBDDサイズが大きい場合には計算時間が大きいという課題があった．本稿では，制約なしのDAG最短路問題はBCSを緩和した問題であることに着目し，制約なしのDAG最短路をヒューリスティック関数とするようなA*探索をBCSに導入する．さらに，BDD上での最短路問題もBCSの緩和と見ることができる．この性質を用いて，BDD上での最短路とこれら2つの組み合わせをヒューリスティック関数とするようなA*探索も提案する． |
| 抄録(英) | This paper deals with shortest path problems on directed acyclic graphs (DAGs), under logical constraints posed between edges. In this setting, a shortest path to each intermediate node does not always appear in a graph-wide shortest path that contains the node. Thus naive approaches will suffer from exponentially many paths. To avoid this problem, an algorithm called BDD-Constraint Search (BCS) is known. This method represents logical constraints as a Binary Decision Diagram (BDD), and solves the problem by refering BDDs to merge equivalent candidate partial paths. However, since BCS has to generate all possible combinations of DAG nodes and BDD nodes, it becomes slow when the BDD representing constraints is large. Since the shortest path problem without logical constraints is a relaxed problem of the constrained one, we propose an A* search method for BCS that exploits solutions of the original shortest path problem as a heuristic function. Moreover, since the shortest path problem on the BDD is also a relaxation of the constrained shortest path problem, our A* search method can also use the solutions of the shortest path problem on a BDD as a heuristic function. We can use the combination of the above two heuristic functions as another heuristic function. |
| キーワード(和) | 有向非巡回グラフ / 最短路 / A*探索 / 二分決定図 / 動的計画法 |
| キーワード(英) | directed acyclic graph / shortest path / A* search / Binary Decision Diagram / dynamic programming |
| 資料番号 | COMP2015-31 |
| 発行日 | 2015-11-24 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2015/12/1(から1日開催) |
| 開催地（和） | 大阪大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 和田 幸一(法政大) |
| 委員長氏名（英） | Koichi Wada(Hosei Univ.) |
| 副委員長氏名（和） | 増澤 利光(阪大) |
| 副委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 幹事氏名（和） | 亀井 清華(広島大) / 古賀 久志(電通大) |
| 幹事氏名（英） | Sayaka Kamei(Hiroshima Univ.) / Hisashi Koga(Univ. of Electro-Comm.) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 制約を伴うDAG最短路問題の高速解法 |
| サブタイトル（和） | |
| タイトル（英） | A Fast Method for Solving Constrained Shortest Path Problems on Directed Acyclic Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 有向非巡回グラフ / directed acyclic graph |
| キーワード(2)（和/英） | 最短路 / shortest path |
| キーワード(3)（和/英） | A*探索 / A* search |
| キーワード(4)（和/英） | 二分決定図 / Binary Decision Diagram |
| キーワード(5)（和/英） | 動的計画法 / dynamic programming |
| 第 1 著者 氏名（和/英） | 竹内 文登 / Fumito Takeuchi |
| 第 1 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 2 著者 氏名（和/英） | 西野 正彬 / Masaaki Nishino |
| 第 2 著者 所属（和/英） | 日本電信電話株式会社(略称：NTT) Nippon Telegraph and Telephone Corporation(略称：NTT) |
| 第 3 著者 氏名（和/英） | 安田 宜仁 / Norihito Yasuda |
| 第 3 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 4 著者 氏名（和/英） | 秋葉 拓哉 / Takuya Akiba |
| 第 4 著者 所属（和/英） | 国立情報学研究所(略称：NII) National Institute of Informatics(略称：NII) |
| 第 5 著者 氏名（和/英） | 湊 真一 / Shin-ichi Minato |
| 第 5 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 6 著者 氏名（和/英） | 永田 昌明 / Masaaki Nagata |
| 第 6 著者 所属（和/英） | 日本電信電話株式会社(略称：NTT) Nippon Telegraph and Telephone Corporation(略称：NTT) |
| 発表年月日 | 2015-12-01 |
| 資料番号 | COMP2015-31 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | COMP-344 |
| ページ範囲 | pp.9-16(COMP), |
| ページ数 | 8 |
| 発行日 | 2015-11-24 (COMP) |