An approximate A∗ algorithm and its application to the SCS problem

✍ Scribed by Gaia Nicosia; Gianpaolo Oriolo

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 123 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00085-3

✦ Synopsis

In this paper we deal with algorithm A * and its application to the problem of ÿnding the shortest common supersequence of a set of sequences. A * is a powerful search algorithm which may be used to carry out concurrently the construction of a network and the solution of a shortest path problem on it. We prove a general approximation property of A * which, by building a smaller network, allows us to ÿnd a solution with a given approximation ratio. This is particularly useful when dealing with large instances of some problem. We apply this approach to the solution of the shortest common supersequence problem and show its e ectiveness.