キューを使用した非再帰バックトラック：メモリ不足

Question

std::queueコンテナをC++ 11の方言で使用してbacktrackingサンプルプログラムを実装しようとしました。

ただし、アルゴリズムのどこかにコードミスがあり、プログラムのメモリが不足します。そのミスは何ですか？以下のサンプルコードで

それらが再帰とstd::stack容器implementations of backtrackingで正常にテストされているので、機能reject()、accept()、first_child()とnext_child()は、正常に動作すると仮定することができます。

// helper functions 
bool reject(const std::string &c); 
bool accept(const std::string &c); 
const std::string * first_child(const std::string &c); // nullptr == no child 
const std::string * next_child(const std::string &c); // nullptr == no child 

void backtrack_que(const std::string &start) 
try 
{ 
    std::queue<std::string> que; 

    que.push(start); 

    while (!que.empty()) 
    { 
     if (reject(que.front())) 
     { 
      que.pop(); 
      continue; 
     } 

     if (accept(que.front())) 
      std::cout << que.front() << '\n'; 

     const std::string *p_child(first_child(que.front())); 

     que.pop(); 

     if (p_child != nullptr) 
     { 
      que.push(*p_child); 

      const std::string *p_sibling(next_child(que.back())); 

      while (p_sibling != nullptr) 
      { 
       que.push(*p_sibling); 
       p_sibling = next_child(que.back()); 
      } 
     } 
    } 
} 
catch (...) 
{ 
    std::cerr << "unknown exception in `" << __func__ << '`' << std::endl; 
    throw; 
} 

Answer 1

私は、単純なカウンティングテストを行い、@IgorTandetnikがキューバリアントに関する正確であったことを発見した：それは60+百万最大サイズに達しました。私には驚くべきことに

、スタックバリアントは、私はこれが原因スタックバリアントはキューバリアントが蓄積しながら、可能な子を最後に「突入」どのようにあると結論付けたコードを再訪時に200を超えることはできませんでした次の世代に進む前に多くの子供たちがいます。よりコンピュータ規模の用語では、スタックはDepth-First Searchです。キューはBreadth-First Searchです。

また、驚くべきことに、伝統的なの再帰的なの亜種が、最も効率的で最も速いと思われることも明らかです。

max recursion depth for bt-rec: 6 
max container size for bt-stk: 176 
max container size for bt-que: 60466176