
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

BDDConstrained A^{*} Search: A Fast Method for Solving Constrained ShortestPath Problems
Fumito TAKEUCHI Masaaki NISHINO Norihito YASUDA Takuya AKIBA Shinichi MINATO Masaaki NAGATA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E100D
No.12
pp.29452952 Publication Date: 2017/12/01 Publicized: 2017/09/05 Online ISSN: 17451361
DOI: 10.1587/transinf.2017EDP7109 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: DAG shortest path, binary decision diagram, combinatorial optimization, A^{*} search,
Full Text: PDF>>
Summary:
This paper deals with the constrained DAG shortest path problem (CDSP), which finds the shortest path on a given directed acyclic graph (DAG) under any logical constraints posed on taken edges. There exists a previous work that uses binary decision diagrams (BDDs) to represent the logical constraints, and traverses the input DAG and the BDD simultaneously. The time and space complexity of this BDDbased method is derived from BDD size, and tends to be fast only when BDDs are small. However, since it does not prioritize the search order, there is considerable room for improvement, particularly for large BDDs. We combine the wellknown A^{*} search with the BDDbased method synergistically, and implement several novel heuristic functions. The key insight here is that the ‘shortest path’ in the BDD is a solution of a relaxed problem, just as the shortest path in the DAG is. Experiments, particularly practical machine learning applications, show that the proposed method decreases search time by up to 2 orders of magnitude, with the specific result that it is 2,000 times faster than a commercial solver. Moreover, the proposed method can reduce the peak memory usage up to 40 times less than the conventional method.

