在实践中搜索：从A到B

想象一下你在一个外国的城市，在某个地方（比如一家酒店），想用公共交通工具去另一个地方（比如一家不错的餐馆）。你是做什么？如果你会像许多人一样，掏出智能手机，输入目的地并开始按照说明操作。

在这里，我们不会去关注实际的搜索算法。相反，我们强调问题解决过程的第一阶段:定义选择及其结果，这往往远非小事，需要仔细思考。我们还需要确定我们的目标是什么，换句话说，我们何时可以解决问题。完成这些后，我们可以查找从初始状态到目标的操作序列。

在本章中，我们将讨论两种问题：

• 在静态环境中搜索和规划只有一个“代理”。


• 俩个玩家（“代理”）相互竞争

这两类并不涵盖所有可能的现实场景，但它们是通用的，足以演示主要的概念和技术。

在处理像导航或下棋这样的复杂搜索任务之前，让我们从一个简化的模型开始，以增强我们对如何通过AI解决问题的理解。

鸡过河问题

我们将从一个简单的问题开始，以阐明这种思路。一艘划艇上的机器人需要将三件货物运过河：一只狐狸，一只鸡和一袋鸡饲料。如果有机会，狐狸就会吃这只鸡，如果有机会，鸡也会吃饲料，两者都不是我们想要的结果。机器人在动物附近时，可以保证它们不吃，但也只有机器人可以操作划艇，并且皮艇最多只允许两件货物与机器人一起过河。机器人如何将其所有货物安全的移至河对岸？

我们通过标出五个可移动的物体来模拟这个难题：机器人、划艇、狐狸、鸡和鸡饲料。原则上，这五个中的每一个都可以出现在河的任一侧，但是由于只有机器人可以操纵划艇，所以两者将始终在同一侧。因此有四种物体，每种物体有两种可能的位置，即16种组合，我们称之为状态：

鸡过河谜题的状态

我们给各状态写了简短的标识，否则确定属于哪个状态时会很麻烦。现在我们可以说，起始状态是NNNN，目标状态是FFFF，而不是说“在起始状态中，机器人在近侧，狐狸在近侧，鸡在近侧，并且鸡饲料在近侧，而在目标状态下，机器人在远侧“，等等。

这些状态中某一些是谜题条件禁止出现的。例如，在NFFN状态（意思是机器人和鸡饲料在近侧，但狐狸和鸡在远侧），狐狸会吃掉鸡。因此，我们可以排除NFFN，NFFF，FNNF，FNNN，NNFF和FFNN（如果你有所怀疑，可以自行检查）。我们留下以下十个状态：

我们现在已经为这个谜题上做了很多的工作，没有看到更接近解决方案的情况，毫无疑问，通过自己动脑，你已经可以解决这个谜题。但是对于更复杂的问题，可能的解决方案数量成千上万倍的增长，我们的系统或机械方法将会起到效果，因为困难的部分适合于简单的计算机。现在我们已经制定了它们之间的状态更替和转换，剩余的部分成为了一个机械任务：找到一条从初始状态NNNN最终状态FFFF的路径。

在下面的图片中染色的路径。首先从NNNN到FFFN（机器人将狐狸和鸡带到另一边），然后再到NFNN（机器人将鸡带回起始侧），最后到FFFF（机器人将鸡和饲料带到另一边）。

状态空间，转换和成本

为了规则化规划问题，我们使用诸如状态空间（State space），转换（transitions）和成本（costs，也译为代价）等概念。