java - 如何索引大量排列？

Question

我正在尝试编写一个程序来寻找解决特定难题的上帝算法——引导当前状态直到其解决状态的最短序列。

为此，我必须映射所有排列/状态(节点)及其各自的距离，直到解决(深度)为止。

我正在使用一些广度优先搜索概念来获取将拼图置于不同/未访问的排列中的排列，并循环此排列直到没有得到任何新位置。

除此之外，我使用两种算法将排列编码为单个索引并检索排列，目的是使用它来将深度值放入数组中。以下伪代码可以演示我在做什么:

Fill table completely with -1
table[pos2idx(theSolvedPermutation)] = 0
depth = 0
loopbegin {
    numOfVisitedPositions = 0
        for (i = 1 to N_PERMUTATIONS) {
            if (table[i] == depth) then {
                for (each available movement m) {
                    current = pos2idx(m applied to idx2pos(i))
                    if (table[current]= -1) then {
                        numOfVisitedPositions++
                        table[current] = depth + 1
                    } endif
                } endfor
            } endif
        } endfor
    depth++
    print numOfVisitedPositions " positions at distance " depth
} loop while numOfVisitedPositions > 0

但是，在这个映射/索引步骤中，似乎有太多信息无法使用这种方法处理。

这里分别是 pos2idx() 和 idx2pos() 方法的伪代码:

pos2idx(permutation[])
    index = 0
    for i = 1 to length - 2
        index *= (length - i + 1)
        for j = i + 1 to length
            if permutation[i] > permutation[j] then
                index += 1
        endfor
    endfor
return index

idx2pos(index, length)
    n = length
    perm[n]     = 2
    perm[n - 1] = 1
    sum = 0

    for i = n - 2 to 1
        perm[i] = 1 + (index % (n - i + 1))
        sum += perm[i] - 1
        index/= (n - i + 1)
        for j = i + 1 to n
            if perm[j] >= perm[i] then
                perm[j]++
        endfor
    endfor

    if sum % 2 = 1 then
        swap perm[n] with perm[n - 1]

    return perm

拼图有 12 个“移动 block ”，8 种不同的移动和奇偶限制。这最后意味着我们不能得到奇数次交换的排列(例如 [1,2,4,3,...,12]，有效的可以是 [1,2,4,3,12, ...11])，我认为可以用值 12!/2 来表示。但是，可能就复杂性而言，该算法无法完成如此多的数据:我的 notebook i3 和 6GB ram 花了 6 分钟来获得 JavaHeapSizeException 哈哈哈。

考虑到拼图只有 8 个元素和 4 个不同的运动(然后是 8!/2 个排列)，我只是应用了相同的方法，我成功地达到了每秒 130000 到 145000 个解决方案。

那么，对于如何在该算法中处理/索引这么多的排列，或者该算法无法在这样的大型处理中完成，有什么提示吗？感谢任何帮助!

一些引用: - Computer Puzzling - Indexing - Useful Mathematics

Answer 1

一个可以减少要查看的配置数量的考虑因素:

您当前的代码认为两种状态是不同的，但从人类的角度来看它们实际上是相同的；这是您只需转动整个立方体即可进行过渡的时候。这样的转变不算走棋，所以这两个状态应该算是一样的。这将不同状态的数量减少了 12 倍。

例如，您可以要求一个特定的部分始终保持在同一坐标。这意味着您必须重新定义一些可用的移动，这样它们就不会触及这个特定的部分。例如，假设您要将 12 号棋子始终固定在位置 12(它永远不会被排列)，并且您当前有一个移动编码为棋子 10、11 和 12 的排列。然后将该移动重新定义为排列棋子 1..9，就好像您首先将整个立方体朝预期移动的相反方向转动(围绕那个角)，然后执行移动(将棋子 12 带回其主位置)。

这意味着您不必存储关于片段 12 的任何内容:length 可以改为 11。同时，您的表将缩小 12 倍。