A *算法与曼哈顿距离启发式算法

 

我一直在研究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-难题问题......我们知道，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;

所以我正在使用逻辑运算符来移动和更改数字，使用最小的空间。

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

- 曼哈顿距离

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

- 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;

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

而现在这个主题的主要原因是我目前使用的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个字节，这些是14百万字节。 。

最后，我需要的是重复使用/释放空间的方式，以便在执行此解算器时我的计算机不会崩溃。

（PD：很抱歉，很长的文章）

你是做这个任务还是为了好玩？

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

IDA *有一些缺点，并不适用于每个领域，但它仅仅是滑动拼图游戏的完美选择。

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

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

以下是一些提高您的A *的提示：

  • 我发现斐波那契堆没有太多的速度增益，所以你可能想要使用更简单的数据结构。 （尽管自从我最后一次尝试后，可用的实现可能会有所改进。）

  • 节点的f-成本将以2为增量跳跃。因此，您可以分摊f-成本，并只担心在相同的f-成本层中对项目进行排序。 一个先进先出队列实际上工作得很好

  • 您可以使用本文中的想法将15-谜题表示转换为置换，这将需要大约43位用于完整表示。 但是，扩展状态会变得更加昂贵，因为您必须转换为不同的表示才能生成移动。

  • 避免完全使用禁止的操作员存储关闭列表。 （参见以前的广度优先启发式搜索论文或关于最佳优先搜索者的本文搜索以了解更多细节。）

    • 希望这些观点能够解决您的问题。 如果您需要，我很乐意提供更多链接或说明。

    链接地址: http://www.djcxy.com/p/65569.html

    上一篇: A* Algorithm with Manhattan Distance Heuristic

    下一篇: Is Manhattan distance still an admissible heuristic in this modified n