| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2015-12-01 10:30 制約を伴うDAG最短路問題の高速解法 ○竹内文登（北大）・西野正彬（NTT）・安田宜仁（北大）・秋葉拓哉（NII）・湊 真一（北大）・永田昌明（NTT）  COMP2015-31 |
|
| 抄録 | （和） | 本稿では，有効非巡回グラフ (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 / / / | |
| 文献情報 | 信学技報, vol. 115, no. 344, COMP2015-31, pp. 9-16, 2015年12月. | |
| 資料番号 | COMP2015-31 | |
| 発行日 | 2015-11-24 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2015-31 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2015-12-01 - 2015-12-01 |
| 開催地（和） | 大阪大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2015-12-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 制約を伴う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 |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 講演者 | 第1著者 |
| 発表日時 | 2015-12-01 10:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2015-31 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | no.344 |
| ページ範囲 | pp.9-16 |
| ページ数 | 8 |
| 発行日 | 2015-11-24 (COMP) |
[研究会発表申込システムのトップページに戻る]