Exact and Heuristic Approaches for the Longest Common Palindromic Subsequence Problem

摘要

The longest common palindromic subsequence (LCPS) problem requires to find a longest palindromic string that appears as subsequence in each string from a given set of input strings. The algorithms that can be found in the related literature are specific for LCPS problems with only two input strings. In contrast, in this work we consider the general case with an arbitrary number of input strings, which is NP-hard. To solve this problem we propose a fast greedy heuristic, a beam search, and an exact A* algorithm. Moreover, A* is extended by a simple diving mechanism as well as a combination with beam search in order to find good quality solutions already early in the search process. The most important findings that result from the experimental evaluation include that (1) A* is able to efficiently find proven optimal solutions for smaller problem instances, (2) the anytime behavior of A* can be significantly improved by incorporating diving or beam search, and (3) beam search is best from a purely heuristic perspective.