4

我目前正在编写一个递归算法来解决 Peg Solitaire 游戏。

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

我的递归方法如下所示：

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。

我的 undo 方法从数组中弹出最后一个动作，并将棋盘恢复到以前的布局（在弹出动作之前）。

似乎对于大约 25 个或更多钉子的随机板，程序根本不会终止。它无限期地继续处理。可解板和具有较少钉子的各种不可解板似乎始终会在 10 秒内以正确的结果终止。

有任何想法吗？

4

1 回答 1

0

由于 peg solitaire 中的每一次移动都会移除一个 peg，因此您不可能循环回到以前的状态：例如，在简单的路径规划中，机器人可能永远在两个方格之间来回移动。所以不是这样。

那么你的算法错了吗？为了简单起见，这里是简化的：

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 没有做任何事情，无论问题的大小如何，您的程序都不会结束。

我会得出结论，问题是一个非常大的搜索问题可能需要很长时间。你可以玩问题的大小。如果它适用于大小为 N 的问题，它是否适用于大小为 N+1 的问题之一？花几秒钟来解决一个大小为 N 的问题表明你可以忘记让它解决 N+10 （我说，基于类似问题的经验）：不仅因为它是一个指数问题，而且因为你可能会因为系统试图获得足够的内存。

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

这一切都有助于其他人得出的结论：这只是一个大问题。

于 2014-11-12T15:54:39.057 回答