首页 > 代码库 > 猫和老鼠的迷宫问题
猫和老鼠的迷宫问题
题目如下：
用一个10行10列的二维平面表格表示迷宫，左上角作为迷宫的入口，右下角作为迷宫的出口。设迷宫中有一只猫在随机游走，一只老鼠要从迷宫的入口逃到出口。如果老鼠遇到猫就会被吃掉。假定老鼠和猫的速度是相同的，而且猫不会主动搜寻老鼠。问题求解的目标是老鼠寻找一条从入口到出口的通路，并且不会被猫吃掉，写出问题的求解规则。（心形为老鼠初始位置，菱形为猫初始位置，五角星为迷宫出口）
这是人工智能导论课堂上老师留的一道作业题，课堂展示之后，为了不想让自创的解题思路就这样隐没，于是决定浪费一些时间写成博客，纪录下来。由于从开始着手解决问题到编程实现只用了不到两天的时候，所以一定会有算法漏洞以及逻辑冗余的情况。希望各路大神尽情指点，小辈一定认真学习。由于没有细心地在网上查找有没有相同的解题思路，所以如果雷同，纯属巧合。
第一眼看到题目的时候，本能反应是使用栈作为数据结构，再进行回溯来遍历整个迷宫，但又隐隐觉得别扭。后来又由于个人懒散，直到课堂展示的前两天才开始真正认真地考虑如何解决题目。
首先，为了解决这个问题，我们需要解决的疑点有二：
一、老鼠如何找到迷宫的出口；
二、如何让老鼠躲避猫，不被抓到。
有猫没猫，会对老鼠寻找出口的轨迹造成一定影响，但不会影响老鼠大体上的行走规则、行走指导思想。所以我们优先重点考虑问题一：老鼠如何找到迷宫的出口。
说起走迷宫，记得小时候玩仙剑奇侠传的时候，遇到过迷宫，走起来很费劲……直到有一天父亲对我说，走迷宫呀，贴着一边的墙走就可以啦！这句话，我一直记得很清，为什么？是因为这句话对我的现实生活和玩游戏造成了很大的影响。那么对于这道题、这个老鼠，赋予它贴墙走的智慧，它完全就可以非常轻松地找到迷宫出口。所以我们该如何遍历整体迷宫？我们用贴墙走来遍历整个迷宫！（虽然贴墙走在本题中展现出良好的优越性，但是我个人也意识到这个算法有一定的缺陷，会在本篇的最后说明。）
在真正开始讲解之前，大家需要认可和熟悉我们解决遍历整个迷宫的基本算法规则，贴墙行走便可遍历此图。如果有对此规则保持迷惑，可以在详解贴墙走规则后，亲自使用地图，尝试遍历整个迷宫后做近一步理解。在此题中，我们使用贴右墙走的方法，选择右墙是因为比较符合我们个人习惯，但左右墙都可以实现遍历整个地图。
需要给大家说清楚的是，什么叫贴右墙走？怎么算是贴右墙走？如何做到贴右墙走？规则总结起来很简单，那就是右手要始终挨着墙并且脚步要往前迈，不管遇到任何墙角任何路口，右手要始终挨着墙，这一点非常重要。
首先，假如我们处于这样的四周环境下，如下图所示（X代表墙，十字架中心代表我们现所在位置，空白表示是通路），北侧和南侧是墙，只有西侧和东侧是道路可以行走。（我将使用东南西北作为方位来描述，而不是前后左右，因为东西南北是绝对的，而前后左右是相对的，原因会在下面慢慢说明）
假如，我们现在面朝东，那么按照我们贴着右墙走的规则，下一步我们将会向东侧行驶。但是如果我们现在面朝西呢？我们需要转个身子过来，这时候我们再按照贴着右墙走的规则，我们将会向西侧行驶。
为什么在同一种所处环境下，我们会走不同的方向？为什么换一个面朝方向，我们下一步将要走的格子就会有变化？这一切都归于一个字，右。贴右墙、贴右墙，而右是一个相对位置，当我们面朝不同方向的时候，我们的右墙也不是同一堵墙。所以大家可以看到，即使在这相同环境下，但面朝方向的不同，对于下一步的选择，我们有着不同的答案。
而大家更好理解的可能是，当我们面朝相同方向的时候，如都朝北。但因为所处环境的差异，我们将走向不同的方向。如下图所示，当我们身处左侧图时，我们会选择向西；而当我们身处右侧图时，同样是面朝北，我们会继续向北。所以可以简单得出，即使面朝同一方向，但由于处在不同环境，对于下一步的选择，我们依然有不同的选择。
举前面的例子，只是想告诉大家。在这个迷宫中我们会遇到各种各样的情况，4种朝向、14种环境，相乘后便是56种不一样情形。对待这56种情形，老鼠做出的判断也应该是不同的（遵循贴右墙行驶的原则而做出的判断）。那么我们该如何在程序中实现对待这56种情形做出相应的判断呢？
首先，描述这56种情况中的任何一种都是相对不易的，可以自己想一下，我们的判断条件中需要有四周围墙的有无和老鼠的朝向。而如果直接用程序实现，程序会显得异常冗长，所以我们只能寻找更好的手段来标识判断这56种情况。
所以，我们想到了用数字标识，数字简单清晰，一长串case语句便可将四分之一情况归纳总结，但是我们应该如何对每一种情况给定一个特定的数字？用1,2,3,4,5,6一直到56来标识这56种情况可不可以？一个数字一种情况，标识每个图的问题解决了，但留下来的问题是老鼠怎么知道它现在所在的位置是多少号？可能第一步还因为程序里有老鼠初始位置的信息，知道自己是第17种情况，应该向右走（假设），但是第二步呢？程序总不能把老鼠要走的路径全都存在程序里吧？那和直接把走向迷宫终点的路径告诉小鼠，让小鼠沿着路径走过去有什么区别吗？所以我们不能这样简简单单的使用数字标识，而是需要用这些数字来满足一些实时性的要求，也就是说，当老鼠处于这样的环境、这样的朝向时，它可以立刻求出用来标识的数字。
我们现在有两个变量，一是老鼠面朝方向、二是四周墙面情况。我们可以认为这是一种稍微复杂的“映射”，通过变量一和变量二的计算，得到变量三，而变量三便是我们想要的标识数字。而我们的要求只有一点，那就变量三必须是唯一的，如果有两对（变量一，变量二）计算，可以同时得到相同的变量三，那么变量三将失去作为标识的作用，同时我们也认为此种映射法则是失败的。
于是，我们先对老鼠面朝方向赋予了权重，面朝北权重为1，面朝西权重为2，面朝南权重为3，面朝东权重为17，如下所示：
然后我们再对四周墙壁赋予了权重，北面墙权重为7，西面墙权重为11，南面墙权重为31，东面墙权重为37，如下图所示：
于是自创公式：
weight_value = http://www.mamicode.com/direction_value * (map[x-1][y] * W_NORTH + map[x][y - 1] * W_WEST+ map[x + 1][y] * W_SOUTH+ map[x][y + 1] * W_EAST)
其中direction_value为老鼠当前面朝方向的权重，W_NORTH，W_WEST，W_SOUTH，W_EAST分别为北墙、西墙、南墙、东墙各自的权值。由于此迷宫存储在二维数组中，值为0认为是墙、值为1认为是通路，而坐标（x , y）是老鼠所在的中心坐标。故此自创“权值公式”中文含义是：老鼠面朝方向的权值乘以所有通路方向的权值之和得到的数字，是此情形（此环境，此朝向）的标识数字。
标识数字的选择，如上文所说，我们只有一个要求，要求它的唯一性。所以我们对这8个数字的严格挑选，需要确保在56次计算得出来的数字没有任意两个相同。近十次的挑选8个数字的组合后，组合（1,2,3,17,7,11,31,37）符合我们要求，故我们使用这8个数字作为我们的权值，来时时刻刻标记老鼠的情形，并进一步做出判断指导。如下图便是，这些标识数字代表的是下一步应该向东西南北各个方向前进。
Ps：由于公式的自创性，故应该会存在更好的公式，更方便理解和计算，望大神们点拨。
根据计算，我们可以总结得出，当出现某些特定数字时，我们将向某特定方向行驶，于是我们贴右墙就有了完整的指导方针！所以直至现在，我们已经将问题一：老鼠如何找到迷宫出口成功解决，接下来，我们将继续解决问题二：如何让老鼠躲避猫？
我们需要解决的问题有两个：
第一：如何不让老鼠主动碰到猫。
第二：如何做到当老鼠遇到猫逃跑后，依然可以尽快找到迷宫出口。
对于第一个问题，我们将采用，认为猫是一堵墙的方法，来绝对避免老鼠主动碰到猫；与此同时，为了确保问题的简单，我们同时认为老鼠也是一堵墙，猫绝不可能主动碰到老鼠。而对于猫和老鼠谁先走的问题，我们做出这样的理解，我们赋予老鼠这样的智慧：等到猫走了，我再走。我们需要强调的是，我们不是在刻意模糊题目，而是在赋予老鼠这样的规则，来确保老鼠的安全（当然，如果把老鼠也当作一堵墙，猫是永远不会扑向老鼠的。但在解题的初期，我们是有考虑如何避免猫碰到老鼠，由于后期觉得较复杂就舍弃掉了，但解释还是这样解释）
对于第二个问题，我们将使用贴墙走的方式来作为逃跑方向的指导方针并采用栈来存储遇到猫后逃跑的路线。使用什么方向并不重要，所以我们直接使用之前的算法作为逃跑方向的指导；而对于为什么使用栈来存储逃跑路线，是因为栈的后进先出的特点，很符合我们现有的情况。既然我们从这里跑，那么我们还要回到这里，我们还要从遇到猫的这个地方继续开始对迷宫进行遍历，否则我们可能会恰好漏掉迷宫出口的位置而进行第二次对迷宫的遍历。
大体的思路是这样，但实际的程序逻辑却比较复杂，在这里，我们简单的表示一下逻辑关系。
1 If（老鼠现在不在逃跑『也就是没遇到猫』） 2 3 { 4 5 If(猫不在老鼠下一步的位置) 6 7 老鼠按照贴墙规则正常前进； 8 9 Else 『猫恰好挡住了老鼠的去路』 10 11 将老鼠所在位置信息入栈，并继续按照贴墙规则前进； 12 } 13 14 Else 『老鼠现在正在逃跑』 15 16 { 17 18 If(猫继续追过来了) 19 20 将老鼠所在位置信息入栈，并继续按照贴墙规则前进； 21 22 Else『猫继续追过来了猫不在栈顶所存信息的位置，可以简单理解为猫没有追来』 23 24 老鼠按照栈顶信息回到上一步的位置，并弹栈； 25 26 }
直到现在，我们已经成功的解决了猫与老鼠的迷宫问题，下面是C++的完成实现代码。如果需要测试，需要在Do_it()函数中的while语句增添节点，通过一次debug便可实现猫和老鼠的一次移动。由于赶代码太匆忙了，注解不足，同时代码可能会有大量冗余，会在闲时慢慢修改，尽情谅解！
1 #include<iostream> 2 using namespace std; 3 #include <stdlib.h> 4 #include <time.h> 5 6 #define ROW 10 7 #define COL 10 8 9 #define T_NORTH 1 10 #define T_WEST 2 11 #define T_SOUTH 3 12 #define T_EAST 17 13 14 #define W_NORTH 7 15 #define W_WEST 11 16 #define W_SOUTH 31 17 #define W_EAST 37 18 19 int map[ROW][COL] = 20 { 21 { 0,0,0,0,0,0,0,0,0,0 }, 22 { 0,1,1,1,1,0,1,1,1,0 }, 23 { 0,0,0,1,0,0,1,0,1,0 }, 24 { 0,1,1,1,0,1,1,0,0,0 }, 25 { 0,1,0,1,1,1,1,0,1,0 }, 26 { 0,1,0,1,1,0,1,1,1,0 }, 27 { 0,1,0,0,0,0,0,1,1,0 }, 28 { 0,1,1,1,1,0,1,0,1,0 }, 29 { 0,1,0,1,1,0,1,1,1,0 }, 30 { 0,0,0,0,0,0,0,0,0,0 }, 31 }; 32 33 int x = 1, y = 1;//老鼠位置坐标(x,y) 34 int cx = 4, cy = 6;//猫位置坐标(cx,cy) 35 int cx0 = 4, cy0 = 6; 36 37 38 void Display_Map() 39 { 40 for (int i = 0; i < ROW; i++) 41 { 42 for (int j = 0; j < COL; j++) 43 { 44 if (i == x&&j == y) 45 cout << "●"; 46 else if (i == cx&&j == cy) 47 cout << "▲"; 48 else 49 { 50 if (!map[i][j]) 51 cout << "□"; 52 else 53 cout << "■"; 54 } 55 } 56 cout << endl; 57 } 58 } 59 60 void Cat_trail() 61 { 62 extern int cx, cy; 63 extern int cx0, cy0;//猫之前的位置(cx0,cy0) 64 int Cat_direction; 65 66 srand((unsigned)time(NULL)); 67 //初始化随机数种子 68 69 //cout << "(" << cx << "," << cy << ")" << endl; 70 71 int Cat_judge = 0; 72 while (!Cat_judge) //产生一个随机方向 73 { 74 Cat_direction = rand() % 4; 75 76 switch (Cat_direction) 77 { 78 case 0: 79 Cat_judge = map[cx - 1][cy]; 80 break; 81 case 1: 82 Cat_judge = map[cx][cy - 1]; 83 break; 84 case 2: 85 Cat_judge = map[cx + 1][cy]; 86 break; 87 case 3: 88 Cat_judge = map[cx][cy + 1]; 89 break; 90 default: 91 break; 92 } 93 } 94 95 //下一步行走 96 switch (Cat_direction) 97 { 98 case 0: 99 cx = cx - 1; 100 break; 101 case 1: 102 cy = cy - 1; 103 break; 104 case 2: 105 cx = cx + 1; 106 break; 107 case 3: 108 cy = cy + 1; 109 break; 110 default: 111 break; 112 } 113 114 map[cx0][cy0] = 1;//将猫刚走过的位置还原成0 115 cx0 = cx, cy0 = cy; 116 map[cx][cy] = 0; 117 118 } 119 120 void Do_it() 121 { 122 extern int x, y; 123 int x0 = 1, y0 = 1;//老鼠之前的位置(x0,y0) 124 125 int direction_num = T_EAST;//方向数，北1，西2，南3，东17 126 127 int weight_num = 0;//位置(x,y)权值 128 int pre_weight_num = 0; 129 int escape[10][3] = { 0 }; 130 int s_top = 0; 131 132 int pre_Way_judge = 0; 133 int Way_judge = 0; 134 int Escape_judge = 0; 135 136 while (x != 8 || y != 8) 137 { 138 map[x][y] = 0;//将老鼠在地图上的位置标记 139 x0 = x, y0 = y; 140 141 pre_weight_num = direction_num*(map[x - 1][y] * W_NORTH + map[x][y - 1] * W_WEST + map[x + 1][y] * W_SOUTH + map[x][y + 1] * W_EAST);//计算猫移动前分叉路口数 142 switch (pre_weight_num) 143 { 144 //下一步，向北行驶 145 case 36:case 18:case 306:case 150: 146 case 110:case 98:case 49:case 38: 147 case 76:case 88:case 119:case 21: 148 case 7:case 14: 149 pre_Way_judge = 0; 150 break; 151 //下一步，向西行驶 152 case 158:case 237:case 165:case 147: 153 case 126:case 42:case 84:case 144: 154 case 96:case 187:case 33:case 11: 155 case 22:case 54: 156 pre_Way_judge = 1; 157 break; 158 //下一步，向南行驶 159 case 1343:case 1275:case 225:case 833: 160 case 646:case 114:case 1156:case 714: 161 case 204:case 136:case 527:case 93: 162 case 31:case 62: 163 pre_Way_judge = 2; 164 break; 165 //下一步，向东行驶 166 case 79:case 75:case 55:case 935: 167 case 48:case 748:case 132:case 44: 168 case 816:case 68:case 629:case 111: 169 case 37:case 74: 170 pre_Way_judge = 3; 171 break; 172 } 173 174 Cat_trail(); 175 176 int Cash_judge = 0;//是否碰撞 177 switch (pre_Way_judge) 178 { 179 case 0: 180 if (x - 1 == cx&&y == cy) 181 Cash_judge = 1; 182 break; 183 case 1: 184 if (x == cx&&y - 1 == cy) 185 Cash_judge = 1; 186 break; 187 case 2: 188 if (x + 1 == cx&&y == cy) 189 Cash_judge = 1; 190 break; 191 case 3: 192 if (x == cx&&y + 1 == cy) 193 Cash_judge = 1; 194 break; 195 } 196 197 weight_num = direction_num*(map[x - 1][y] * W_NORTH + map[x][y - 1] * W_WEST + map[x + 1][y] * W_SOUTH + map[x][y + 1] * W_EAST);//计算猫移动后分叉路口数 198 switch (weight_num) 199 { 200 //下一步，向北行驶 201 case 36:case 18:case 306:case 150: 202 case 110:case 98:case 49:case 38: 203 case 76:case 88:case 119:case 21: 204 case 7:case 14: 205 Way_judge = 0; 206 break; 207 //下一步，向西行驶 208 case 158:case 237:case 165:case 147: 209 case 126:case 42:case 84:case 144: 210 case 96:case 187:case 33:case 11: 211 case 22:case 54: 212 Way_judge = 1; 213 break; 214 //下一步，向南行驶 215 case 1343:case 1275:case 225:case 833: 216 case 646:case 114:case 1156:case 714: 217 case 204:case 136:case 527:case 93: 218 case 31:case 62: 219 Way_judge = 2; 220 break; 221 //下一步，向东行驶 222 case 79:case 75:case 55:case 935: 223 case 48:case 748:case 132:case 44: 224 case 816:case 68:case 629:case 111: 225 case 37:case 74: 226 Way_judge = 3; 227 break; 228 } 229 230 if (Escape_judge == 0) 231 { 232 if (!Cash_judge) 233 { 234 switch (Way_judge) 235 { 236 case 0: 237 { 238 x = x - 1; 239 direction_num = T_NORTH; 240 } 241 break; 242 case 1: 243 { 244 y = y - 1; 245 direction_num = T_WEST; 246 } 247 break; 248 case 2: 249 { 250 x = x + 1; 251 direction_num = T_SOUTH; 252 } 253 break; 254 case 3: 255 { 256 y = y + 1; 257 direction_num = T_EAST; 258 } 259 break; 260 } 261 262 map[x0][y0] = 1;//将老鼠刚走过的位置还原成1 263 264 } 265 else 266 { 267 escape[s_top][0] = x; 268 escape[s_top][1] = y; 269 escape[s_top][2] = direction_num; 270 271 Escape_judge = 1; 272 s_top++; 273 274 switch (Way_judge) 275 { 276 case 0: 277 { 278 x = x - 1; 279 direction_num = T_NORTH; 280 } 281 break; 282 case 1: 283 { 284 y = y - 1; 285 direction_num = T_WEST; 286 } 287 break; 288 case 2: 289 { 290 x = x + 1; 291 direction_num = T_SOUTH; 292 } 293 break; 294 case 3: 295 { 296 y = y + 1; 297 direction_num = T_EAST; 298 } 299 break; 300 } 301 302 map[x0][y0] = 1;//将老鼠刚走过的位置还原成1 303 304 } 305 } 306 else 307 { 308 if (cx == escape[s_top - 1][0] && cy == escape[s_top - 1][1]) 309 { 310 escape[s_top][0] = x; 311 escape[s_top][1] = y; 312 escape[s_top][2] = direction_num; 313 314 Escape_judge = 1; 315 s_top++; 316 317 switch (Way_judge) 318 { 319 case 0: 320 { 321 x = x - 1; 322 direction_num = T_NORTH; 323 } 324 break; 325 case 1: 326 { 327 y = y - 1; 328 direction_num = T_WEST; 329 } 330 break; 331 case 2: 332 { 333 x = x + 1; 334 direction_num = T_SOUTH; 335 } 336 break; 337 case 3: 338 { 339 y = y + 1; 340 direction_num = T_EAST; 341 } 342 break; 343 } 344 345 map[x0][y0] = 1;//将老鼠刚走过的位置还原成1 346 347 } 348 else 349 { 350 map[x][y] = 1; 351 352 s_top--; 353 x = escape[s_top][0]; 354 y = escape[s_top][1]; 355 direction_num = escape[s_top][2]; 356 357 if (0 == s_top) 358 Escape_judge = 0; 359 360 } 361 } 362 Display_Map(); 363 cout << endl; 364 } 365 } 366 367 int main() 368 { 369 Do_it(); 370 return 0; 371 }
关于数学，关于计算机，还有太多值得自己去学习，希望以后可以在这里记录下来。
如有错误或者建议，请尽情指教！
大三上
2016/10/19凌晨
猫和老鼠的迷宫问题