Practical algorithm for the Beltway problem with a complexity parameter introduction

The Beltway problem is a famous computational geometry challenge relevant to fields like bioinformatics and crystallography. Not only is the complexity class of the Beltway problem not known but there is no practical non-polynomial time algorithm to solve it. This paper models the problem as a Constraint SatisfactionProblem (CSP) and applies a backtracking approach with forward-checking to explore the solution space. Moreover, it introduces a "multiplicity rate" parameter to measure the input's complexity, observingthat higher multiplicity generally increases run-time. To the best of the author's knowledge, no deterministic algorithm exists that can solve large instances of the Beltway problem.Experimental results indicate that the algorithmperforms efficiently for low-multiplicity instances and acceptably under higher multiplicities.

کلیدواژه ها:

Reconstruction ، Constraint Satisfaction ، Forward Checking