10 用广度优先搜索去开锁（第4/4页）

在这个具体的例子中，我们在H城市找到了要找的罪犯。至此我们可以在H城市逮捕他，结束搜索。

在搜索问题中，如果任意相邻的两个点之间移动的代价（例如所需的时间、体力，等等）是相等的，那么广度优先搜索可以保证找到一条花费最小代价的路径。这是因为它在检查完所有离起点距离X步的点后，才会开始检查那些更远的，例如离起点距离X+1步的点。

如果对于每个点都记下它是由哪一个点走来的，我们就可以很容易地追溯到这条最短路径。我们只要从终点开始，不断地回溯到它之前的一个点，直到回到起点就好了。

不过，值得注意的是，广度优先搜索只有在相邻点之间移动的代价都一样时才会给出最优的方案。一般来说，找出两点之间步数最少的路径和找出两点之间代价最小的路径是不一样的。举个例子，如果一群远足者想要尽量节省体力的话，他们宁愿会走一条相对较长但可以避开山路的路，即使穿山而过可能会使整个路程更短，也会更有观光价值，但走这段山路无疑会耗费更多的体力。