我一直在用 C 语言开发一个 15 个谜题求解器。我的代码使用的大量内存给我带来了一些问题。
我不会发布我的代码，因为它太长了......我已经实现了我正在使用的大部分库，它可能会给您带来困惑。让我们从基础开始。
我现在正在使用的东西是：（全部用C实现）
- 斐波那契堆：
/* Struct for the Fibonacci Heap */
typedef struct _fiboheap {
int size; // Number of nodes in the heap
node min; // Pointer to the minimun element in the Heap
funCompare compare; // Function to compare within nodes in the heap
freeFunction freeFun;// Function for freeing nodes in the heap
} *fiboheap;
/* Struct of a Fibonacci Heap Node */
typedef struct _node {
node parent; // Pointer to the node parent
node child; // Pointer to the child node
node left; // Pointer to the right sibling
node right; // Pointer to the left sibling
int degree; // Degree of the node
int mark; // Mark
void *key; // Value of the node (Here is the element)
} *node;
- 哈希表
我自己唯一没有实现的是，我正在使用uthash.
- 15 个谜题状态表示
这是一个有趣的话题。在解释这里的情况之前，让我们先思考一下 15-Puzzle 问题...众所周知，15-Puzzle 有 16 个图块（我们将空白图块视为数字 0 的图块）。那么，15 题问题有多少种可能的状态呢？嗯，这是阶乘（16）状态。所以，有很多州。这意味着我们希望我们的状态尽可能小......如果我们的初始状态离解决方案太远，我们可能会探索太多的状态，以至于我们的程序内存将会爆炸。
所以...我的 15 个谜题表示由使用位和逻辑运算符组成：
/* Struct for the 15-puzzle States Representation */
typedef struct _state {
unsigned int quad_1; /* This int represent the first 8 numbers */
unsigned int quad_2; /* This int represent the last 8 numbers */
unsigned short zero; /* This is the position of the zero */
} *state;
所以我正在做的是使用逻辑运算符来移动和更改数字，使用最小的空间。
Note该结构的大小是12 bytes（因为它有三个整数）
- 曼哈顿距离
这就是众所周知的曼哈顿距离启发式。您基本上可以在其中计算每个数字当前位置到目标状态中的数字位置的距离总和。
- A* 实现和与 A* 一起使用的节点结构
让我们从节点开始。
typedef struct nodo_struct {
nodo parent; // Pointer to the parent of the node
state estado; // State associated with the node
unsigned int g : 8; // Cost of the node
action a; // Action by which we arrived to this node
// If null, it means that this is the initial node
} *nodo;
Note这些节点与斐波那契堆中的节点无关。
现在这个主题的主要原因...我当前正在使用的 A* 的伪代码。
a_star(state initial_state) {
q = new_fibo_heap; // Sorted by (Cost g) + (Manhattan Distance)
// It will have nodes which contain a pointer to the state
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))) {
/* The dist used above is stored in the hash table as well */
closed.insert(n->state);
dist(n->state) = n->g; // Update the hash table
if (is_goal(n->state)) {
return extract_solution(n); // Go through parents, return the path
}
for <a,s> ∈ successors(n->state) {
// 'a' is the action, It can be 'l', 'r', 'u', 'd'
// 's' is the state that is a successor of n
if (manhattan(s) < Infinity) {
q.push(make_node(n,a,s));
// Assuming that manhattan is safe
}
}
}
}
return NULL;
}
所以我还无法回答的问题是......
如何有效地管理内存？可以重用状态或节点吗？这会带来什么后果？
我的意思是，如果你看一下伪代码。它不考虑重用状态或节点。它只是不断地分配节点和状态，即使它们之前已经被计算过。
我一直在思考这个问题......每次运行求解器时，它都可以快速扩展数百万个节点。正如我们所知，当您找到另一条路径的成本低于前一条路径时，A* 可能会重新探索节点。这意味着...如果我们探索 100 万个节点，这将是 2400 万个字节（哇）...考虑到每个节点都有一个状态，每个节点将有 14 个字节，即 1400 万个字节。 。
最后，我需要的是一种重用/释放空间的方法，这样我的计算机在执行这个解算器时就不会崩溃。
（PD：很抱歉这篇文章很长）
