A Heuristic Solution to the Closest String Problem Using Wave Function Collapse Techniques

Abstract

The Closest String Problem (CSP) is an NP-Complete problem which seeks to find the geometrical center of a set of input strings: given $k$ strings of length $L$ and a non-negative integer $d$ , construct a solution string $t$ , if it exists, such that the Hamming distance between $t$ and each input string is no larger than $d$ . This paper proposes WFC-CSP, a novel heuristic algorithm inspired by Wave Function Collapse (WFC) techniques to solve CSP. Experimental results show that WFC-CSP is highly reliable and efficient in solving CSP across different configurations and instance sizes. Using extensive test data sets, WFC-CSP’s performance was compared with multiple state-of-the-art algorithms including Gramm et al.’s Fixed-parameter algorithm (FP-CSP), the Ant-CSP algorithm by Faro and Pappalardo using metaheuristic techniques, the third IP formation algorithm by Meneses et al., the LDDA_LSS algorithm by Liu et al., and a sequential version of the heuristic algorithm (Heuris_Seq) by Gomes et al. We observe that WFC-CSP outperforms the other algorithms in solution quality or run time or both metrics. The WFC-CSP algorithm has wide applications in solving CSP in the fields of computational biology and coding theory.

Keywords

• WaveFunctionCollapse
• closest string problem
• NP-complete
• NP-hard
• heuristic