迷宫求解

来自计算思维百科
跳转至: 导航搜索
迷宫求解.jpg

给你一个迷宫,指定一个入口和一个出口,你能从入口走到出口吗?

解决方案

方案1---回溯法

解决方法:出发前做两种标记,比如说红纸和绿纸。绿纸标记你走过的路,避免回到原点,红纸用来标记死路。你从出口出发,向前方,左方,右方探索,每次探索遇到岔路口的时候做一个绿纸标记,表示我来过这里。当发现是死路的时候,你按原路返回到最后一个岔路口,并在那个路口做红纸标记,表示那个岔路不可走,然后重新选择一个没有走过的路口,这样就不会走同样的死路,就不会犯同样的错误两次。就这样一直探索,直到走到终点。这种解决问题的方法就是经典的回溯法。

涉及的计算思维

在现实生活中,有好多人都会因为不认识路而回到原点。其实繁华大城市里环境差不多的街道就像是迷宫,如果没有看地图真的会迷路。又比如有人在沙漠中迷路,如果他一直往前走,他就会走回原点,因为人的左脚踏出的步长和右脚不一致所致,所以我们应该结合沙漠在地图的位置和太阳的方向来寻找出路。

上面所说的问题都是迷宫求解问题。迷宫求解问题可以用计算机的栈存储结构和回溯法来做。马踏棋盘和世界名画陈列室问题也是类似的问题,他们都可以用回溯法来做。这体现了计算思维的递归特点。