تقرير
Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions
| العنوان: | Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions |
|---|---|
| المؤلفون: | Minato, Shin-ichi, Banbara, Mutsunori, Horiyama, Takashi, Kawahara, Jun, Takigawa, Ichigaku, Yamaguchi, Yutaro |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Symbolic Computation, 05C30, 05C85, I.1.3 |
| الوصف: | In this paper, we propose a fast method for exactly enumerating a very large number of all lower cost solutions for various combinatorial problems. Our method is based on backtracking for a given decision diagram which represents all the feasible solutions. The main idea is to memoize the intervals of cost bounds to avoid duplicate search in the backtracking process. In contrast to usual pseudo-polynomial-time dynamic programming approaches, the computation time of our method does not directly depend on the total cost values, but is bounded by the input and output size of the decision diagrams. Therefore, it can be much faster if the cost values are large but the input/output decision diagrams are well-compressed. We demonstrate its practical efficiency by comparing our method to current available enumeration methods: for nontrivial size instances of the Hamiltonian path problem, our method succeeded in exactly enumerating billions of all lower cost solutions in a few seconds, which was hundred or much more times faster. Our method can be regarded as a novel search algorithm which integrates the two classical techniques, branch-and-bound and dynamic programming. This method would have many applications in various fields, including operations research, data mining, statistical testing, hardware/software system design, etc. Comment: Related work (Section 6) is added. Experimental results for another set of problem instances (simple path problem) are added in Section 5.2. Some other minor corrections are made. Style file is changed to LIPIcs format |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2201.08118 |
| رقم الأكسشن: | edsarx.2201.08118 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |