c++ - 保留有关访问状态的信息的想法

Question

我现在正在制作 15 拼图求解器(在 C++ 中)，但我的程序必须解决 3x4 拼图、8x8 拼图等，而不是只有 15 个拼图... -> X x Y 拼图。我必须以某种方式保留有关访问状态的信息，我的第一个想法是制作树，例如:
谜题:

State 1
1 2
3 0

State 2
1 3
0 2

我在我的树上:

root->1->2->3->0
            \_
                \->3->0->2

这也适用于 5x3、6x6 等拼图，适用于所有拼图

这个想法可行，但是浪费了很多内存，而且添加节点需要一些时间:/所以效率很低。

下一个想法是在 STL 的 std::map< > 中保留访问过的状态，但我不知道如何制作好的散列函数——从拼图状态创建快捷方式(因为我不必存储拼图状态，我只需要已访问过的信息。您是否有任何想法，对于 std::map 的键，或其他想法来保持有关已访问状态的信息？

Answer 1

假设您只对解决 X*Y 谜题感兴趣，其中 X, Y <= 16。我将用 X*Y 字节数组表示谜题的状态，其中每个字节给出一个正方形的值在拼图中。在奇怪的基数中使用字节而不是 BigInteger 可能会给您更快的访问和修改时间，因为位算术往往很慢并且在内存/速度权衡方面可能不是好的整体方法。

template<unsigned X, unsigned Y>
class PuzzleState {
    unsigned char state[X*Y];
    public:
    void set(unsigned x, unsigned y, unsigned char v) {
        state[x+X*y] = v;
    }
    unsigned get(unsigned x, unsigned y) {
        return state[x+X*y];
    }
    bool operator<(const PuzzleState<X, Y>& other) const {
        return memcmp(state, other.state, X*Y) < 0;
    }
};

然后只需使用 std::set<PuzzleState<8,8 >与 insert和 find方法。在测试性能是否仍然不合适之后，您可以抛出一个哈希表而不是 std::set。使用简单的哈希函数，例如 Rolling hash .