Advertisement
Published in:
2021 | OriginalPaper | Chapter
10. Fore-and-Back
Authors : Vittorio Maniezzo, Marco Antonio Boschetti, Thomas Stützle
Published in: Matheuristics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Fore-and-Back, previously also denoted as Forward&Backward or simply as F&B (though the algorithm presented in this chapter differs in some details from the previously published ones), is an extension of beam search that can improve its effectiveness and that, when run with no limits on computational resources, becomes an exact solution method. However, by design, Fore-and-Back is mainly concerned with heuristic solving, trying to quickly get high quality solutions with little attention paid to optimality proofs. A significant characteristic of this method is that, despite being a primal only method, it is able to compute bounds to the cost of completing partial solutions, therefore to discard partial solutions from expansion and ultimately to reduce the search space.