曼哈顿距离启发式的A *算法 [英] A* Algorithm with Manhattan Distance Heuristic

查看:199
本文介绍了曼哈顿距离启发式的A *算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我一直在用C语言开发一个15难题的求解器.我的代码使用的大量内存也有一些问题.

I've been working on a 15-puzzle solver in C. And I had some issues with the huge amounts of memory that my code uses.

我不会发布我的代码,因为它太长了……我已经实现了我正在使用的大多数库,这可能会给您带来混乱.让我们从基础开始.

I won't be posting my code because it's too long... I've implemented most of the libraries I'm using and it will probably just bring confusion to you. Let's start on the basics.

我现在正在使用的东西是:(所有这些都在C中实现)

The things that I'm using right now are: (All of them implemented in 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 .

The only thing I haven't implemented myself, I'm using uthash.

-15个拼图状态的代表

这是一个有趣的话题.在这里解释情况之前,让我们先来思考一下15难题的问题...众所周知,15难题有16个图块(重新将空白图块算作数字为0的图块).那么,有15个难题的状态有多少种呢?好吧,这是阶乘(16)状态.因此,这是很多州.这意味着我们希望我们的状态尽可能小...如果我们的初始状态离解决方案太远,我们可能会探究太多状态,以至于程序存储器会爆炸.

This is an interesting topic. Before explaining the situation here, let's just think a little bit about the 15-puzzle problem... As we know, 15-Puzzle has 16 tiles (We're counting the blank tile as the tile with the number 0). So, how many possible states has the 15-puzzle problem? Well, it's factorial(16) states. So, that's a lot of states. That means that we want our states to be as small as possible... If our initial state is too far away from the solution, we may explore so much states that our program memory will just explode.

所以...我的15难题表示法包括使用位和逻辑运算符:

So... my 15-puzzle representation consist of using bits and logical operators:

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

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

So what I'm doing is using logical operators to move and change the numbers, using the minimum space.

请注意,该结构的大小为 12字节(因为它具有三个整数)

Note that the size of this struct is 12 bytes (Because it has three integers)

-曼哈顿距离

这只是著名的曼哈顿距离启发式".基本计算每个数字当前位置到目标状态下数字位置的距离之和.

This is just the well known Manhattan Distance Heuristic. Where you basically calculate the sum of the distances of each number current position to the number position in the goal state.

-与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 that these nodes had nothing to do with the nodes in fibonacci heap.

现在是造成这个话题的主要原因...我正在使用的A *伪代码.

And now the main reason of this topic... The pseudocode of A* I'm currently using.

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

所以我无法回答的问题是...

So the questions I haven't been able to answer yet are...

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

我的意思是,如果您看一下伪代码.它不考虑重用状态或节点.它只是不断分配节点和状态,即使它们是先前计算过的也是如此.

I mean, If you take a look at the pseudocode. It's not considering re-using states or nodes. It just keeps allocating over and over nodes and states, even though they've been calculated before.

我一直在考虑很多问题...每次运行求解器时,它都能快速快速地扩展数百万个节点.并且我们知道,当您找到另一条成本低于前一条路径的路径时,A *可能会重新探索节点.这意味着...如果我们探索100万个节点,它将是2400万个字节(哇)...并且考虑到每个节点都有一个状态,即每个节点14个字节,即1,400万个字节.

I've been thinking a lot about this... Each time you run the solver, it can expand millions of nodes real quick. And as we know, A* may re-explore nodes when you find another path with a cost less than the previous one. That means... If we explore 1 million nodes, it will be 24 millions of bytes (Wow)... And considering that each node has a state, that would be 14 bytes per node, those are 14 millions of bytes...

最后,我需要的是一种重新使用/释放空间的方法,以使我的计算机在执行该求解器时不会崩溃.

In the end, What I need is a way of reusing/freeing space so my computer won't crash when I execute this solver.

(PD:很抱歉,很长的帖子)

(PD: Sorry for the long post)

推荐答案

您是为了做作业还是为了娱乐?

Are you doing this for an assignment or for fun?

如果是出于娱乐目的,请不要使用A *,而要使用IDA *. IDA *将更快,并且几乎不占用内存.此外,您可以使用额外的内存来构建更好的试探法,并获得更好的性能. (如果您使用Google模式数据库",则应该找到足够的信息.这些信息由Jonathan Schaeffer和Joe Culberson发明,但由Rich Korf和Ariel Felner进行了详尽的研究.)

If it's for fun, then don't use A*, use IDA*. IDA* will be faster and it uses almost no memory. Furthermore, you can use the extra memory to build better heuristics, and get even better performance. (You should find sufficient information if you google "pattern database". These were invented by Jonathan Schaeffer and Joe Culberson, but studied in significant detail by Rich Korf and Ariel Felner.)

IDA *有一些缺点,并非在每个领域都适用,但是对于滑动拼贴难题而言,它几乎是完美的.

IDA* has some drawbacks and doesn't work in every domain, but it is just about perfect for the sliding-tile puzzle.

另一种可能有用的算法是广度优先启发式搜索.本白皮书和其他论文讨论了如何避免完全存储关闭列表.

Another algorithm which could help is Breadth-First Heuristic Search. This and other papers discuss how you can avoid storing the closed list entirely.

基本上,很多聪明的人以前都已经解决了这个问题,并且已经发布了他们的方法/结果,以便您可以向他们学习.

Basically, a lot of smart people have tackled this problem before and they've published their methods/results so you can learn from them.

以下是一些改善A *的提示:

Here are some tips to improve your A*:

  • 我发现Fibonacci堆并没有太大的速度提高,因此您可能想使用更简单的数据结构. (尽管自从我上次尝试此方法以来,可用的实现可能有所改善.)

  • I have found that there isn't much of a speed gain from Fibonacci heaps, so you might want to use a simpler data structure. (Although available implementations might have improved since I tried this last.)

节点的f成本将以2的增量跳跃.因此,您可以对f成本进行存储,而不必担心在同一f成本层中对项目进行排序. FIFO队列实际上工作得很好.

The f-cost of a node will jump in increments of 2. Thus, you can bucket your f-costs and only worry about sorting items in the same f-cost layer. A FIFO queue actually works pretty well.

您可以在本文中使用这些想法. a>将15拼图表示转换为置换,整个表示将花费约43位.但是,扩展状态变得更加昂贵,因为必须转换为其他表示形式才能生成移动.

You can use the ideas in this paper to convert the 15-puzzle representation into a permutation, which will take about 43 bits for the full representation. But, it becomes more expensive to expand states because you have to convert into a different representation to generate moves.

避免完全使用禁止的运算符存储关闭列表. (请参阅先前的广度优先启发式搜索文件或有关最佳优先边界搜索的论文了解更多信息.)

Avoid storing the closed list entirely using forbidden operators. (See the previous Breadth-First Heuristic Search paper or this paper on Best-First Frontier search for more details.)

希望这些观点能解决您的问题.如果您需要它们,我们很乐意提供更多链接或说明.

Hopefully these points will address your issues. I'm happy to provide more links or clarification if you need them.

这篇关于曼哈顿距离启发式的A *算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆