Backtrack non récursif utilisant la file d'attente: manque de mémoire

J'ai essayé d'implémenter un programme d'exemple backtracking en utilisant un conteneur std::queue, dans le dialecte C++ 11. Cependant, il existe une erreur de codage quelque part dans l'algorithme qui provoque l'épuisement du programme. Quelle est cette erreur?Backtrack non récursif utilisant la file d'attente: manque de mémoire

Dans l'exemple de code ci-dessous, les fonctions reject(), accept(), first_child() et next_child() peuvent être supposés fonctionner correctement, parce qu'ils ont été testés avec succès avec le récipient récursive et std::stackimplementations of backtracking.

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

Source

2017-01-05 user7023624

Pour chaque chaîne, vous ajoutez 36 chaînes plus longues. Si vous commencez par une chaîne vide, vous obtiendrez 36^5 = 60 + millions de chaînes dans la file d'attente, ce qui, selon une estimation approximative, nécessiterait plus de 1 Go de RAM. Si vous commencez avec une chaîne de plus de 5 caractères, votre boucle ne s'arrête jamais du tout. –

@IgorTandetnik Merci d'avoir repéré le bug 'longueur> 5' dans' first_child() '. En ce qui concerne le bug de mémoire insuffisante, j'ai de la difficulté à comprendre pourquoi cela ne se produit pas lorsque 'std :: stack' est utilisé. – user7023624

La version de la pile a le même problème, autant que je sache. Je suppose que 'std :: stack' utilise' std :: vector' en dessous alors que 'std :: queue' utilise' std :: deque'. Ce dernier a des frais généraux un peu plus élevés par élément. Ainsi, vos chaînes 60 + M parviennent juste à s'intégrer dans la RAM avec la pile, mais sont épuisées avec la file d'attente. –

J'ai effectué un test simple de comptage et a constaté que @IgorTandetnik était exacte au sujet de la file d'attente variante: il a atteint plus de 60 millions de taille maximale.

Étonnamment pour moi, le Stack variante ne dépasse pas 200. À revisiter le code, je conclus que cela est dû à la façon dont la Stack variante « se précipite » pour le dernier enfant possible alors que les files d'attente accumule variantes un grand nombre d'enfants avant d'aller plus loin à la prochaine génération: en termes d'informatique-sciency, Stack fait Depth-First Search tandis que File d'attente fait Breadth-First Search.

Également surprenant était que, apparemment, le traditionnel Recursive variante semble être le plus efficace et aussi le plus rapide.

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

Source

2017-01-07 09:04:39 user7023624

Backtrack non récursif utilisant la file d'attente: manque de mémoire

Répondre

Questions connexes