使用 A-star 优化 N-Puzzle 上的重复节点搜索（封闭列表、开放列表）

Question

我编写了一个程序，使用 A* 算法来解决 N-Puzzle。该算法运行完美，但与针对同一问题使用相同算法的所有程序相比，它似乎要慢得多。我认为减慢我的代码的部分是检查新节点是否存在于打开和关闭列表中。本质上，我正在做的是检查特定节点的整个值数组，每个节点都存储在 Closed 和 Open 列表中。这是我认为导致速度下降的代码片段。

for(auto temp_Node:Neighbours(process))
        {
            auto pred = [temp_Node](Node* item)                         //lambda Expression for 'pred', custom comparator
            {
                bool value=true;
                for(int i=0;i<N;i++)
                    for(int j=0;j<N;j++)
                    {
                        if(item->Grid[i][j]!=temp_Node->Grid[i][j])
                        {
                            value=false;
                            break;
                        }
                    }
                if(item->g!=temp_Node->g)
                    value=false;
                return value;
            };
            if(find_if(begin(closed_list),end(closed_list), pred)==end(closed_list))
            {
                auto open_list_cpy=find_if(begin(open_list),end(open_list), pred);
                if(open_list_cpy==open_list.end())
                {
                    open_list.insert(temp_Node);
                }

如您所见，我将 lambda 表达式与 find_if 结合使用来检查每个节点中的所有值。

我想知道我是否遗漏了什么，或者是否有任何其他更有效的方法来解决这个问题，或者这是应该如何完成并且我的代码的其他部分有问题？

Answer 1

您可能希望使用网格保留 map 或 set 个节点以进行比较，而不是按顺序搜索所有节点：

struct GridLess {
    bool operator()(const Node *a,const Node *b) const
    {
        assert(a);
        assert(b);
        for(int i=0;i<N;i++)
        {
           for(int j=0;j<N;j++)
           {
               if(a->Grid[i][j]!=b->Grid[i][j])
               {
                   return a->Grid[i][j] < b->Grid[i][j];
               }
           }
        }
        return false;
    }
};


std::set<Node*,GridLess> closed_list;

现在您可以使用

if (closed_list.count(temp_Node)==0) {
    // No node in closed_list has the same grid as temp_node
}

这将时间复杂度从 O(n) 降低到 O(log(n))。

使用 A-star 优化 N-Puzzle 上的重复节点搜索（封闭列表、开放列表）

Optimizing Duplicate node search(Closed list,Open List) on N-Puzzle using A-star

algorithm

performance

c++11

optimization

a-star