A *和N - 益智優化

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和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×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 :: priority_queue與std :: deque可能會佔用更少的內存。還有其他更改可以嘗試，看看他們是否改善了事情。

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（路徑長度+啓發式）來訂購您的邊界。

這裏的問題是，你選擇的試探最少的一個，這可能不是正確的「下一個孩子」選擇。

我相信這是什麼導致你的計算爆炸。