Нерекурсивный Backtrack с использованием очереди: заканчивается память

Я попытался реализовать примерную программу backtracking с помощью контейнера на диалекте C++ 11.Нерекурсивный Backtrack с использованием очереди: заканчивается память

Однако в алгоритме есть ошибка кодирования, из-за чего программа заканчивается из памяти. Что это за ошибка?

В примере кода ниже, функции reject(), accept(), first_child() и next_child() можно предположить, чтобы работать правильно, так как они были успешно испытаны с рекурсивной и std::stack контейнера implementations 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; 
}

источник

2017-01-05 user7023624

Для каждой строки, которую вы поп, вы добавляете 36 длинных строк. Если вы начинаете с пустой строки, в итоге вы получите около 36^5 = 60 + миллион строк, что по приблизительной оценке займет 1 ГБ ОЗУ. Если вы начинаете с строки длиной более 5 символов, ваш цикл никогда не останавливается вообще. –

@IgorTandetnik Благодарим вас за обнаружение ошибки 'length> 5' в' first_child() '. Что касается ошибки из-за памяти, я с трудом понимаю, почему это не происходит, когда используется 'std :: stack'. – user7023624

У версии стека такая же проблема, насколько я могу судить. Я предполагаю, что 'std :: stack' использует' std :: vector' под ним, тогда как 'std :: queue' использует' std :: deque'. Последний имеет несколько более высокие накладные расходы для каждого элемента. Таким образом, ваши строки 60 + M просто укладываются в ОЗУ со стеком, но заканчиваются с очередью. –

я выполнил простой тест подсчета и обнаружил, что @IgorTandetnik был точен в отношении очереди варианта: он достиг 60+ миллионов максимального размера.

Удивительно для меня, Stack вариант не превышает 200. После пересмотра кода я сделал вывод, что это происходит из-за того, как Stack вариант «носится» до последнего возможного ребенка в то время как вариантные накапливает очереди большое количество детей, прежде чем перейти к следующему поколению: в более сложных вычислительных терминах, Стек делает 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

источник

2017-01-07 09:04:39 user7023624

Нерекурсивный Backtrack с использованием очереди: заканчивается память

ответ

Смежные вопросы