[Zurück]

M. Djukanovic, G. Raidl, C. Blum:
"A Beam Search for the Longest Common Subsequence Problem Guided by a Novel Approximate Expected Length Calculation";
Vortrag: International Conference on Machine Learning, Optimization, and Data Science, Certosa di Pontignano, Siena, Italy; 10.09.2019 - 13.09.2019; in: "Machine Learning, Optimization, and Data Science", LNCS, 11943 (2020), ISBN: 978-3-030-37598-0; S. 154 - 167.

The longest common subsequence problem (LCS) aims at
nding a longest string that appears as subsequence in each of a given
set of input strings. This is a well known NP-hard problem which has
been tackled by many heuristic approaches. Among them, the best performing
ones are based on beam search (BS) but di er signi cantly in
various aspects. In this paper we compare the existing BS-based approaches
by using a common BS framework making the di erences more
explicit. Furthermore, we derive a novel heuristic function to guide BS,
which approximates the expected length of an LCS of random strings.
In a rigorous experimental evaluation we compare all BS-based methods
from the literature and investigate the impact of our new heuristic
guidance. Results show in particular that our novel heuristic guidance
leads frequently to signi cantly better solutions. New best solutions are
obtained for a wide range of the existing benchmark instances.
Keywords: string problems; expected value; beam search

http://dx.doi.org/10.1007/978-3-030-37599-7_14

https://publik.tuwien.ac.at/files/publik_288244.pdf