Carregant...
Carregant...

Vés al contingut (premeu Retorn)

A probabilistic beam search approach to the shortest common supersequence problem

Autor
Blum, C.; Cotta, C.; Fernández, A.; Gallardo, F.
Tipus d'activitat
Document cientificotècnic
Data
2006-11
Codi
LSI-06-36-R
Repositori
http://hdl.handle.net/2117/87415 Obrir en finestra nova
Resum
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 (inclu...
Citació
Blum, C., Cotta, C., Fernández, A., Gallardo, F. "A probabilistic beam search approach to the shortest common supersequence problem". 2006.
Paraules clau
Combinatorial Mathematics, Greedy Algorithms, Optimisation, Probability, Search Problems, String Matching

Participants

  • Blum, Christian  (autor)
  • Cotta, C.  (autor)
  • Fernández, Antonio J.  (autor)
  • Gallardo, Francisco  (autor)

Arxius