A probabilistic beam search approach to the shortest common supersequence problem
作者： Christian Blum , Carlos Cotta , Antonio J. Fernández , José E. Gallardo
DOI: 10.1007/978-3-540-71615-0_4
关键词:
摘要: The Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorial optimization problem that formalizes many real world problems. This paper presents novel randomized search strategy, called probabilistic beam (PBS), based on the hybridization between and greedy constructive heuristics. PBS competitive (and sometimes better than) previous state-of-the-art algorithms for solving SCSP. describes provides an experimental analysis (including comparisons with approaches) demonstrate its usefulness.
springer.com
uma.es 
sci-hub.st 参考文章(16)
Jianer Chen, Iyad A. Kanj, Weijia Jia, Vertex Cover: Further Observations and Further Improvements workshop on graph theoretic concepts in computer science. pp. 313- 324 ,(1999) , 10.1007/3-540-46784-X_30
Carlos Cotta, Memetic Algorithms with Partial Lamarckism for the Shortest Common Supersequence Problem Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach. pp. 84- 91 ,(2005) , 10.1007/11499305_9
Carlos Cotta, A Comparison of Evolutionary Approaches to the Shortest Common Supersequence Problem Computational Intelligence and Bioinspired Systems. pp. 50- 58 ,(2005) , 10.1007/11494669_7
J�rgen Branke, Martin Middendorf, Frerk Schneider, Improved heuristics and a genetic algorithm for finding short supersequences Or Spektrum. ,vol. 20, pp. 39- 45 ,(1998) , 10.1007/BF01545528
Rolf Niedermeier, Peter Rossmanith, A general method to speed up fixed-parameter-tractable algorithms Information Processing Letters. ,vol. 73, pp. 125- 129 ,(2000) , 10.1016/S0020-0190(00)00004-1
V. G. Timkovskii, Complexity of common subsequence and supersequence problems and related problems Cybernetics. ,vol. 25, pp. 565- 580 ,(1990) , 10.1007/BF01075212
Martin Middendorf, More on the complexity of common superstring and supersequence problems Theoretical Computer Science. ,vol. 125, pp. 205- 228 ,(1994) , 10.1016/0304-3975(92)00074-2
Jeong Seop Sim, Kunsoo Park, The consensus string problem for a metric is NP-complete Journal of Discrete Algorithms. ,vol. 1, pp. 111- 117 ,(2003) , 10.1016/S1570-8667(03)00011-X
Krzysztof Pietrzak, On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems Journal of Computer and System Sciences. ,vol. 67, pp. 757- 771 ,(2003) , 10.1016/S0022-0000(03)00078-3
David E. Foulser, Ming Li, Qiang Yang, Theory and algorithms for plan merging Artificial Intelligence. ,vol. 57, pp. 143- 181 ,(1992) , 10.1016/0004-3702(92)90016-Q