お知らせ 研究会の開催と会場に参加される皆様へのお願い(2021年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2015-12-01 10:30
制約を伴うDAG最短路問題の高速解法
竹内文登北大)・西野正彬NTT)・安田宜仁北大)・秋葉拓哉NII)・湊 真一北大)・永田昌明NTTCOMP2015-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)
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2015-12-01 10:30:00 
発表時間 30 
申込先研究会 COMP 
資料番号 IEICE-COMP2015-31 
巻番号(vol) IEICE-115 
号番号(no) no.344 
ページ範囲 pp.9-16 
ページ数 IEICE-8 
発行日 IEICE-COMP-2015-11-24 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会