回溯方法简介与示例

回溯是基于基于是/否决策的问题的问题解决技术。在这里，您正在做一个决定，如果由于错误的决定而遇到无法接受的结果，您将返回错误的决定，并尝试做出不同的决定。

通常，回溯解决方案会伴随递归。因此，有时会使我们难以理解解决方案。在本章的最后，我们将看一个简单的编码示例。

了解回溯的最佳示例是“迷宫中的球”问题。

问题陈述如下：

迷宫的起点将放置一个球；您的工作是移动球，使其到达迷宫的尽头。

下图是

从上面的图像中，我们可以看到球可以向左，向右，向下移动。通过使用这3个操作，您需要使球到达终点。

在这里，您将做出一系列决策以使球到达终点。在某些时候，您可能会走到尽头，然后回溯到可以做出不同决定的地步。因此，这称为回溯。

让我们从理论上解决问题：

球将从方块1开始，必须通过做出一系列基于“是”，“否”的决定来到达方块9。

让我们先走这条路

1-> 2 -> 3

然后它将下降到“ 6”并继续前进

1-> 2 -> 3 -> 6 -> 5 -> 4

因为4是结束，它将转到7

1-> 2 -> 3 -> 6 -> 5 -> 4 -> 7

现在为“ 7”时，它无处可去。因此，您需要回溯到4，然后回溯到5。

1-> 2 -> 3 -> 6 -> 5 -> 8 -> 9

如您所见，我们对如何遍历做出了许多决定。回溯基于蛮力方法。您将继续操作，直到达到预期结果以外的程度。然后，您返回到具有可接受结果的位置，然后做出其他决定。

现在让我们看一下迷宫问题中球的编码部分。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：