A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem

The Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorial optimization problem that formalizes many real world problems. This paper presents a novel randomized search strategy, called probabilistic beam search (PBS), based on the hybridization between beam search and greedy...

Descripción completa

Detalles Bibliográficos
Autores principales: Blum, Christian, Cotta, Carlos, Fernández, Antonio J., Gallardo, José E.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2007
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7120107/
http://dx.doi.org/10.1007/978-3-540-71615-0_4
_version_ 1783514903367122944
author Blum, Christian
Cotta, Carlos
Fernández, Antonio J.
Gallardo, José E.
author_facet Blum, Christian
Cotta, Carlos
Fernández, Antonio J.
Gallardo, José E.
author_sort Blum, Christian
collection PubMed
description The Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorial optimization problem that formalizes many real world problems. This paper presents a novel randomized search strategy, called probabilistic beam search (PBS), based on the hybridization between beam search and greedy constructive heuristics. PBS is competitive (and sometimes better than) previous state-of-the-art algorithms for solving the SCSP. The paper describes PBS and provides an experimental analysis (including comparisons with previous approaches) that demonstrate its usefulness.
format Online
Article
Text
id pubmed-7120107
institution National Center for Biotechnology Information
language English
publishDate 2007
record_format MEDLINE/PubMed
spelling pubmed-71201072020-04-06 A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem Blum, Christian Cotta, Carlos Fernández, Antonio J. Gallardo, José E. Evolutionary Computation in Combinatorial Optimization Article The Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorial optimization problem that formalizes many real world problems. This paper presents a novel randomized search strategy, called probabilistic beam search (PBS), based on the hybridization between beam search and greedy constructive heuristics. PBS is competitive (and sometimes better than) previous state-of-the-art algorithms for solving the SCSP. The paper describes PBS and provides an experimental analysis (including comparisons with previous approaches) that demonstrate its usefulness. 2007 /pmc/articles/PMC7120107/ http://dx.doi.org/10.1007/978-3-540-71615-0_4 Text en © Springer Berlin Heidelberg 2007 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Blum, Christian
Cotta, Carlos
Fernández, Antonio J.
Gallardo, José E.
A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
title A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
title_full A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
title_fullStr A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
title_full_unstemmed A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
title_short A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
title_sort probabilistic beam search approach to the shortest common supersequence problem
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7120107/
http://dx.doi.org/10.1007/978-3-540-71615-0_4
work_keys_str_mv AT blumchristian aprobabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT cottacarlos aprobabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT fernandezantonioj aprobabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT gallardojosee aprobabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT blumchristian probabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT cottacarlos probabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT fernandezantonioj probabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem
AT gallardojosee probabilisticbeamsearchapproachtotheshortestcommonsupersequenceproblem

Ejemplares similares