6

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

状态 1
1 2
3 0

状态 2
1 3
0 2

我保留在我的树上：

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

这也适用于所有谜题的 5x3、6x6 等谜题

这个想法行得通，但是它浪费了很多内存，并且添加节点需要一些时间：/所以它非常低效。

下一个想法是在 stl 的 std::map< > 中保持访问状态，但我不知道如何制作好的散列函数 - 从拼图状态制作快捷方式（因为我不必存储拼图状态，我只需要信息已被访问。对于 std::map 的密钥或其他保持信息已被访问的想法，您有什么想法吗？

4

3 回答 3

2

假设您只对解决 X,Y <= 16 的谜题 X*Y 感兴趣。我将用 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;
    }
};

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

于 2011-04-14T12:17:34.807 回答
1

我将单个状态表示为 BigInteger 数字（此处提供了一个 c++ 实现，或者如果您想在此处实现您自己的，这里也有一个线程）。

假设您有一个具有 (X,Y) 维度的拼图，您将使用 base = X*Y 创建一个数字，该数字的数字将表示拼图拼成一维。

例如：

State 1
1 2
3 0

这将被展平为

1 2 3 0

然后转换成一个基数为 4 的数字，如：

state = (1 * (4^3)) + (2 * (4^2)) + (3 * 4) + 0;

这将唯一地标识任何谜题的任何给定状态。

于 2011-04-14T10:13:02.330 回答
1

Zobrist 散列在玩抽象游戏的程序中几乎无处不在。

于 2011-04-14T14:12:04.943 回答