Title:
|
Beam search for the longest common subsequence problem
|
Author:
|
Blum, Christian; Blesa Aguilera, Maria Josep; López Ibañez, Manuel
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
Abstract:
|
The longest common subsequence problem is a classical string problem that concerns finding the common part of a set of strings. It has several important applications, for example, pattern recognition or computational biology. Most research efforts up to now have focused on solving this problem optimally. In comparison, only few works exist dealing with heuristic approaches. In this work we present a deterministic beam search algorithm. The results show that our algorithm outperforms classical approaches as well as recent metaheuristic approaches. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Beam search -Longest common subsequence |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|