如何检查有两个空的n-puzzle是否可解?

问题描述 投票:0回答:1

我已经修改了关于n-puzzle的问题。在这种情况下,这道题有两个空而不是一个空。

Initial State
3   5   1   
4   6   -   
7   2   -   


Goal State
-   1   7   
3   2   -   
5   6   4   

请问有什么算法可以解决这个问题吗?

artificial-intelligence a-star sliding-tile-puzzle
1个回答
1
投票

所有现有的解决常规滑动瓷砖谜题的算法(如A*或IDA*)也可以解决这个变体。有多个空的谜题相当于一个 模式库 对于滑动瓷砖拼图--将部分棋子替换为空白的拼图的精确解法可以作为只有一个空白的原始拼图的启发式解法。

准确地说,它们相当于 加法模式数据库. 你可以将几个组合在一起,并添加它们的启发式数值,只要交换两个空白的动作成本为0,并且没有一个瓦片是重复的)。)

© www.soinside.com 2019 - 2024. All rights reserved.