Optimally solving permutation sorting problems with efficient partial expansion bidirectional heuristic search

摘要: In this paper we consider several variants of the problem sorting integer permutations with a minimum number moves, task many potential applications ranging from computational biology to logistics. Each is formulated as heuristic search problem, where different induce sets allowed moves within tree. Due intrinsic nature category problems, which in cases present very large branching factor, classic unidirectional algorithms such A∗ and IDA∗ quickly become inefficient or even infeasible dimension grows. Therefore, more sophisticated are needed. To aim, propose combine two recent paradigms have been employed difficult problems showing good performance: enhanced partial expansion (EPE) efficient single-frontier bidirectional (eSBS). We new class combining benefits EPE eSBS, named Single-frontier Bidirectional Search Enhanced Partial Expansion (eSBS-EPE). then an experimental evaluation that shows eSBS-EPE effective approach for family often outperforming previous methods on large-size instances. With were able push limit solve largest size instances some domains (the pancake burnt puzzles). This novel paradigm hence provides promising framework also other domains.