대기열을 사용하는 비회원 백 트랙 : 메모리가 부족합니다.

Question

std::queue 컨테이너를 사용하여 backtracking 예제 프로그램을 구현하려고 시도했지만 C++ 11 언어로는 시도하지 않았습니다.

그러나 프로그램의 메모리가 부족한 알고리즘의 어딘가에 코딩 실수가 있습니다. 그 실수는 무엇입니까? 그들은 순환과 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