c - 启发式移位数组

原文 标签 c a-star heuristics

给定目标状态

int final[3][3]={{1,2,3},
                 {4,5,6},
                 {7,8,9}};

作为一个随机的初始状态,我只想通过移动表的行(右或左)和列(上下)来将数组排序为final
   7 8 4    by shifting to the right the first row it will become 4 7 8
   2 1 9                                                          2 1 9
   6 5 3                                                          6 5 3

所以我想用一个*搜索,我试图找到一个好的启发。
我已经试过使用错误放置的数组元素。
有什么建议吗?

最佳答案

我认为这是一个代数问题。给出了一组由6个循环(3行3列)生成的置换,您希望找到更多的移动来帮助您获得任何置换。
第一条建议:不是所有的排列都是可能的!由于每个移位都是偶数置换(3个周期是两个置换的组合),所以只有偶数置换是可能的。因此,您将无法找到任何配置的解决方案,其中除了(2,1,3),(4,5,6),(7,8,9)中的两个交换数字之外,所有配置都已就位。
第二条建议。如果r是行移位,c是列移位,则计算rcr'c'的作用,其中r'和c'是逆移位。这个“换向器”又是一个由3个元素组成的循环,但这次它们不在一行或一列中。通过选择不同的r和c,可以得到很多3个循环,这可以在第三条建议中使用。
第三条建议。考虑已经处于最终位置的数字区域。对这个集合的补集应用3个循环来减少它,直到得到一个解决方案。

相关文章:

c - 无法将C语言中的模拟放到网页上

c - gcc“的多个定义”错误

java - A *算法存在的问题[关闭]

java - A *搜索实施

java - Astar的启发式功能

c - 将无符号长整数的每个字节转换为无符号char数组的元素

c - 分离的pthread可以死吗?

java - 明星算法不采取视觉上理想的路线[重复]

algorithm - NSGA 2:伪代码

algorithm - 人工智能/规则来猜测用户在服装/服装方面的品味