C++穿越迷宫问题.doc

C++穿越迷宫问题（一直靠着右手边走） 注：不瞒大伙，这是我这学期学C++期末的时候交的实验报告。 由于这是本人自己原创的算法，所以在这里提出，愿与大家分享。有不足之处请大伙指出，相互交流讨论。作为初学者，我愿意谨听教诲！ Duck. 2013.6.26 一，研究问题 穿越迷宫 二，问题阐述 “@”表示墙，“· ”表示迷宫中可行路线上的空格，走过的路线用“X”表示。本问题只研究12×12规模且只有一个入口和一个出口（迷宫也许会不通）的迷宫。如何从入口走到出口？ 三，算法分析 问题一， 迷宫构造 分析 这个问题是自定义，即我对这个问题制定的规则，没有什么好分析的 解决 首先，我用二维字符型数组来表示迷宫的墙和可行路 其次，可由系统产生0到1的随机数来控制每一个位置产生墙的概率，当然，如果要使概率可变动，那也无非是传递一个值而已。为使问题简单化，我将产生墙的概率设置为30%。 第三，将第一行和最后一行全部设置为墙，第一列和最后一列均只有一个可行路。 问题二， 穿越方式 分析 这类问题解决的方法应该很多，但就我现在掌握的以及现在的灵感，我只能想到蛮力的办法。 解决 一直沿着穿越者的右手边的墙壁走，如若此迷宫是通的，那一定能找到出口！ 用递归的办法，我只需要研究当前的位置到下一步的过程就可以了。 问题三， 方向控制 分析 1、我设置的是二维数组，其动态必须通过数组的下标来控制 2、对于穿越者来说，他的方向只有前后左右，人在其中必定是不知道自己的坐标的 3、有了方向才不能迷失，这对于我们的穿越者也同样如此，每一次作的决策就是选择方向，即向左转90°还是不转还是向右转90°，这里规定穿越者一次只能选择其中一种，向左转和向右转的次数从最开始就累计，且一次向左转和一次向右转可抵消为不转 4、由于迷宫是随机构造的，所以也有可能出现类似漩涡一样的路径，所以累计的向左转或者向右转的次数也有可能超过3次，即在空间存在转的角度超过360°，那么就需要研究同一方向上的转动次数的规律。 解决 根据以上分析，需要将做决策时穿越者的状态，具体的说就是穿越者面向的方向，用坐标绝对位置来表示出来。 规定初始位置人的朝向是坐标方位向右用sum=0表示； 每一次穿越者向自己的左边转一次，sum就减1； 每一次穿越者向自己的右边转一次，sum就加1； 将同一方向上的数字进行研究，可以发现其内在的规律： 绝对向右的数字有…-12,-8,-4,0,4,8,12…=4n 绝对向上的数字有…-13,-9,-5,-1,3,7,11…=4n-1 绝对向左的数字有…-14,-10,-6,-2,2,6,10…=4n-2 据对向下的数字有…-11,-7,-3,1,5,9,13…=4n+1 由上观察，我发现余数sum%4与方向是对应的，就是说余数可以作为方向的判断标志，根据C++对%的定义和用法，发现余数与被除数的符号一致，所以这样每个方向上有两个余数（绝对向右的除外，因为其余数为0），且它们都区别于其他方向上的余数。 这样容易得出—— 设人的当前坐标为a[i][j] sum%4=0时，人绝对向右，此时若向前走一步，则为a[i][j+1] sum%4= 3 or -1 时，人绝对向上，此时若向前走一步，则为a[i-1][j] sum%4= -3 or 1 时，人绝对向下，此时若向前走一步，则为a[i+1][j] sum%4= -2 or 2 时，人绝对向左，此时若向前走一步，则为a[i][j-1] 问题四，决策分析 过程决策 分析1 假设前面的路都没有走过 这是核心问题。 这里分析时假定此时人的当前绝对方位是面向右的。 当前穿越者位置特征分析 可以肯定，当前位置特征必定是穿越者的右边是一堵墙 穿越者前面环境分析 根据排列组合知识可知，有4（）种情况，即 1 2 3 4 X· X @ X @ X· @@ @@ @· @· 人前有路，路右有墙 人前有墙，墙右有墙 人前有墙，墙右有路 人前有路，路右有路 解决1 根据分析，决策可分为三类，即将2和3合并 1 2