提出新算法，高效求解最长路径问题
Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics
- 基于双向搜索框架，自然引入前向-前向启发式
- 节点扩展次数减少，部分场景下运行时间更优
- 适合求解最长简单路径等最大值类问题
双向启发式搜索在可逆问题中可降低搜索开销。传统上，前向-前向（F2F）启发式虽能减少节点扩展，但因管理开销过大常导致整体运行时间上升。本文提出BiXDFBnB，一种将原用于最短路径的单前缘双向搜索（SFBDS）框架拓展至广义最长简单路径（GLSP）问题的新算法。该方法天然适配成对状态处理，使前向-前向启发式评估无需额外开销。实验表明，该算法可有效应用于最长简单路径（LSP）、蛇形路径（Snakes）及线圈盒（CIB）等最长路径问题，在多个案例中显著减少节点扩展次数，并在某些情况下提升整体运行效率。
原文摘要 · Abstract (English)
Bidirectional heuristic search can potentially reduce search effort for problems amenable to backward search. Therein, it is well-known that front-to-front heuristics can reduce the number of node expansions, but their overhead is so high that overall runtime almost always increases. We propose BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm that adapts the Single-Frontier Bidirectional Search (SFBDS) framework - originally developed for shortest-path (MIN) problems - to the Generalized Longest Simple Path (GLSP) setting. Because SFBDS inherently operates on paired states, front-to-front (F2F) heuristic evaluation arises naturally and avoids the overhead typically associated with bidirectional frontier management. We show that this adaptation can be successfully applied to maximization (MAX) problems while efficiently handling overlapping constraints. BiXDFBnB is applied to several types of longest-path problems: Longest Simple Path (LSP), Snakes, and Coil-in-the-Box (CIB). Empirical evaluation shows that the new algorithm frequently reduces the number of node expansions and, in some cases, also improves overall runtime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。