The ( n 2-1 )-Puzzle and Related Relocation Problems
The ( n 2-1 )-Puzzle and Related Relocation Problems
复制标题
(n 2-1)-谜题及相关的搬迁问题
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. A N I E L R A T N E R A N D M A N F R E D W A R M
中科院分区：
文献类型：
--
作者：
D. A N I E L R A T N E R A N D M A N F R E D W A R M
8 谜题和 15 谜题多年来一直被用作测试启发式搜索技术的领域。根据经验，我们知道这些谜题是“困难的”，因此对于测试搜索技术很有用。在本文中，我们提供了强有力的证据，证明这些难题确实是很好的测试问题。我们将 8 谜题和 15 谜题扩展到 n xn 棋盘，并表明找到扩展谜题的最短解决方案是 NP 困难的，因此被认为在计算上不可行。我们还草拟了一种用于变换 .beards 的近似算法，该算法保证使用不超过常数乘以最小移动次数，其中该常数与给定的胡须及其边长 n 无关。研究的难题是平面重定位问题的实例，其中可达性问题是多项式的，但有效重定位是 NP 困难的。这些问题是自然的机器人问题：机器人需要有效地重新定位飞机上的包裹。我们的研究鼓励研究相关机器人问题的多项式逼近算法。
The 8-puzzle and the 15-puzzle have been used for many years as a domain for testing heuristic search techniques. From experience it is known that these puzzles are "difficult" and therefore useful for testing search techniques. In this paper we give strong evidence that these puzzles are indeed good test problems. We extend the 8-puzzle and the 15puzzle to an n xn board and show that finding a shortest solution for the extended puzzle is NP-hard and is thus believed to be computationally infeasible. We also sketch an approximation algorithm for transforming .beards that is guaranteed to use no more than a constant times the minimum number of moves, where the constant is independent of the given beards and their side length n. The studied puzzles are instances of planar relocation problems where the reachability question is polynomial but efficient relocation is NP-hard. Such problems are natural robeties problems: A robot needs to efficiently relocate packages in the plane. Our research encourages the study of polynomial approximation algorithms for related robotics problems.