递归回溯算法无法解决某些情况

Question

我正在编写一个递归算法来解决弹球纪游戏。

该算法需要使用“回溯”方法来解决问题。我认为我已经成功地找到了一个非常接近正确解的方案。据看，我的代码可以正确地解决所有可解的棋盘问题。它也似乎可以正确地确定何时棋盘是不可解的，但仅当钉子数量不太高时才行。

我的递归方法如下：

public static void solve()
{
    if(isSolved())
    {
        long endTime=System.currentTimeMillis();
        System.out.println("Solved");
        solved=true;
        printArr(board);

    }
    else
    {
            for(int i=0;i<7;i++)
            {
                for(int j=0;j<7;j++)
                {
                    for (int k=0;k<4;k++)
                    {
                        if(makeMove(new int[]{i,j,k}))
                        {
                            if(solved!=true)
                            {
                                solve();
                                undoMove();
                            }
                        }


                    }
                }
            }
        }
    }

该棋盘是标准的Peg Solitaire棋盘。我有信心我的isSolved()方法能够正确地确定棋盘是否已被解决。我的makeMove函数接受行、列和方向（i、j和k）。它找到这些坐标处的木棒，并检查它是否可以朝请求的方向移动。

如果可以，它会进行移动，将其添加到移动数组中，并返回true。 如果不能，它会返回false。

我的撤销方法弹出最后一个移动并将棋盘恢复到之前的布局（在执行弹出的移动之前）。

似乎对于大约25个以上木棒的随机棋盘，程序根本不会终止。它会无限期地继续处理。 有解的棋盘和带有较少木棒的各种无解棋盘似乎在10秒内始终以正确的结果终止。

有任何想法吗？

- Josh

---

你的算法是否可能只是需要很长时间，或者执行了两个不改变游戏状态的移动？比如将卡牌A移动到堆栈B，然后又将其移回来？ - MrHug

@MrHug 该算法在技术上尝试着找到每一种通往解决方案的“路径”，直到找到其中一条，或者某个“路径”到达了一个无解的棋盘，此时递归方法调用序列终止，并调用undoMove()。然后从棋盘上下一个可用点重新开始重复这个过程，因此我看不出它会卡住的可能性。 - Josh

@KurtDuBois，我尝试过类似的方法，但是由于棋盘继续改变（实际上，在我的所有可解决的棋盘中，经常需要进行300,000多次undoMove调用才能到达解决方案，因此很难识别无限循环），所以记录似乎毫无用处。 - Josh

你能展示一下你的完整代码吗？对于一个774的棋盘大小，尝试每种排列方式的数量是(7*7*4)!，这个数量非常巨大。 - Pham Trung

@PhamTrung 经过更深入的思考，我认为你可能是正确的。这意味着算法没有问题，只是运行时间太长了。 - Josh

Answer 1

由于在Peg Solitaire中的每一步都会移除一个棋子，因此你不可能回到先前的状态：就像简单路径规划中，机器人可能会永远在两个方格之间来回移动。所以这不是问题所在。

那么你的算法错了吗？这里是简化后的算法：

solve (board state) is

if the board is solved, record success
else
   for all possible moves from this board state
      if move is possible
        make it
        call solve
        undo the move

这个算法不可能陷入循环；当它递归时，它会深入搜索空间（也就是说，它会进行一次移动）。所以问题不在这里。

你可能在一些没有展示的函数中出现了错误（比如make move和undo move）。如果make move没有做任何事情，无论问题的规模如何，你的程序都不会结束。

因此，我得出结论，问题在于一个非常大的搜索问题可能需要很长时间。你可以尝试调整问题的规模。如果它可以解决大小为N的问题，那么它是否可以解决大小为N+1的问题？花费几秒钟来解决一个大小为N的问题表明，你可以忘记让它解决N+10的问题（基于我类似问题的经验）：不仅因为这是一个指数问题，而且因为系统可能会尝试获取足够的内存而导致抖动。

有时候解决方案是跟踪你已经尝试过的节点，以减少冗余搜索。我怀疑你在这个问题上得不到太多帮助——你不能保留已访问状态的列表（这将需要指数级的内存），并且仅为前几个级别保留已访问状态的列表不会扩展你可以搜索的深度太多。

这一切都是为了别人得出的结论而付出的努力：它只是一个大问题。

- Topological Sort