Frogs Game
3.96/5 (14投票s)
在本文中，我们将解释回溯算法，它是暴力搜索方法的一种改进。
引言
首先，我编写了一个玩青蛙游戏的程序。这是一个简单的游戏。左边有三只青蛙在叶子上，右边有三只青蛙在叶子上。游戏的目标是让左边的三只青蛙移动到右边，右边的三只青蛙移动到左边。
标有“L”的青蛙可以向前移动一个位置，或者跳过标有“R”的青蛙向前移动两个位置。标有“R”的青蛙可以向后移动一个位置，或者跳过标有“L”的青蛙向后移动两个位置。
编写玩游戏的程序很简单。我们只需要验证用户的移动，并检查他是否到达了目标。也有可能不再有任何移动，并且目标没有实现。在这种情况下，我们会通知用户并重置游戏。
当计算机解决游戏时，问题就开始了。计算机必须做出能够导向目标的移动。当它做出第一个移动时，不清楚这个移动是否会带来一个圆满的结局。计算机必须尝试情况下的所有可能性。如果移动导向目标，计算机必须记住这个移动以及到达这个移动的路径。如果移动导向一个不再有“合法”移动可能的情况，计算机必须放弃这个移动并选择另一个替代方案。
背景
解决这个问题的算法是标准的**回溯算法**，我们通过它来遍历树的节点。问题的解决方案通常在树的叶子节点上，或者（在我们的例子中）是到达叶子节点的路径。
让我们来看看我们的问题。我决定创建一个包含 7 个元素的表，索引从 0 到 6。起始位置是 LLL_RRR。每个元素都有它的位置、它的字母和新的可能位置。在起始位置，有两种可能的移动：“L 从 2 移动到 3”和“R 从 4 移动到 3”。我们可以决定在每一步中选择第一个可能性。所以我们选择移动“L 从 2 移动到 3”。新情况是 LL_LRRR。
现在我们也有两种可能性：“L 从 1 移动到 2”或“R 从 4 移动到 2”。我们选择第一种，新情况是 L_LLRRR。
第三步只有一个可能的移动：“L 从 0 移动到 1”。新情况是 _LLLRRR。
我们没有任何可能的移动了，也没有达到目标。所以我们必须回溯一步。我们必须恢复到旧的情况：L_LLRRR。在这种情况下，只有一个可能的移动，所以我们必须再回溯一步，恢复到情况：LL_LRRR。由于我们已经尝试了第一个可能性并且没有达到目标，所以我们选择另一个可能的移动：“R 从 4 移动到 2”。新情况是 LLRL_RR。
我们继续这个过程，直到我们达到目标，或者我们用完了所有可能的移动。
在图中，我们在最左边的层次可以看到前两种可能的移动。用红色前景色标记的是已执行的移动。用黑色背景色标记的是已执行但被取消的移动，因为它们没有导向目标。
在第一个移动“L 从 2 移动到 3”之后，我们看到移动“L 从 1 移动到 2”和“L 从 0 移动到 1”都没有导向游戏的终点。所以我们选择第二个替代移动“R 从 4 移动到 2”。在第三步，我们探索可能的移动“L 从 3 移动到 4”。由于这不是一个获胜的移动，我们必须选择移动“R 从 5 移动到 4”。我们继续这个过程，直到我们达到目标。我们还必须考虑到游戏可能无法解决。
Using the Code
为了解决这个问题，我编写了一个名为 TryThis 的方法。它是一个递归方法，所以它使用了一个边缘条件和一个递归调用。当可能移动数组中不再有元素时，就达到了边缘条件。
方法 TryThis 接收一个参数，该参数描述了步骤的数量（或树的深度 - 例如，“L 1 2”和“R 4 2”具有相同的步骤号）。
首先，我声明了一个 struct solutionData，它描述了解决方案的一个步骤。
public struct solutionDataa
{
public int oldIndex;
public int newIndex;
public char ch;
}
方法 TryThis 的代码如下
private bool TryThis(int i)
{
bool success = false;
//find all possible moves in a situation
ArrayList a = FindAll(s, i);
int last = a.Count;
int j = 0;
//lookup all possible moves
while (!success && last != j)
{
solutionData c = (solutionData)a[j];
writeMove(c);
if (TheEnd()) return true;
//recursive call
success = TryThis(i + 1);
if (!success)
{
//cancel the move
GoBack(i, c);
//try the next possible move
j++;
}
return success;
}
在方法 TryThis 中，我们调用了 FindAll 方法。使用这个方法，我们在一个“情况”下找到所有可能的移动，并将移动以 ArrayList 的形式返回。“情况”指的是 L 和 R 青蛙的不同位置（例如 L_LLRRR 或 _LLLRRR）。
private ArrayList FindAll(StringBuilder s, int k)
{
//finds all possible moves on level k
ArrayList a = new ArrayList();
solutionData b = new solutionData();
for (int i = 0; i < 7; i++)
{
if (i < 6)
if (s[i] == 'L' && s[i + 1] == ' ')
{
b.oldIndex = i;
b.newIndex = i + 1;
b.ch = 'L';
a.Add(b);
}
if (i < 5)
if (s[i] == 'L' && s[i + 1] == 'R' && s[i + 2] == ' ')
{
b.oldIndex = i;
b.newIndex = i + 2;
b.ch = 'L';
a.Add(b);
}
if (i > 0)
if (s[i] == 'R' && s[i - 1] == ' ')
{
b.oldIndex = i;
b.newIndex = i - 1;
b.ch = 'R';
a.Add(b);
}
if (i > 1)
if (s[i] == 'R' && s[i - 1] == 'L' && s[i - 2] == ' ')
{
b.oldIndex = i;
b.newIndex = i - 2;
b.ch = 'R';
a.Add(b);
}
}
return a;
}
我尝试了三种不同的方式来呈现解决方案。首先，我使用了一个 ListBox 来查看我的解决方案是否有效。然后我添加了一个 TreeView。在 TreeView 中，您可以看到计算机如何做出它的移动。最后，我添加了一个游戏模拟。
通过这个程序，您也可以玩这个游戏。为此目的（以及用于模拟），我决定创建一个名为 ATable 的 UserControl。该控件包含一个 TableLayoutPanel，其中包含标签（用于青蛙的位置）和七个按钮。这些按钮共享许多属性，所以我们将它们放在一个按钮表中。
Button[] frog = new Button[7];
每个按钮都用字母（L 或 R）初始化，并注册了一个名为 LegalMove 的事件处理程序。
EventHandler LegalMove;
public ATable()
{
.......
LegalMove = new EventHandler(MoveB);
for (int i = 0; i < 7; i++)
{
frog[i] = new Button();
.....
frog[i].Click += LegalMove;
tLP.Controls.Add(frog[i], i, 1);
}
}
方法 MoveB 将按钮向左或向右移动。为了验证移动是否合法，我使用了一个名为 situation 的 StringBuilder 变量。每次移动后，控件都会更改 situation 变量。
在程序中，我们还需要在用户进行移动时触发一个事件。因此，我添加了一个名为 NextM 的事件。
public delegate void Next(int position);
public event Next NextM;
事件的参数是移动的按钮的位置。每次点击按钮时都会触发该事件。
private void MoveB(object sender, EventArgs e)
{
if (((Button)sender).Text == "L")
MoveFromLeftToRight(situation, tLP.GetColumn((Button)sender));
else
MoveFromRightToLeft(situation, tLP.GetColumn((Button)sender));
if (NextM != null)
//fire the event
this.NextM(tLP.GetColumn((Button)sender));
}
在主窗体中，我放置了一个 ATable 类型的对象，然后我编写了事件处理程序。
private void aTable1_NextM(int position)
{
if (TheEnd())
MessageBox.Show("Congratulations! You won!",
"The end",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
else
if (NoMovePossible())
{
MessageBox.Show("No more moves are possible\n",
"The end",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
//reset game
aTable1.ResetSituation();
}
}
关注点
我们可以编写一个新的用户控件，用青蛙的图片代替按钮。程序应该可以通过稍作修改就能工作。
我的程序不搜索游戏的所有解决方案。当它找到第一个导向目标的移动序列时，它就结束了。您可以在 TreeView 中看到未被利用的移动。它们具有白色背景和黑色文本颜色。
使用相同的算法，我们可以解决其他问题，如国际象棋棋盘上的八皇后问题或迷宫搜索。
历史
- 2008 年 8 月 18 日：这是程序的第一个版本。它旨在学习一个基本的编程算法。顺便说一下，我们还学习了如何将新的用户控件与现有用户控件结合起来。