我尝试使用 std::queue
容器以 C++11 方言实现回溯示例程序。
但是,算法中某处存在编码错误,导致程序内存不足。这个错误是什么?
在下面的代码示例中,可以假定函数 reject()
、 accept()
、 first_child()
和 next_child()
正常工作,因为它们已经通过递归和回溯的std::stack
容器实现成功进行了测试。
// 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;
}
我进行了一个简单的计数测试,发现@IgorTandetnik队列变体是准确的:它达到了 60+ 百万最大大小。
令我惊讶的是,Stack 变体不超过 200。在重新访问代码时,我得出结论,这是由于 Stack 变体如何"冲向"最后一个可能的子级,而队列变体在进一步进入下一代之前积累了大量子级:在更多的计算机科学术语中,Stack 进行深度优先搜索,而队列进行广度优先搜索。
同样令人惊讶的是,显然,传统的递归变体似乎是最有效的,也是最快的。
max recursion depth for bt-rec: 6
max container size for bt-stk: 176
max container size for bt-que: 60466176