翻译：《蛇棋》游戏与算法
原文：Snakes and Ladders Game Code
作者：VAMSI SANGAM
大家好，《蛇棋》游戏旨在寻找最短路径，本文讲解如何使用广度优先遍历算法（BFS，不了解该算法的同学，请参考这篇文章）来解决该问题。
笔者喜欢实用的技术，而图论就是其一。诚然，其他数据结构也应用广泛，但由于图论的特性，使其与我们的生活联系最为紧密。接下来，笔者就用经典游戏《蛇棋》举例，说明如何使用BFS来解决实际生活中的问题。
想必大家小时候一定都玩过《蛇棋》，规则就不多说了。而这里要说的，则是如何通过图论和BFS，找到最短的路径（掷骰子的次数，以及每次掷的点数），抵达终点赢取胜利。下图为蛇棋棋盘，本文将以它来举例说明。
可以看出，我们能以无数种走法抵达终点，但哪个是最优的呢？更重要的是，如何用代码来实现？这正是本文接下来要说到的。现在来想想看，如何用图（顶点和边）来表示这张棋盘？
别太苛求自己，先从简单的开始……只考虑最开始的7个方块，弄清楚什么该用项点来表示，什么该用边来表示，最后在纸上画出来。有了这个思路，很容易想到：棋盘上的数字方块可以用顶点表示，那么，边又是什么呢？按掷出来的点数，我们可以从一个方块走到另一个。现在，先不考虑棋盘上的梯子和蛇，只要把棋盘的一步部分以图的形式画出来，最后我们可以得到下图：
可以看到，按掷的点数，我们有六条路线离开方块1，对于方块2，方块3……同理。现在要明确一个重点，记住，这是有向图！一旦掷出了5点并且走到方块6，就再也无法回头了。现在，我们让问题稍微复杂一些，在上图的方块6中增加一张梯子，想想看边会有什么变化？
如果你在方块1掷出5点，则会直接到达方块27（方块2掷出4点，方块3掷出3点同理，依次类推）。现在从“逻辑”上来说，方块6在图中已经不存在了（如果没有秒懂，就再好好想想）！
无论何时到达了方块6，都无法停留在那里，而是直接跳到方块27。现在，如果用邻接表表示这张图，用顶点1表示方块1，那么顶点1的链表中是有顶点6还是有顶点27？当然是顶点27！因为顶点6即是顶点27呀！
因此，图中的边的箭头都不会停在顶点6，注意到了吗？所以，在邻接表中，顶点6的链接中会有什么呢？什么都没有！因为无论掷出几点，都无法抵达方块6，所以邻接节点链表中凡是到达顶点6的都应为空。这两点很重要，在为棋盘构造邻接表时需要特别注意。
如果方块上不是梯子，而是蛇，处理方式是一样的。逻辑上来那说该方块在链表中是不存在的，与其邻接的边也可以移除。唯一不同于梯子的是，到达蛇头会跳到数值更低的方块。
遇到蛇会增加无意义的路程，所以最优路径不会需到蛇。所以，我们假定一定不会遇到蛇，在求解最优路径时需要避开遇到蛇的情况。为了更好地理解上文中所说走到梯子和蛇的场景，这里给出了邻接表的图例：
上图应该能清晰地解释所有的问题，如果你还有不清楚的，请在评论区提问吧！现在，有了邻接表我们要做什么呢？当然是对该表调用广度优先算法啊！
用图论知识解决蛇棋问题的难点在于构造顶点和边，一旦构造好图，接下来要做的就只是对其调用BFS，就可以获知从顶点1到达顶点100的最短路径了。现在，试着实践一下，投入一点精力，相信你会成功的。但如果你还是没能得到正确答案，我将我的代码放在下面。在看代码前，以下先阐述算法的思路：
首先，不考虑棋盘上的蛇和梯子把所有的边都加上，接着再根据蛇和梯子的情况，将相关的边一一去掉；
若一个顶点n有梯子或蛇，应该按上文图中描述的那样，将能抵达该点的边进行替换。对于顶点n，需将以下顶点的边都替换成新值：顶点(n - 1)，(n - 2)，(n - 3)，(n - 4)，(n - 5)，(n - 6)。之所以选这些点，是因为只有这些项点的边包含有能抵达顶点n的边。
替换的过程被封装成了replace()方法，它获取链表后，搜索包含oldVertext值的节点，并将其替换成newVertex。
在数组中总是包含有一个无用的元素，占了索引0，使得有效的值是从索引1开始算起。
最短路径所掷骰子次数等于最后一个顶点（顶点100）的层级数，为什么？思考一下，你会明白的！
这里构造了一个递归方法printShortestPath()，它递归地找查每一个顶点的父节点，直到到达起始节点（节点1），期间会依照其走过的递归栈输出其到达的顶点，倒过来看就是路径。
/* ========== ========== ========== ========= */ // Snakes and Ladders // // Quickest Way to Win using // // Breadth First Search // // // // Functions follow Pascal Case // // Convention and Variables // // follow Camel Case Convention // // // // Author - Vamsi Sangam // // Theory of Programming // /* ========== ========== ========== ========== */ # include # include structNode { intval; structNode * next; }; // Adds a new edge, u --> v, to adjacencyList[u] structNode * add(structNode * head, intvertex) { structNode * traverse = (structNode *) malloc(sizeof(structNode)); traverse->val = vertex; traverse->next = head; returntraverse; } // The Breadth First Search Algorithm procedure. Takes empty parent and level // arrays and fills them with corresponding values that we get while applying BFS voidbreadthFirstSearch(structNode * adjList[], intvertices, intparent[], intlevel[]) { structNode * temp; inti, par, lev, flag = 1; lev = 0; level[1] = lev; while(flag) { flag = 0; for(i = 1; i val] != 0) { // A level for this is already set temp = temp->next; continue; } level[temp->val] = lev + 1; parent[temp->val] = par; temp = temp->next; } } } ++lev; } } // Replaces the value of an edge (u -->) v to (u --> v') // Traverses the entire list of adjacencyList[u] => O(|E|) operation // Here, "v" is stored as "oldVertex" and "v'" is stored as "newVertex" voidreplace(structNode * head, intoldVertex, intnewVertex) { structNode * traverse = head; // Search for the occurence of 'oldVertex' while(traverse->next != NULL) { if(traverse->val == oldVertex) { break; } traverse = traverse->next; } // replace it with the new value traverse->val = newVertex; } // Prints the Adjacency List from vertex 1 to |V| voidprintAdjacencyList(structNode * adjList[], intvertices) { inti; // Printing Adjacency List printf("\nAdjacency List -\n"); for(i = 1; i ", i); structNode * temp = adjList[i]; while(temp != NULL) { printf("%d -> ", temp->val); temp = temp->next; } printf("NULL\n"); } } // A recursive procedure to print the shortest path. Recursively // looks at the parent of a vertex till the 'startVertex' is reached voidprintShortestPath(intparent[], intcurrentVertex, intstartVertex) { if(currentVertex == startVertex) { printf("%d ", currentVertex); } elseif(parent[currentVertex] == 0) { printShortestPath(parent, startVertex, startVertex); printf("%d ", currentVertex); } else{ printShortestPath(parent, parent[currentVertex], startVertex); printf("%d ", currentVertex); } } intmain() { intvertices, edges, i, j, v1, v2; vertices = 100; // For a 10X10 board // We will make the Adjacency List's size // (|V| + 1) so that we can use it 1-indexed structNode * adjList[vertices + 1]; intparent[vertices + 1]; // Just like 'adjList' -> Size = |V| + 1 intlevel[vertices + 1]; // Just like 'adjList' -> Size = |V| + 1 for(i = 0; i v2) for(i = 0; i #算法、翻译#版权声明
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
