如何解决在c++中有许多不同层次的问题(它们是递归的)。

Question

我想知道如何处理问题，在c中有一个进程在许多不同的问题“层次”中使用，最好是以一种“惯用”的方式。我知道我没有很好地解释这一点，所以让我举一个例子：

考虑制作游戏解算器的一般问题，它应该打印出最好的下一步棋。我认为它应该检查for循环中的所有可能的棋，看看它是否是(在这一轮中)获胜的棋，如果是，则返回这步棋，否则检查对手可以与你的棋(for循环)进行的每一步棋，并调用函数再次找到最好的棋。

然而，我发现这种方法有一些局限性，比如性能(程序将花费时间运行调用函数等所需的样板代码)和有限的灵活性，因为函数将必须找到一种方法来与调用者沟通found.That是多么好的一步，如果可以做到的话。

bestmove()
{
  for (;i<maxmove;i++)
   {
    if(checkifwinning(moves[i])) return;
    for (;n<maxopponentmove;n++)
     {
      bestmove();
     }
   }

我和haskell打交道已经有一段时间了，所以我担心我的注意力集中在寻求递归解决方案上。我希望你能教我一种用“c原生”的方式来编写这个函数的方法。

Answer 1

您正在讨论搜索博弈树以找到最佳走法；您可以使用像minimax这样的标准算法。您的方法似乎是深度优先搜索树，在发现的第一个获胜走法时终止；请注意，这不会找到通往获胜走法的最短路径，也不会阻止对手的胜利。

有一些方法可以加快游戏树的搜索速度，比如alpha-beta pruning。这样的标准算法是可行的--比担心在C等语言中调用函数的开销要好得多。C函数调用并不昂贵。在编写C代码时要注意这种“优化”--不管怎样，优化器在这类事情上可能会做得更好。至少，首先以最直接的方式编写一个版本，这样您就有了基准测试。你的工作就是找到一个好的算法。

Answer 2

C语言允许使用递归函数。然而，它没有尾递归调用的概念(但在某些情况下，最近的GCC编译器能够将一些尾递归调用优化为纯粹的迭代机器码)。

在编写递归函数时，应该避免过深的递归和过大的本地调用帧(所以使用堆内存)。

Answer 3

我认为你真正需要的是一个类似branch-and-bound的算法:保存一个“开放”移动列表(即，尚未考虑)和一个“关闭”移动列表(即，已经考虑)。在C语言中，最好使用两个队列(打开和关闭)来实现。然后你就会有一个如下的算法：

while (open is not empty)
{
   pop gameState from open
   if (gameState in closed)
      continue;
   push gameState to closed
   for (eachMove)
   {
       computeNewState();
       addStateToOpen();
   }
}

与递归方法相比，这种方法有几个优点：

• 你确信每个游戏状态只会被考虑一次
• 你不会“压倒”堆栈