我一直在用C语言开发一个15拼图求解器。我的代码在使用大量内存时遇到了问题。

我不会发布我的代码，因为它太长了…我实现了大部分我使用的库，这可能会让你感到困惑。让我们从基础开始吧。

我目前使用的东西包括：（所有这些都是用C语言实现的）

– 斐波那契堆：

/* 斐波那契堆的结构 */typedef struct _fiboheap {    int  size;           // 堆中节点的数量    node min;            // 指向堆中最小元素的指针    funCompare compare;  // 用于比较堆中节点的函数    freeFunction freeFun;// 用于释放堆中节点的函数} *fiboheap;/* 斐波那契堆节点的结构 */typedef struct _node {    node parent;    // 指向父节点的指针    node child;     // 指向子节点的指针    node left;      // 指向右兄弟的指针    node right;     // 指向左兄弟的指针    int  degree;    // 节点的度数    int  mark;      // 标记    void *key;      // 节点的值（这里是元素）} *node;

– 哈希表

这是我唯一没有自己实现的部分，我使用的是uthash。

– 15拼图状态表示

这是一个有趣的话题。在解释这里的情况之前，让我们先稍微思考一下15拼图问题…我们知道，15拼图有16个瓷砖（我们将空白瓷砖计为编号为0的瓷砖）。那么，15拼图问题有多少可能的状态呢？嗯，它有16的阶乘个状态。所以，这是一个非常多的状态。这意味着我们希望我们的状态尽可能小…如果我们的初始状态离解决方案太远，我们可能会探索如此多的状态，以至于我们的程序内存会爆炸。

所以…我的15拼图表示方法是使用位和逻辑运算符：

/* 15拼图状态表示的结构 */typedef struct _state {    unsigned int quad_1; /* 这个整数代表前8个数字 */    unsigned int quad_2; /* 这个整数代表后8个数字 */    unsigned short zero; /* 这是零的位置 */} *state;

所以我所做的是使用逻辑运算符来移动和改变数字，尽可能使用最小的空间。

注意这个结构的大小是12字节（因为它有三个整数）

– 曼哈顿距离

这只是众所周知的曼哈顿距离启发式。你基本上是计算每个数字当前位置到目标状态中数字位置的距离之和。

– A*的实现和与A*一起使用的节点结构

让我们从节点开始吧。

typedef struct nodo_struct {    nodo parent;        // 指向节点父节点的指针    state estado;       // 与节点关联的状态    unsigned int g : 8; // 节点的成本    action a;           // 到达此节点的动作                        // 如果为null，则表示这是初始节点} *nodo;

注意这些节点与斐波那契堆中的节点无关。

现在是这个话题的主要原因…我目前使用的A*的伪代码。

a_star(state initial_state) {    q = new_fibo_heap; // 按（成本g）+（曼哈顿距离）排序                       // 它将包含指向状态的指针的节点    q.push(make_root_node(initial_state));    closed = new_hash_table();    while (!q.empty()) {        n = q.pop();        if ((n->state ∉ closed) || (n->g < dist(n->state))) {         /* 上面使用的dist也存储在哈希表中 */            closed.insert(n->state);            dist(n->state) = n->g;   // 更新哈希表            if (is_goal(n->state)) {                return extract_solution(n); // 通过父节点，返回路径            }            for <a,s> ∈ successors(n->state) {            // 'a'是动作，可以是'l', 'r', 'u', 'd'            // 's'是n的后继状态                if (manhattan(s) < Infinity) {                    q.push(make_node(n,a,s));                    // 假设manhattan是安全的                }            }        }    }    return NULL;}

所以我还没有能够回答的问题是…

如何有效地管理内存？你可以重用状态或节点吗？这会带来什么后果？

我的意思是，如果你看一下伪代码。它没有考虑重用状态或节点。它只是不断地分配节点和状态，即使它们之前已经被计算过了。

我一直在思考这个问题…每次运行求解器时，它可以很快地扩展数百万个节点。正如我们所知，当你找到另一条路径的成本低于之前的路径时，A*可能会重新探索节点。这意味着…如果我们探索了100万个节点，将会有2400万字节（哇）…考虑到每个节点都有一个状态，那将是每个节点14字节，这些是1400万字节…

最终，我需要一种重用/释放空间的方法，这样我的电脑在执行这个求解器时就不会崩溃。

(PD: 抱歉这篇文章太长了)

回答：

你做这个是作业还是为了好玩？

如果是出于好玩，那么不要使用A*，使用IDA*。IDA*会更快，而且几乎不使用内存。此外，你可以使用额外的内存来构建更好的启发式方法，从而获得更好的性能。（如果你在谷歌上搜索“pattern database”，应该能找到足够的信息。这些是由Jonathan Schaeffer和Joe Culberson发明的，但Rich Korf和Ariel Felner进行了详细的研究。）

IDA*有一些缺点，并不适用于所有领域，但它几乎是完美的适合滑动拼图游戏。

另一个可能有帮助的算法是广度优先启发式搜索。这篇论文和其他论文讨论了如何完全避免存储关闭列表。

基本上，很多聪明人之前已经解决过这个问题，他们已经发表了他们的方法/结果，所以你可以从中学习。

以下是一些改进你的A*的建议：

• 我发现使用斐波那契堆并没有带来多少速度上的提升，所以你可能想要使用更简单的结构。（虽然自从我上次尝试以来，可用的实现可能已经有所改进。）

• 节点的f成本会以2为增量跳跃。因此，你可以将f成本分桶，只需关注同一f成本层中的项目的排序。FIFO队列实际上工作得相当好。

• 你可以使用这篇论文中的想法，将15拼图表示转换为排列，这将需要大约43位来表示完整的表示。但是，扩展状态会变得更加昂贵，因为你必须转换成不同的表示来生成移动。

• 使用禁止操作符完全避免存储关闭列表。（有关更多详细信息，请参阅前面的广度优先启发式搜索论文或关于最佳优先前沿搜索的这篇论文。）

希望这些要点能解决你的问题。如果你需要更多链接或澄清，我很乐意提供帮助。