A*和N-Puzzle优化

Question

我正在为N字谜写一个解算器(参见http://en.wikipedia.org/wiki/Fifteen_puzzle)。

现在我使用unordered_map来存储拼图板的散列值，并使用曼哈顿距离作为算法的启发式算法，这是一个简单的DFS。

所以我有

    auto pred = [](Node * lhs, Node * rhs){ return lhs->manhattanCost_ < rhs->manhattanCost_; };
    std::multiset<Node *, decltype(pred)> frontier(pred);
    std::vector<Node *> explored; // holds nodes we have already explored
    std::tr1::unordered_set<unsigned> frontierHashTable;
    std::tr1::unordered_set<unsigned> exploredHashTable;

这在n=2和n= 3的情况下非常有效。然而，对于n=4和更高的版本，它确实是时好时坏。(stl无法为新节点分配内存)

我还怀疑我在unordered_set中遇到了散列冲突

unsigned makeHash(const Node & pNode)
{
unsigned int b    = 378551;
unsigned int a    = 63689;
unsigned int hash = 0;

for(std::size_t i = 0; i < pNode.data_.size(); i++)
{
    hash = hash * a + pNode.data_[i];
    a    = a * b;
}

return hash;
}

16！=2×10^13 (可能的安排)

2^32 =4 x 10^9 ( 32位哈希中可能的哈希值)

我的问题是，我如何优化我的代码来解决n=4和n=5？我从这里知道http://kociemba.org/fifteen/fifteensolver.html

http://www.ic-net.or.jp/home/takaken/e/15pz/index.html

n=4在平均不到一秒的时间内是可能的。

编辑:算法本身在这里：

bool NPuzzle::aStarSearch()
 {
auto pred = [](Node * lhs, Node * rhs){ return lhs->manhattanCost_ < rhs->manhattanCost_; };
std::multiset<Node *, decltype(pred)> frontier(pred);
std::vector<Node *> explored; // holds nodes we have already explored
std::tr1::unordered_set<unsigned> frontierHashTable;
std::tr1::unordered_set<unsigned> exploredHashTable;

// if we are in the solved position in the first place, return true
if(initial_ == target_)
{
    current_ = initial_;
    return true;
}

frontier.insert(new Node(initial_)); // we are going to delete everything from the frontier later..

for(;;)
{
    if(frontier.empty())
    {
        std::cout << "depth first search " << "cant solve!" << std::endl;
        return false;
    }


    // remove a node from the frontier, and place it into the explored set
    Node * pLeaf = *frontier.begin();
    frontier.erase(frontier.begin());
    explored.push_back(pLeaf);

    // do the same for the hash table
    unsigned hashValue = makeHash(*pLeaf);
    frontierHashTable.erase(hashValue);
    exploredHashTable.insert(hashValue);

    std::vector<Node *> children = pLeaf->genChildren();
    for( auto it = children.begin(); it != children.end(); ++it)
    {
        unsigned childHash = makeHash(**it);
        if(inFrontierOrExplored(frontierHashTable, exploredHashTable, childHash))
        {
            delete *it;
        }
        else
        {
            if(**it == target_)
            {
                explored.push_back(*it);
                current_ = **it;

                // delete everything else in children
                for( auto it2 = ++it; it2 != children.end(); ++it2)
                    delete * it2;

                // delete everything in the frontier
                for( auto it = frontier.begin(); it != frontier.end(); ++it)
                    delete *it;

                // delete everything in explored
                explored_.swap(explored);
                for( auto it = explored.begin(); it != explored.end(); ++it)
                    delete *it;

                return true;
            }
            else
            {
                frontier.insert(*it);
                frontierHashTable.insert(childHash);
            }
        }
    }
}

}

Answer 1

因为这是家庭作业，所以我将建议一些你可以尝试的策略。

首先，尝试使用valgrind或类似的工具来检查内存泄漏。如果你不删除所有新的东西，你可能会有一些内存泄漏。

其次，计算应该探索的节点数量的界限。跟踪您所探索的节点的数量。如果您通过了限制，您可能无法正确检测周期。

第三，尝试使用深度优先搜索而不是A*的算法。它的内存需求在树的深度上应该是线性的，这应该只是改变排序顺序(pred)的问题。如果DFS工作，您的A*搜索可能正在探索过多的节点，或者您的内存结构可能效率太低。如果DFS不工作，这可能又是周期的问题。

第四，尝试更紧凑的内存结构。例如，std::multiset可以执行您想要的操作，但是带有std::deque的std::priority_queue可能占用较少的内存。你还可以尝试其他的改变，看看它们是否能改善事情。

Answer 2

首先，我推荐cantor expansion，您可以使用它作为散列方法。这是1比1，也就是16！可能的排列将被散列到0 ~ 16！- 1中。

然后我会自己实现map，正如你可能知道的，std对于计算来说效率不够高。map实际上是一个Binary Search Tree，我建议您使用Size Balanced Tree，或者您也可以使用AVL tree。

仅供记录，直接使用bool hash[]和big prime也可能收到良好的结果。

然后是最重要的- A* function，就像你的第一个链接中的东西，你可以尝试各种A* function并找到最好的。

Answer 3

您只需使用启发式函数来对多集进行排序。你应该使用min(g(n) + f(n))，即min(路径长度+启发式)来排序你的边界。

这里的问题是，你选择了启发式最少的一个，这可能不是正确的“下一个孩子”。

我相信这就是导致你的计算爆炸的原因。