迷宫问题

迷宫问题总结:

这三点贯穿所有迷宫问题,包括其变形问题

考虑一个简单的问题,从该迷宫中的起点走到终点.只需简单的查看是否碰到了墙,如果碰到了就换个方向走,同时要求不能往已经来过的方向走.

而这种不再去搜索一些明显不对的方向,在搜索算法里叫做剪枝,剪掉没用的分支

换一个迷宫,在这个迷宫中会出现碰壁问题,如果走到死胡同了要往回走.这就是回溯.
(前面是当有可以向前走的路时是不能回退的,而如果前进的路没有了,则采用回溯)

回溯

解决的问题：从一个指定集合中选择一个对象序列,使该序列满足某一标准
回溯是经过修改的深度优先查找方法,是在树中查找

#先序遍历是树的一种深度优先查找
def depth_first_search(head):
  vist head
  for u in head.child:
    depth_first_search(u)

回溯过程包括:对一个状态空间树进行深度优先查找,检查每个节点有没有希望(是否满足条件).如果没有希望,回溯到该节点的父节点.

剪枝相较于回溯的区别是,它只做判断这条路是否可行,如果不可行,直接断了这条路,而回溯是会进行尝试性操作,如果最终不可行,返回上一状态,再切断此路.

类似迷宫问题:也是搜索+剪枝+回溯

把华容道里的空格当作我们迷宫中的一个移动点.
好像空格在迷宫中移动,每次到一个新的状态,就有几个方向可以搜索,如果是之前碰到过的状态那就不搜索.

考虑何时用回溯？
回溯在迷宫中对应于走到了死胡同了,而在这里华容道里的回溯,可以指其各个方向的路都已经走过了,那么此时就相当于无路可走,那么就应该回溯.

如何实现回溯？
回溯的过程有点像栈的操作,往前走就像是入栈,到了死胡同要往回走,就像是出栈.
当然也可以考虑用递归函数的形式来实现回溯

正确的移动步骤应该如何记录?
同样类似于迷宫里的方法.search开始时把步骤记录下来,如果search未成功,则将之前记录的步骤去除

上述思路可以通过暴力求解的方式解决,且时间复杂度高.考虑优化.

上述用回溯的思想说白了就是利用深度优先搜索.要想得到最优解,最好使用广度优先搜索.

所谓深度优先搜索,就是会找到一个方向一直往里搜到底
而广度优先搜索就不一样了,他会优先搜索所有方向的第一步,然后再接着搜索每一个可行方向的第二步,以此类推;这就像电视剧里的分头搜索的剧情一样.

由于这里要从深度优先遍历改为广度优先遍历,因此在编码上会有一些区别.即回溯不再是必要的了.而是需要一个队列,不断放入当前状态的所有可行方向的搜索
这个方法判断结束的条件是,队列为空,所有方向都找不到,那就无法胜利,当在过程中找到了一个胜利,则退出.

如何记录最终的路径?
趋势只要每一个状态,记住它上一个状态以及这次的方向就可以了.

广度优先搜索比深度优先搜索多了一个队列来存储要搜索的状态,但是它却能得到最优解,这也是空间换时间吧

如果要得到最优解肯定用广度优先搜索,但是深度优先搜索什么时候该用呢?
如果要求找到游戏胜利的所有路径,可能需要大量的空间,而深搜的空间更少,所以更适合.