我如何使這個算法更有效率的內存？

Question

我一直在研究這段代碼幾天，似乎 適用於相對較小規模的搜索樹，但使用較高的搜索樹會導致分段錯誤。

我試圖尋找到這樣的錯誤來自使用印刷標誌的具體位置，而且似乎在is_goal（）函數來打破。但是該函數的代碼可以假定爲正確的。

所以，問題似乎是內存的問題，這就是爲什麼我在堆的隊列，也是我創造的節點。但它仍然崩潰。

有沒有更多的內存節省技巧，可以考慮到我不使用？或者也許有更好的方法來保存這樣的節點？

重要的是要注意，我需要使用BFS（我不能使用A *，使搜索樹小）是非常重要的。

此外，如果您需要知道，映射是一個散列表，我保存節點的着色，所以我沒有探索時重複（這是因爲散列保存取決於狀態信息，而不是節點信息）。編輯：我已被告知表明要完成的目標，例如在搜索樹中找到目標狀態，目標是能夠重複執行 大問題，如rubik 3x3x3，n-puzzle 4x4 5x5，河內塔等等。爲此，使用的內存必須最小化，因爲這些問題的搜索樹非常大，最終目標是將此算法與其他類似的算法比較，如*，dfid，ida *和等等。我希望這是足夠的信息。

Node* BFS(state_t start){ 

    state_t state, child; 
    int d, ruleid; 
    state_map_t *map = new_state_map(); 
    ruleid_iterator_t iter; 
    std::queue<Node*> *open = new std::queue<Node*>(); 

    state_map_add(map, &start, 1); 

    Node* n = new Node(start); 
    open->push(n); 

    while(!open->empty()) { 
     n = open->front(); 
     state = n->get_state(); 
     open->pop(); 

     if (is_goal(&state) == 1) return n; 

     init_fwd_iter(&iter, &state); 

     while((ruleid = next_ruleid(&iter)) >= 0) { 
      apply_fwd_rule(ruleid, &state, &child); 


      const int *old_child_c = state_map_get(map, &child); 
      if (old_child_c == NULL) { 
       state_map_add(map, &child, 1); 
       Node* nchild = new Node(child); 
       open->push(nchild); 
      } 

     } 

    } 

    return NULL; 
} 

Answer 1

我看到一些內存泄漏。

開放永遠不會被刪除，但可能可以分配在堆棧而不是在堆中。

std::queue<Node*> open; 

您在隊列中刪除此推送的節點更重要的是沒有可能是非常大的內存消耗的起源。

刪除您從隊列中刪除並且您不打算重複使用的節點。在排除隊列之前刪除隊列的節點。

Node* BFS(state_t start){ 

    state_t state, child; 
    int d, ruleid; 
    state_map_t *map = new_state_map(); 
    ruleid_iterator_t iter; 
    std::queue<Node*> open; 

    state_map_add(map, &start, 1); 

    Node* n = new Node(start); 
    open.push(n); 

    while(!open.empty()) { 
     n = open.front(); 
     state = n->get_state(); 
     open.pop(); 

     if (is_goal(&state) == 1) { 
      for (std::queue<Node*>::iterator it = open.begin(); it != open.end(); ++it) 
       delete *it; 

      return n; 
     } 
     else { 
      delete n; 
     } 

     init_fwd_iter(&iter, &state); 

     while((ruleid = next_ruleid(&iter)) >= 0) { 
      apply_fwd_rule(ruleid, &state, &child); 


      const int *old_child_c = state_map_get(map, &child); 
      if (old_child_c == NULL) { 
       state_map_add(map, &child, 1); 
       Node* nchild = new Node(child); 
       open.push(nchild); 
      } 

     } 

    } 

    return NULL; 
}