迷宫问题 n给出一个迷宫的地图,有一些格子中有障 碍,问从起点到终点的最短路径,并输出 所有的最短路径 ■回溯法解题思路 1、这个方向有路可走,我没走过,往 这个方向前进 2、是死胡同往回走回到上一个路口 3、重复第一步,直到找着出口
迷宫问题 ▪ 给出一个迷宫的地图，有一些格子中有障 碍，问从起点到终点的最短路径，并输出 所有的最短路径。 ▪ 回溯法解题思路 1、 这个方向有路可走，我没走过， 往 这个方向前进 2、 是死胡同,往回走,回到上一个路口 3、 重复第一步，直到找着出口
但是 ■回溯法的缺点暴露无遗: 搜索耗时极巨,无法忍受。 那么 我们可否提前判断我们前进的方向是 否可能得到最优解呢?如果可以的话 ,搜索效率岂不是能够提高了吗 答案就是: 剪枝!
但是 ▪ 回溯法的缺点暴露无遗： 搜索耗时极巨，无法忍受。 ▪ 那么 我们可否提前判断我们前进的方向是 否可能得到最优解呢？如果可以的话 ，搜索效率岂不是能够提高了吗 ▪ 答案就是： 剪枝！