使用A星优化N-Puzzle上的重复节点搜索(关闭列表，打开列表)

Question

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

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

如您所见，我正在使用带有 find_if 的 lambda 表达式来检查每个节点中的所有值。

我

想知道我是否遗漏了一些东西，或者是否有任何其他更有效的方法来解决此问题，或者这是应该完成的方式，而我的代码的其他部分有问题？

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((。