使用回溯的随机遍历 N * M 网格的复杂性

Question

我制作了一个算法，使用回溯计算 N*M 网格中的随机路径。它从 [N/2][0] 开始，并应在 [N/2][M - 1] 结束。每次迭代他都选择一个随机方向(左、右、前)并继续递归。选定的方向保存在内存中，这样每个节点就不会使用相同的方向两次。当节点遇到一个已使用的节点或网格的边界并且每个方向都经过测试时，它会拉回堆栈。

它工作得很好，但我想知道如何根据网格的大小计算问题的复杂性。

很抱歉我的英语不好，如果我忘了说什么，请问我你需要的信息。

非常感谢!

Answer 1

我觉得你不能在这里谈论确定性运行时间，因为理论上，一旦陷入循环(例如，你遇到一个你已经访问过的节点)，随机数可能会永远返回相同的方向(尽管发生这种情况的可能性很小)。换句话说，您描述的是我们所说的 randomized algorithm。 (大致上任何使用随机位来指导其执行的算法；这意味着运行时间是一个随机变量)。

相反，您可以谈论 expected running time ，即算法返回随机路径前的预期操作次数。

请考虑为算法提供工作代码，以便我们给出更具体的答案。