回溯技术解决中文积木拼图(华荣道)(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/backtrack-technique-to-solve-chinese-slide-block-p-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 7 分钟阅读 - 3348 个词 阅读量 0回溯技术解决中文积木拼图(华荣道)(译文)
原文地址:https://www.codeproject.com/Articles/10454/Backtrack-technique-to-solve-Chinese-Slide-Block-P
原文作者:Dong Xiang
译文由本站 robot-v1.0 翻译
前言
A C# 2.0 program which solves a puzzle by DFS and BFS algortithms.
一个C#2.0程序,可通过DFS和BFS算法解决难题.
介绍(Introduction)
我最喜欢的游戏是<中国方块拼图>(Hua Rong Dao).我曾经花很多时间思考如何解决它.因此,当我学习回溯技术时,我立即选择尝试它.(Chinese Slide Block Puzzle (Hua Rong Dao) was my favorite game. I used to spend hours pondering on how to solve it. So, when I learned backtracking technique, I immediately chose to try on it.)
回溯(Back tracking)
首先,让我们对回溯进行一些介绍.回溯是一种遍历搜索空间所有可能配置的系统方法.通常,回溯算法如下所示:(First, let’s have a little introduction on backtracking. Backtracking is a systematical method to iterate through all the possible configurations of a search space. In general, a backtrack algorithm looks like this:)
bool backtrack(int step, Solution candidate, Data input)
{
if (IsASolution(candidate, step, input))
{
processSolution(candidate);
return true;
}
newCandidates = CreateNewCandidates();
foreach (Solution s in newCandidates)
{
bool finished = backtrack(step + 1, s, input);
if (finished) return ture;
}
return false;
}
在搜索空间中进行迭代时,我必须决定要使用哪种算法:深度优先搜索(DFS)或广度优先搜索(BFS).(While iterating through the search space, I must make a decision which algorithm to use: Depth first search (DFS), or Breadth first search (BFS).)
DFS(DFS)
上面的伪代码实际上是在使用DFS.通常,DFS不会在队列中存储所有候选项,因此其内存效率更高.但是,DFS有两个问题:(The above pseudo-code is actually using DFS. In general, DFS is more memory efficient since it does not store all the candidates in a queue. However, DFS has two problems:)
- 如果找到解决方案,我不知道这是否是最佳解决方案.(If I hit a solution, I don’t know whether it is the best solution or not.)
- 如果在找到解决方案之前在搜索树中遇到了一个很深的分支,那将花费很长时间.(If I run into a very deep branch in the search tree before hitting the solution, it will take a very long time.) 为了解决第一个问题,当我找到解决方案时,我不会停止搜索.相反,我继续遍历这棵树,比较解决方案以找到最佳解决方案.为了解决第二个问题,我任意选择一个固定的深度范围.如果选择的范围太小,可能根本找不到任何解决方案.在这种情况下,我会不断加深搜索限制,直到找到解决方案为止.(To solve the first problem, I don’t stop the search when I hit a solution. Instead, I continue to traverse the tree, and compare the solutions to find the best one. To solve the second problem, I arbitrarily choose a fixed depth bound. If the bound I choose is too small, I may not find any solution at all. In that case, I iteratively deepen the search limit until I find a solution.)
BFS(BFS)
DFS的替代方法是BFS. BFS回溯的伪代码为:(The alternative to DFS is BFS. The pseudo-code for BFS backtracking is:)
bool BSFbacktrack(Data input)
{
queue.Enqueue(firstCandidate);
while (!queue.empty())
{
candidate = queue.Dequeue();
if (IsASolution(candidate, input))
{
processSolution(candidate);
return true;
}
newCandidates = CreateNewCandidates();
foreach (Solution s in newCandidates)
{
queue.Enqueue(s);
}
}
}
在BFS搜索中,我必须将新的候选人存储在队列中.因此,BFS比DFS需要更多的内存.但是,与DFS不同,其第一个解决方案是最佳解决方案.(In BFS search, I have to store the new candidates in a queue. So, BFS requires more memory than DFS. However, unlike the DFS, its first solution is the best solution.)
决定使用DFS或BFS(Decide to use DFS or BFS)
因为我想要最好的解决方案,所以BFS算法正是我想要的.如上所述,BFS的局限性在于它的内存.让我们计算一下我需要多少内存.在中文滑块游戏中,我至少需要走116步才能达到目标.因此,队列必须保存步骤115的所有配置.如果每个步骤都有两个选项,那么我必须在队列中存储2 ^ 115个节点.当然,这太多了.幸运的是,只有10块瓷砖.因此,拼图的配置小于10!<2 ^ 22.如果跟踪所有访问过的节点,则可以跳过那些访问过的节点以节省内存.更重要的是,这种技术避免了循环.因此,对于BFS和DFS都非常重要.(Because I want the best solution, BFS algorithm is exactly what I want. As I talked above, the limit of BFS is its memory. Let’s calculate how much memory I need. In the Chinese slide block puzzle, I need to move at least 116 steps to reach the goal. So, the queue must hold all the configurations for step 115. If each step has two options, then I have to store 2^115 nodes in the queue. This is certainly way too many. Fortunately, there are only 10 pieces of tile. So, the configuration of the puzzle is less than 10!<2^22. If I keep track of all nodes that I have visited, I can skip those nodes that I have visited to save memory. More importantly, this technique avoids loops. So, it is important for both BFS and DFS.) 在我的程序中,我尝试了DFS和BFS.我比较两个结果以验证程序是否正确.有趣的是,我发现程序中的BFS比DFS快60倍.总的来说,这肯定是不正确的.(In my program, I have tried both DFS and BFS. I compare the two results to verify the program is correct. Interestingly, I found that the BFS is 60 times faster than DFS in my program. This is certainly not true in general.)
难题的哈希(Hash of the puzzle)
为了加快两种配置的比较,我将每种情况的哈希计算为(To speed up the comparison of two configurations, I compute the hash of each case as a) long
数.因为拼图的大小是4 * 5,所以坐标只需要2 + 3 =5位.拼图中有10个磁贴,总计50位.由于大小(number. Because the size of the puzzle is 45, the coordinate only needs 2+3=5 bits. There are 10 pieces of tile in the puzzle, which adds up to 50 bits. Since the size of*) long
在C#中是64位,我可以用一个来表示拼图的每个配置(*is 64 bits in C#, I can represent each configuration of the puzzle in one*) long
数.(*number.*)
类层次结构中的设计模式(Design pattern in the class hierarchy)
该程序有很多变体:(There are many variants in this program:)
- 拼图有五种布局.(There are five layouts of the puzzle.)
- 有两种搜索算法.(There are two search algorithms.)
- 共有四种瓷砖,形状和尺寸都不同.(There are four kinds of tiles, with different shapes and sizes.)
- 每个图块可以在四个方向上移动.(Each tile can move in four directions.)
一开始,我发现我经常使用((In the beginning, I found that I was using a lot of ()
switch
/(/)if
)条件语句.在许多功能中重复相同的逻辑.这明确表明我需要在这里使用设计模式.复习了我从NetObjectives上的课程之后,我意识到() conditional statements. The same logic is repeated in many functions. This is a clear indication that I need to use design patterns here. After reviewing the class I took from NetObjectives, I realized that)**访客模式(visitor pattern)**正是我所需要的.(is exactly what I needed.) 访客模式也称为双调度.其想法是将决策从运行时转移到设计阶段.(Vistor pattern is also called double-dispatching. Its idea is to move the decision making from run-time to design stage.) 在我的设计中(In my design,)Tile
是的访客(is a visitor to)IDireciton
.为每个访问者定义了四个功能:(. Four functions are defined for each visitor:)MoveUp
,(,)MoveDown
,(,)MoveRight
和(, and)MoveLeft
.在上课时(. In the visited class)IDireciton
,我定义一个函数(, I define a function)Accept(Tile)
.此功能是调度程序(虚拟功能),在(. This function is a dispatcher (virtual function) which is implemented in)IDireciton
的四个孩子班(’s four child classes)Up
,(,)Down
,(,)Left
和(, and)Right
.类的层次结构是:(. The class hierarchy is:)
中文积木拼图的背景(华荣道)(Background of the Chinese Slide Block Puzzle (Hua Rong Dao))
在三国王朝中,曹操是最有权势的国王.他用一支强大的军队入侵了另外两位国王.然而,在赤壁战争中,曹操被另两位国王的联合击败.在逃跑路线中,曹操被关羽将军抓获.由于曹操在他的艰难时期对他非常慷慨,关羽将军决定让曹操通过,即使面临死刑的危险.您的目标是帮助关羽安排将军和士兵让曹操逃脱.(In the three-Kingdom dynasty, CaoCao was the most powerful king. He invaded the other two kings with a mighty army. However, in the war of ChiBi, CaoCao was defeated by the union of the other two kings. In the escaping route, CaoCao was caught by General Guan Yu. Because Caocao had been very generous to him during his difficult time, General Guan Yu decided to let Caocao pass, even in the risk of the death punishment. Your goal is to help Guan Yu arrange his generals and soldiers to let CaoCao escape.) 你可以找到游戏(You can find the game) 这里(here) .在我的程序中,我以以下格式打印拼图:(. In my program, I print the puzzle in this format:)
2003
2003
4115
4785
6**9
-xx-
exit
这个难题一共有十个.曹操是编号为0的最大块(2X2).关羽将军是编号为1的水平矩形.编号为2到5的四个垂直矩形代表四个将军.最后四个小方块,编号从6到9,代表四名士兵.仅有两个空白标记为" ".(There are totally ten pieces in this puzzle. Caocao is the biggest block (2X2) with number 0. General Guan Yu is the horizontal rectangle with number 1. The four vertical rectangles, numbered 2 through 5, represent four generals. The last four small blocks, numbered 6 through 9, represent four soldiers. The only two empty spaces are marked with ‘’.) 游戏规则是将大块0移到底部.(The rule of the game is to move the big block 0 to the bottom.) 初始状态还有其他布局.您可以在源代码底部找到所有布局和解决方案.这是最简单的布局及其解决方案.(There are also other layouts of the initial state. You can find all the layouts and solutions in the bottom of the source code. Here is the easiest layout and its solution.)
Initial state:
6711
0022
0033
8944
*55*
Solve the puzzle in 20 steps:
5R[001] 8D[002] 9D[003] 0D[004] 2L[005] 2L[006] 3U[007] 4U[008] 5U[009] 9R[010]
6711 6711 6711 6711 6711 6711 6711 6711 6711 6711
0022 0022 0022 **22 *22* 22** 2233 2233 2233 2233
0033 0033 0033 0033 0033 0033 00** 0044 0044 0044
8944 *944 **44 0044 0044 0044 0044 00** 0055 0055
**55 8*55 8955 8955 8955 8955 8955 8955 89** 8*9*
8R[011] 9R[012] 8R[013] 0D[014] 4L[015] 4L[016] 5U[017] 8U[018] 8R[019] 0R[020]
6711 6711 6711 6711 6711 6711 6711 6711 6711 6711
2233 2233 2233 2233 2233 2233 2233 2233 2233 2233
0044 0044 0044 **44 *44* 44** 4455 4455 4455 4455
0055 0055 0055 0055 0055 0055 00** 008* 00*8 *008
*89* *8*9 **89 0089 0089 0089 0089 00*9 00*9 *009
步骤编号在括号中.第一个移动是5R,这意味着将块5向右移动.第二步是8D,这意味着将块8向下移动.第三步是9D,这意味着将块9向下移动,依此类推…(The step number is in bracket. The first move is 5R, which means move the block 5 to right. The second step is 8D, which means move the block 8 down. The third step is 9D, which means move block 9 down, etc…)
实施平台(The implementation platform)
该程序是用C#2.0和VS.NET 2005 Beta 2实现的,因为我真的很喜欢泛型.(The program is implemented with C# 2.0 and VS.NET 2005 Beta 2 because I really like the generics.)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# Windows .NET .NET2.0 Visual-Studio VS2005 Dev 新闻 翻译