(AI)滑动拼图解决方案分析器（译文）

原文地址：https://www.codeproject.com/Articles/368188/AI-Sliding-Puzzle-Solution-Analyzer

原文作者：Mehmet Mutlu

译文由本站 robot-v1.0 翻译

前言

Details of my solution algorithms, implemented programs, and the results I have concluded.

我的解决方案算法,已实现的程序以及已得出的结果的详细信息.

• 下载可执行文件-43.1 KB(Download executables - 43.1 KB)
• 下载源代码120 KB(Download source code - 120 KB)
• 下载MATLAB文件-2.72 MB(Download MATLAB files - 2.72 MB)

目录(Table of Contents)

• 介绍(Introduction)

• 滑动拼图的AI搜索方法(AI Search Methods for Sliding Puzzle)

  • 2.1.已实施的不知情的搜索方法(2.1. Implemented Uninformed Search Methods)

    • 2.1.1.广度优先搜索(BFS)(2.1.1. Breadth First Search (BFS))
    • 2.1.2.深度优先搜索(DFS)(2.1.2. Depth First Search (DFS))
    • 2.1.3.迭代加深深度有限深度优先搜索(IDFS)(2.1.3. Iterative Deepening Depth Limited Depth First Search (IDFS))

  • 2.2.已实施的知情搜索方法(2.2. Implemented Informed Search Methods)

    • 2.2.1. A 错位的瓷砖启发式(A 错误)(2.2.1. A with Misplaced Tiles Heuristic (A Mis))
    • 2.2.2.曼哈顿距离启发式算法的A (A 人)(2.2.2. A with Manhattan Distance Heuristic (A Man))

• 实施计划(Implemented Program)

• 已实施的补充计划(Implemented Complementary Programs)

  • 4.1. C#中的数据转换器(4.1. Data Converter in C#)
  • 4.2. MATLAB中的数据绘图仪(4.2. Data Plotter in MATLAB)

• 结果(Results)

  • 5.1.算法分析(5.1. Algorithms’ Analysis)
  • 5.2.拼图大小分析(5.2. Puzzle Size Analysis)

• 结论(Conclusion)

• 致谢(Acknowledgement)

• 参考文献(References)

• 附录(Appendix)

1.简介(1. Introduction)

基本搜索算法构成了人工智能(AI)的基础.因此,学习它们的概念并能够实现它们对于进行更高级的AI研究至关重要.(Basic search algorithms constitute the fundamentals of Artificial Intelligence (AI). So learning their concept and being able to implement them are extremely crucial to do more advanced research on AI.)

在此报告中,我将解释解决方案算法,已实现的程序以及已得出的结果的详细信息.(In this report I will be explaining the details of my solution algorithms, implemented programs, and the results I have concluded.)

2.滑动拼图的AI搜索方法(2. AI Search Methods for Sliding Puzzle)

几乎所有与AI有关的基本知识都可以在Steward Russell和Peter Norvig的书中找到. “人工智能:一种现代方法” [1].(The very basics of almost anything related to AI can be found in the book of Steward Russell and Peter Norvig; “Artificial Intelligence: A Modern Approach” [1].)

在本次实地考察中,我们被要求实施"广度优先搜索"(BFS),“深度优先搜索”(DFS),“迭代加深深度有限搜索DFS”(IDFS)以及具有"错位的瓦片启发式"(A * Mis)的A 算法和"曼哈顿总距离启发式"(A 男子),尺寸可调.在这些算法中,A ,IDFS和BFS提供最佳路径,另一方面,DFS在检测最短解路径的意义上不是最佳的.(In this take home examination, we were asked to implement Breadth First Search (BFS), Depth First Search (DFS), Iterative Deepening Depth Limited Search DFS (IDFS), and A algorithm with “Misplaced Tiles Heuristic” (A Mis) and “Total Manhattan Distance Heuristic” (A Man) on an adjustable size “Sliding Puzzle”. Among these algorithms, A, IDFS, and BFS give optimal paths, on the other hand, DFS is not optimal in the sense of detecting the shortest solution path.*)

拼图游戏需要代理商来解决问题,这是我们在回家考试中编写的程序.这是一个确定的,偶发的,完全可观察的问题.换句话说,这是在计算机环境中要实现的最简单的问题之一.但是,滑动拼图具有非常环状的结构.最小的循环仅需两个步骤即可构建,即向前和向后移动磁贴.尽管发现两步循环非常容易,但是检测到一些较大的循环并非易事.(Sliding puzzle requires an agent to solve the problem, which is the program written by us in that take home examination. It is a deterministic, episodic, and fully observable problem. In other words, it is one of the simplest problems to realize in the computer environment. However, sliding puzzle has a very loopy structure. The smallest loop is constructed at only two steps, i.e., moving a tile forward and backward. Although finding that two step loop is very easy, some larger loops are not trivial to detect.)

在解决这个难题的同时,应该建立开放状态的历史.否则,搜索空间将无限扩展,甚至解决最简单的难题也将成为负担,有时甚至是不可能的.我将历史记录保存在C#的Sorted List结构中.它基本上使用关键字对插入的节点进行排序,并且当要求检索节点时,使用该关键字请求节点.因此,历史记录中的搜索变得非常高效和快捷.(While solving this puzzle, a history of opened states should be constructed. Otherwise, the search space unboundedly expands and solving even the easiest puzzles becomes a burden and sometimes impossible. I kept that history in a Sorted List structure of C#. It basically sorts the inserted nodes with a key and when asked to retrieve a node, the node is requested with that key. So search in the history becomes very efficient and fast.)

供进一步参考,一个3x3的滑动拼图具有181,440个可解决状态,一个4x4的拼图具有约13万亿步,而一个5x5的拼图具有约10个状态.(For further reference, a 3x3 sliding puzzle has 181,440 solvable states, a 4x4 one has ~13 trillion steps, and a 5x5 case has ~10)25(25)状态.因此,3x3几乎是在合理的时间内所有算法都可以解决的唯一方法.(states. So, 3x3 is almost the only one that can be solved with all algorithms in a reasonable time.)

解释书面代码的最佳方法是绘制其流程图.因此,我将解释流程图中使用的算法.希望他们将使该报告更易于理解和清晰.(The best way to explain a written code is to draw its flowchart. So I will be explaining the algorithms used with the flowchart. Hopefully, they will make this report easier to understand and more clear.)

我将在本报告的相应部分中更详细地说明我的方法.(I will be explaining my methods in more detail in the corresponding sections in this report.)

2.1.已实施的不知情的搜索方法(2.1. Implemented Uninformed Search Methods)

顾名思义,不知情的搜索不知道访问哪个后继节点将是有益的. BFS,DFS和IDFS是在本次实地考察中实现的.(Uninformed search, as the name implies, has no idea to visit which successor node would be beneficial. BFS, DFS, and IDFS are the ones that are implemented in this take home examination.)

2.1.1.广度优先搜索(BFS)(2.1.1. Breadth First Search (BFS))

除了历史记录,所实现的算法与[1]中所述的算法完全相同. BFS算法也可以在没有历史记录的情况下工作,但是由于滑动拼图的循环结构,搜索空间变得无边无际.因此,在找到解决方案之前填满内存变得极为可能.在算法测试中,可以看出BFS无法在合理的时间(2-3分钟)内解决超过15个步骤的难题.但是,实施历史记录后,可以在合理的时间内达到25个步骤.我的BFS总是提供最佳(最短)的解决方案路径.(The implemented algorithms are exactly the same as explained in [1] except the history keeping. BFS algorithm also works without history, but due to the loopy structure of the sliding puzzle, the search space becomes unbounded. Hence, filling up the memory before the solution is found to become extremely possible. On the algorithm tests, it is seen that BFS cannot solve puzzles exceeding 15 steps in a reasonable time (2-3 minutes). However, after implementing history, it can reach to 25 steps in a reasonable time. My BFS always gives an optimal (shortest) solution path.)

图1:已实现的BFS算法(Figure 1: Implemented BFS algorithm)#### 2.1.2.深度优先搜索(DFS)(2.1.2. Depth First Search (DFS))

DFS通常以递归方式实现.我也实现了递归版本.但是,我没有在代码的最终版本中使用它.迭代版本仍可以在源代码中找到,但是可执行程序使用非递归DFS.它与BFS几乎完全相同,除了它使用堆栈而不是队列.在3x3问题中,如果幸运的话,DFS可以在几百步之内找到解决方案.但是大多数情况下,它会搜索几乎整个搜索空间,并且大约需要一分钟才能解决3x3问题.由于4x4和更大的拼图具有更多的状态,可以说DFS不能在合理的时间内找到解决方案,除非用户很幸运.(DFS is usually implemented in a recursive manner. I have implemented the recursive version too. However, I did not use it in the final version of my code. The iterative version still can be found in the source code, but the executable program uses non-recursive DFS. It is almost exactly the same as BFS, except for the fact that it uses a stack instead of a queue. In a 3x3 problem, if one is lucky, DFS can find the solution in a few 100 steps. But most of the time it searches almost the entire search space and takes around a minute to solve a 3x3 problem. Due to the fact that 4x4 and larger puzzles have much more states, DFS can be said to fail to find a solution in a reasonable time unless the user is lucky.)

图2:实现的DFS算法(Figure 2: Implemented DFS algorithm)#### 2.1.3.迭代加深深度有限深度优先搜索(IDFS)(2.1.3. Iterative Deepening Depth Limited Depth First Search (IDFS))

我已经以递归和非递归形式实现了IDFS.但是由于易于理解和更好的跟踪代码的能力,因此最终程序中仅使用非递归算法.(I have implemented IDFS in both recursive and non-recursive forms. But only the non-recursive algorithm is used in the final program due to ease of understanding and better ability to track the code.)

图3:实现的DFS算法(Figure 3: Implemented DFS algorithm)IDFS有一个限制值,该限制从1开始.如果在第一次迭代中未找到任何解决方案,则将限制增加1,然后深度限制DFS再次开始.极限被增加直到阈值.在我的程序中,该阈值大于200,000,因此对于3x3的情况,总能找到解决方案.实际上,该限制在实际情况下永远无法达到该值,因为当深度限制变大时,要花费大量时间搜索整个搜索空间.实际上,要搜索指定深度,IDFS比BFS需要更长的时间,因为IDFS迭代搜索所有级别.但是IDFS的好处是它只需要很少的内存.存储大约等于深度限制的节点数就足够了.(IDFS has a limit value, and the limit starts from 1. When no solution is found in the first iteration, the limit is increased by 1, and Depth Limited DFS starts again. The limit is increased until a threshold value. In my program that threshold value is larger than 200,000 so that for a 3x3 case a solution is always found. Actually, the limit can never reach that value in a real case since it takes really a lot of time to search the entire search space when the depth limit gets larger. Actually to search a specified depth, IDFS takes longer than BFS since IDFS iteratively searches for all levels. But the good thing with IDFS is that it requires very little memory. Storing an approximate number of nodes equal to the depth limit is enough.)

为了获得最佳效果,我需要保留历史记录,但是这次需要对历史记录进行略微修改,如图3所示.现在,IDFS始终提供最佳解决方案.因为如果在历史记录中找到后继节点,但后继节点的深度小于历史记录列表中的节点,则将其推入堆栈并更新历史记录.(For optimality, in my IDFS, I needed to keep the history but this time the history is slightly modified as seen in figure 3. Now, IDFS always gives an optimal solution. Because if a successor node is found in the history but the successor’s depth is smaller than the one in the history list, it is pushed to the stack and the history is updated.)

2.2.已实施的知情搜索方法(2.2. Implemented Informed Search Methods)

明智的搜索方法可以做出有关打开哪个节点的预测.在此问题中,节点的成本可被视为其深度,因为每次移动仅花费1.(The informed search methods can make a prediction about opening which node will be more beneficial. In this problem the cost of a node can be thought of as its depth since each move costs only 1.)

A 通过两个启发式函数实现.其中一个正在计算放错位置的瓷砖,另一个正在计算所有瓷砖到其目标状态的曼哈顿总距离.两种启发式都是可以接受的,即小于实际求解成本.但是,曼哈顿距离比放错位置的瓷砖更接近剩余步长.(A is implemented with two heuristic functions. One of them is counting misplaced tiles, the other is counting the total Manhattan distance of all tiles to their goal states. Both heuristics are admissible, i.e., smaller than the actual solving cost. But Manhattan distance gives a closer approximation to the remaining steps than misplaced tiles.)

2.2.1. A 错位的瓷砖启发式(A 错误)(2.2.1. A with Misplaced Tiles Heuristic (A Mis))

首先,使用总错置的图块启发式实现A .它与BFS算法相似,其历史保持在IDFS算法中进行了改进.但是,这次,具有最小(成本+启发式)功能的项目从列表中弹出.该列表以排序方式保存,因此访问最小的元素比检查列表中的所有元素要快得多.我在错置的图块启发式情况下实现的A 始终会提供最佳结果.而且它明显比BFS,DFS和IDFS快.首先,我将用曼哈顿距离解释A ,然后给出A 算法的流程图,因为这对于两个启发式函数都是相同的,只是计算启发式变化.(First, A is implemented with a total misplaced tiles heuristic. It is similar to the BFS algorithm with the history keeping improvement done in the IDFS algorithm. However, this time, the item with the smallest (Cost + Heuristic) function is popped out of the list. The list is kept in a sorted manner so that accessing the smallest element is much faster than checking all elements in the list. My implemented A with misplaced tiles heuristic always gives an optimal result. And it is noticeably faster than BFS, DFS, and IDFS. First I will explain A with Manhattan distance and then give a flowchart of the A algorithm since it is the same for both heuristic functions, only the calculation of the heuristic changes.)

2.2.2.曼哈顿距离启发式算法的A (A 人)(2.2.2. A with Manhattan Distance Heuristic (A Man))

在所有已实施算法中,具有曼哈顿距离启发式算法的A 算法给出了最佳结果.它存储的节点很少,只需很少的步骤和时间即可找到解决方案.利用该算法,证明了曼哈顿距离启发式滑动拼图的有效性.(A algorithm with Manhattan distance heuristic gives the most optimal results among all of the implemented algorithms. It stores very little nodes, finds the solution with expanding very little steps and time. With this algorithm, the efficiency of Manhattan distance heuristic for sliding puzzle is proved.)

已实现的A 算法的流程图如下:(The flowchart of the implemented A algorithm is as follows:)

图4:已实现的A 算法(Figure 4: Implemented A algorithm)## 3.实施方案(3. Implemented Program)

我已经用C#实现了我的程序.作为C#的另一种规范,我们可以说它不允许将指针与自定义类和指针算术一起使用.但是,它的预定义结构允许用户即使没有指针也可以执行其工作.例如,代替创建后向指针,我们可以创建父节点,而不是跟随后向指针,我们可以跟随父节点,即,一个节点在其结构中存储了其祖先的另一个节点.同样,C#默认提供了许多实现,例如Sorted List.此外,Microsoft可能会提供用于编写​​程序的最佳IDE,即Visual Studio.(I have implemented my program in C#. As a different specification of C#, we can say that it does not allow the use of pointers with custom classes and pointer arithmetic. However, its predefined structures allow the user to do its work even without pointers. For example, instead of creating back pointers, we can create a parent node, and instead of following back pointers, we can follow parent nodes, i.e., a node stores another node which is its ancestor in its structure. Also, many implementations such as Sorted List are given as default with C#. Furthermore, Microsoft gives probably the best IDE for writing programs, Visual Studio.)

该程序分为节点,拼图和不同算法的许多类.如果一个问题可以表示为一个难题,那么我的程序就可以解决.(The program is divided into many classes for node, puzzle, and different algorithms. If a problem can be represented as a sliding puzzle, my program can solve it.)

一开始我执行的程序如下:(My implemented program at the start is as follows:)

图5:主GUI的开始屏幕(Figure 5: Start screen of main GUI)用户可以创建自己的难题,让PC创建难题,加载现有难题,甚至立即加载Monte Carlo运行.注意,必须首先生成蒙特卡洛数据.因此,让我们从一个自动拼图生成器开始.通过避免循环,它会在指定的真实距离处生成滑动拼图.但是它以深度优先的方式进行,有时求解器算法可以找到比所需步骤更短的路径.但最后,难题是按照其真实步骤而不是所需的创建步骤进行检查的.可以通过单击主GUI中的"为我创建拼图"按钮来打开自动拼图生成器.(The user can create his own puzzle, let the PC create a puzzle, load an existing puzzle, or even load a Monte Carlo run immediately. Note that, Monte Carlo data must be generated first. So let us begin with an automatic puzzle generator. It generates a sliding puzzle at the specified true distance by avoiding loops. But it does it in a depth first manner and sometimes solver algorithms can find a shorter path to the solution than the desired step. But at the end, puzzles are examined in their true steps, not in the desired creation step. The automatic puzzle generator can be opened by clicking the “Create Puzzle For Me” button in the main GUI.)

图6:开始时的自动拼图生成器(Figure 6: Automatic puzzle generator at the start)首先,必须选择拼图的大小,然后选择所需的正确步长.拼图将自动生成并显示.如果您不喜欢该拼图,只需单击"生成新拼图"按钮.您可以重复直到喜欢拼图.要保存拼图,请单击"我喜欢,保存拼图"按钮.它可以让您选择名称和保存拼图的位置.难题将另存为XML.我们可以打开XML并提供任何自定义状态.但是用户必须确保拼图的可解性.否则,我的程序还具有手动拼图生成器.自动拼图生成器的最后一件事是,它以指定的步长和大小生成由100个拼图组成的蒙特卡洛数据.它不会显示它们,但它们只是随机状态.用户可以打开蒙特卡洛数据保存文件并进行检查.但是请确保不要修改它.(First, the puzzle size must be chosen, then the desired true step. The puzzle will be generated and displayed automatically. If you do not like the puzzle, just click the “Generate New Puzzle” button. You can repeat until you like the puzzle. For saving a puzzle, click on the “I Like It, Save Puzzle” button. It will let you choose the name and place to save the puzzle. The puzzle is saved as XML. We can open the XML and give any custom state. But the user must ensure the solvability of the puzzle. Otherwise my program also has a manual puzzle generator. The last thing on the Automatic puzzle generator is that, it generates Monte Carlo data consisting of 100 puzzles at the specified step and size. It will not display them but they are just random states. The user can open the Monte Carlo data saved file and examine it. But be sure not to modify it.)

图7:使用自动拼图生成器生成的拼图(Figure 7: A puzzle generated with the Automatic Puzzle Generator)创建蒙特卡洛数据时,进度显示在表单的顶部.但是,如果要取消蒙特卡洛生成,只需关闭自动拼图生成器就可以了,并且不会保存任何内容.您可以同时打开许多拼图生成器,因为它们独立于拼图求解器工作.(While creating Monte Carlo data, progress is displayed at the top bar of the form. But if you want to cancel the Monte Carlo generation, simply closing the Automatic Puzzle Generator will work and nothing will be saved. You can open many puzzle generators at the same time, since they work independent of the Puzzle Solver.)

我们可以使用它来生成一个自定义难题.手动拼图生成器将完成工作.选择大小后,只需单击编号的按钮即可更改状态.用户可以保存他/她喜欢的任何状态.对于自定义拼图,所需的真实步长将显示为-1.(We can use this to generate a custom puzzle. The Manual Puzzle Generator will do the work. After selecting size, just clicking on the numbered buttons will change the state. The user can save any state that he/she likes. The desired true step will be displayed as -1 for custom puzzles.)

图8:自动拼图生成器在步骤100生成10x10拼图(Figure 8: Automatic Puzzle Generator generates a 10x10 puzzle at step 100)

图9:手动拼图生成器开始屏幕(Figure 9: Manual Puzzle Generator start screen)

图10:手动拼图生成器的初始状态,即目标状态(Figure 10: Manual Puzzle Generator initial state which is the goal state)

图11:手动改组的拼图示例(Figure 11: Manually shuffled puzzle sample)生成拼图后,用户可以将其加载到主GUI.只需单击"加载已保存的拼图"按钮即可加载生成的拼图.拼图加载后,拼图规格将显示在GUI主屏幕上.最初,它将在"我将解决它的选项"上打开.这个选项是(After generating a puzzle, the user can load it to the main GUI. Just clicking on the “Load A Saved Puzzle” button will load the generated puzzle. Once the puzzle is loaded, puzzle specifications will be displayed on the main GUI screen. Initially it will open on “I will solve it option”. This option is)不(not)已实施.这只是为了好玩,并且会让用户单击按钮并尝试解决他/她自己的难题.在我的程序中,难题解决的数据也保存在难题保存文件中.因此,如果生成的难题一次解决,它将显示以前解决的统计信息.无论如何,用户可以根据自己的需要解决难题.加载大拼图时,GUI会自动调整大小.在某些计算机上,GUI按钮的位置可能已移动.但是GUI可以轻松调整大小.(implemented. It would be just for fun and would let the user click on buttons and try to solve the puzzle him/herself. In my program, the puzzle solved data is also saved on the puzzle save file. So if a generated puzzle is solved once, it will display the previously solved statistics. Anyway the user can solve the puzzle as much as he/she wants. When a large puzzle is loaded, the GUI does the resizing automatically. The GUI button placement might be shifted in some computers. But the GUI can easily be resized.)

为了使程序解决难题,请单击单选按钮中的算法,然后单击"解决"按钮.对于不同的算法,按钮将以不同的颜色显示.(For making the program solve the puzzle, click on the algorithm among the radio buttons and click the “Solve” button. For different algorithms, buttons will be displayed in different colors.)

图12:手动生成的拼图加载到主GUI(Figure 12: Manually generated puzzle loaded to the main GUI)

图13:加载大型拼图时的主GUI(Figure 13: Main GUI when a large puzzle is loaded)解决难题后,其解决方案统计信息和解决方案步骤将保存到其创建的XML文件中.保存文件的示例如下:(When a puzzle is solved, its solution statistics and solution steps are saved to its created XML file. An example of a saved file is as follows:)

<?xml version="1.0" encoding="utf-8"?>
<AIMehmutluSlidingPuzzleSaveFile>
  <Puzzle.000>
    <Size>3</Size>
    <State>1,2,3,7,4,5,0,8,6</State>
    <DesiredOptimalSolutionStep>-1</DesiredOptimalSolutionStep>
    <SolvedAlgorithms>
      <BFS>
        <Solved>T</Solved>
        <SolutionTime>7</SolutionTime>
        <NoOfStoredNodes>18</NoOfStoredNodes>
        <NoOfNodeExpansion>26</NoOfNodeExpansion>
        <SolutionStep>4</SolutionStep>
        <SolutionNodes>
          <Node0>1,2,3,7,4,5,0,8,6</Node0>
          <Node1>1,2,3,0,4,5,7,8,6</Node1>
          <Node2>1,2,3,4,0,5,7,8,6</Node2>
          <Node3>1,2,3,4,5,0,7,8,6</Node3>
          <Node4>1,2,3,4,5,6,7,8,0</Node4>
        </SolutionNodes>
      </BFS>
      <DFS>
        <Solved>F</Solved>
        <SolutionTime></SolutionTime>
        <NoOfStoredNodes></NoOfStoredNodes>
        <NoOfNodeExpansion></NoOfNodeExpansion>
        <SolutionStep></SolutionStep>
        <SolutionNodes>
          <Node0>1,2,3,7,4,5,0,8,6</Node0>
        </SolutionNodes>
      </DFS>
      <IDFS>
        <Solved>F</Solved>
        <SolutionTime></SolutionTime>
        <NoOfStoredNodes></NoOfStoredNodes>
        <NoOfNodeExpansion></NoOfNodeExpansion>
        <SolutionStep></SolutionStep>
        <SolutionNodes>
          <Node0>1,2,3,7,4,5,0,8,6</Node0>
        </SolutionNodes>
      </IDFS>
      <AStarMisplacedTiles>
        <Solved>F</Solved>
        <SolutionTime></SolutionTime>
        <NoOfStoredNodes></NoOfStoredNodes>
        <NoOfNodeExpansion></NoOfNodeExpansion>
        <SolutionStep></SolutionStep>
        <SolutionNodes>
          <Node0>1,2,3,7,4,5,0,8,6</Node0>
        </SolutionNodes>
      </AStarMisplacedTiles>
      <AStarManhattan>
        <Solved>F</Solved>
        <SolutionTime></SolutionTime>
        <NoOfStoredNodes></NoOfStoredNodes>
        <NoOfNodeExpansion></NoOfNodeExpansion>
        <SolutionStep></SolutionStep>
        <SolutionNodes>
          <Node0>1,2,3,7,4,5,0,8,6</Node0>
        </SolutionNodes>
      </AStarManhattan>
    </SolvedAlgorithms>
  </Puzzle.000>
</AIMehmutluSlidingPuzzleSaveFile>

在上面保存的文件示例中,拼图生成数据位于最顶部.此外,还有专门为不同求解器算法保留的位置.一旦算法解决了难题,它的统计信息就会保存到相应的空格中.例如,以上数据使用BFS求解. BFS统计信息将保存到相应的空间,并且求解路径也将保存为状态序列.上面的难题只是一个难题.在蒙特卡洛数据中,有100个难题,每个难题名为(In the above saved file example, puzzle generation data is at the very top. Also, there are specifically reserved places for different solver algorithms. Once an algorithm solves the puzzle, its statistics is saved to the corresponding spaces. For example, the above data is solved with BFS. BFS statistics are saved to the corresponding spaces and the solution path is also saved as a sequence of states. The above puzzle is just a single puzzle. In Monte Carlo Data, there are 100 puzzles, each named as)拼图(数字)(Puzzle.(Number)).例如,Puzzle.024指的是24(. For example, Puzzle.024 refers to the 24)日(th)蒙特卡洛数据中的难题.(puzzle in the Monte Carlo Data.)

因此,如果我们将已解题的拼图加载到主GUI,它将显示先前的解统计信息.最初显示拼图的初始节点.如果解决了难题,则用户可以通过单击在其上具有向前和向后箭头的按钮来检查解决方案的路径.同时单击"播放"按钮将自动播放上一个解决方案步骤.(Therefore, if we load a solved puzzle to the main GUI, it will display the previous solution statistics. Initially the initial node of the puzzle is displayed. If the puzzle is solved, the user can check the solution path by clicking on the buttons having forward and backward arrows on them. Also clicking on the PLAY button will automatically play the previous solution step.)玩(Play)可以随时停止;手动步骤可以后退或前进.解决方案步骤完成后,播放选项将显示目标状态2秒钟,并将重新显示初始状态.(can be stopped at any time; manually steps can be taken back or forward. Once the solution steps finish, the playing option will display the goal state for two seconds and it will redisplay the initial state.)

图14:使用BFS解决了手动生成的难题(步骤(-1))(Figure 14: A manually generated puzzle (step (-1)) is solved with BFS)

图15:使用DFS解决了手动生成的难题(Figure 15: A manually generated puzzle is solved with DFS)

图16:IDFS解决了手动生成的难题(Figure 16: A manually generated puzzle is solved with IDFS)

图17:使用A 错放的磁贴启发式解决了手动生成的难题(Figure 17: A manually generated puzzle is solved with A Misplaced Tiles heuristic)

图18:使用A * Manhattan Distance启发式解决了手动生成的难题(Figure 18: A manually generated puzzle is solved with A Manhattan Distance heuristic*)如果加载了一个非常困难的难题,而您对等待解决方案感到无聊,则只需按"停止求解器"按钮即可.在GUI上工作时,将启用或禁用按钮,以避免程序的工作顺序发生冲突.(*If a very hard puzzle is loaded and you get bored of waiting for the solution, you can simply press the “Stop Solver” button. While working on the GUI, buttons will be enabled or disabled to avoid conflicts in the working order of the program.*)

图19:使用DFS解决手动生成的难题时的主GUI,可以看到以前的统计信息(Figure 19: The main GUI while resolving a manually generated puzzle with DFS, previous statistics can be seen)

图20:求解Monte Carlo运行时的主GUI(Figure 20: Main GUI while solving a Monte Carlo run)蒙特卡洛(Monte Carlo)按顺序运行.首先1(Monte Carlo run works in a sequential order. First the 1)圣(st)使用BFS,DFS,IDFS,A * Mis解决难题,最后使用A * Man算法解决难题,然后解决第二个难题.它适用于所有100个难题.用算法求解后,已解决的消息显示在GUI上.可以在图20上看到.但是请注意,BFS,IDFS,A * Mis和A * Man在较浅的步骤解决难题的速度比DFS快得多.因此,他们的消息很快就会显示和删除.因此,仅在等待算法解决时,该消息才引人注意.例如,在图20中,在使用DFS求解时显示"使用BFS求解难题".并且其他算法的消息将很快被跳过,因为它们将很快解决.它是(puzzle is solved with BFS, DFS, IDFS, A Mis, and finally with A* Man algorithms, then the second puzzle is solved. It goes for all 100 puzzles. After solving with an algorithm, a solved message is displayed on the GUI. It can be seen on Figure20. But note that BFS, IDFS, A* Mis, and A* Man solve a puzzle at shallow steps much faster than DFS. So their messages are displayed and deleted very quickly. So the message is only noticeable when waiting for an algorithm to solve. For example, in Figure 20, “Puzzle is solved with BFS” is displayed while solving with DFS. And the messages of other algorithms will be skipped very quickly since they will solve very quickly. It is*)不(*not*)一个错误.(*a bug.*)

A * Man是一个相当不错的算法.除非拼图彻底改组,否则它可以非常快速地解决拼图.在图26中,显示了A * Man的能力.在58秒内完成10x10拼图,可在7秒内解决.(A Man is a pretty good algorithm. It can solve puzzles very quickly unless the puzzle is extremely shuffled. In Figure 26, the capability of A* Man is displayed. A 10x10 puzzle at 58 true steps is solved in 7 seconds.*)

图21:A 曼哈顿距离启发式功能测试(Figure 21: Capability test of A Manhattan Distance heuristic)## 4.已实施的补充计划(4. Implemented Complementary Programs)

4.1. C#中的数据转换器(4.1. Data Converter in C#)

为了在MATLAB上绘制性能图,需要使用MATLAB提取解决方案统计数据.为了简化在MATLAB中的工作,我编写了一个小型独立程序,用于将XML解析的Monte Carlo数据转换为更简单的文本格式.我为算法比较和大小比较编写了同一转换程序的不同变体.与A 的大小比较不是很好的解释.我将在下一节中提供有关它的详细信息,因此我也使用BFS进行了大小比较.(In order to plot performance plots on MATLAB, solution statistics data need to be extracted with MATLAB. In order to simplify work in MATLAB, I wrote a small standalone program for converting XML solved Monte Carlo data to simpler text format. I wrote different variations of the same conversion program for algorithm comparison and size comparison. Size comparison with A was not very explanatory. I will give details in the next section about it, so I also performed size comparison with BFS.)

图22:用于算法比较的XML文本转换器和数据解码器蒙特卡洛数据(Figure 22: XML to text converter and data decoder for algorithm comparison Monte Carlo data)

图23:XML到文本的转换器和数据解码器,用于大小比较采用A * Man算法的Monte Carlo数据(Figure 23: XML to text converter and data decoder for size comparison Monte Carlo data with A Man algorithm*)

图24:用于大小比较的XML到文本转换器和数据解码器,带BFS算法的蒙特卡洛数据(Figure 24: XML to text converter and data decoder for size comparison Monte Carlo data with BFS algorithm)在解决了100种难题的蒙特卡洛数据之后,使用上述程序将XML文件转换为文本.将解码后的数据文件的将来名称写到小程序上的文本文件上,然后单击GUI上唯一可用的按钮.它将要求您在XML文件中找到已解决的Monte Carlo数据.给出XML文件后,它将在可执行文件所在的目录中生成解码后的文本文件.文本文件准备就绪后,它们将被馈送到将绘制数据的MATLAB函数中.(After solving various 100 puzzle Monte Carlo data, the XML files are converted to text with the above programs. Write the future name of the decoded data file on to a text file on the mini program, then click on the only available button on the GUI. It will ask you to locate the solved Monte Carlo data in an XML file. Once the XML file is given, it will generate the decoded text file in the directory in which the executable file resides. Once the  text files are ready they will be fed to MATLAB functions that will be plotting the data.)

4.2. MATLAB中的数据绘图仪(4.2. Data Plotter in MATLAB)

为了获得漂亮的图,我编写了MATLAB函数,该函数将使用许多Monte Carlo运行的解码文本数据并提取信息.函数只会要求包含Monte Carlo运行的目录.最后,它将给出情节.对于不同的数据运行,需要在MATLAB函数中进行小的参数更改.的MATLAB(In order to have nice plots, I wrote MATLAB functions that will take many Monte Carlo run decoded text data and extract the information. Functions will only ask for directory containing Monte Carlo runs. Finally, it will give the plots. For different data runs, small parameter changes in the MATLAB functions are necessary. MATLAB)**.m(.m)**随此报告一起提交的文件夹中也提供了包含MATLAB函数的文件.由于MATLAB函数相当冗长,因此在此书面报告中将不会提供代码.(files containing MATLAB functions are also given in the folder submitted with this report. Since MATLAB functions are quite lengthy, code will not be presented in this written report.)

5.结果(5. Results)

5.1.算法分析(5.1. Algorithms' Analysis)

为了进行算法比较,在所需的真实步骤5\10\15\20和25上创建了100个3x3拼图.使用五种不同的算法解决了500个拼图,即将2500个解决方案用作数据库.所有创建的谜题均未按照所需的步骤进行,因为它们是按照"家庭定义"工作表中所述的深度优先方式创建的.但是将它们精细地分成真实的步长数组,并检查数据是否包含真实的步长.所得数据的步长为4到25(4\5\6\7\8\9\10\11\12\13\14\15\16\17\18\19\20\21\22\23 ,24,25).所有数据都绘制在M​​ATLAB图形中(For algorithm comparison, 100 3x3 puzzle lots are created at desired true steps 5, 10, 15, 20, and 25. A total of 500 puzzles are solved with five different algorithms, i.e., a 2500 solution is used as the database. All created puzzles are not at the desired steps since they are created in a depth first fashion as explained in the “Take Home Definition” sheet. But they are delicately separated into true step arrays and data is examined for true steps. The resulting data has steps varying from 4 to 25 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25). All data is plotted on the MATLAB graphs in)蓝点(blue dots).但是,当在真实步长处的样本数超过设置为20的阈值时,在同一真实步长处的合奏将被视为值得推力的合奏并进行平均并标记为(. But when the number of samples at true step exceeds the threshold value which was set to 20, the ensemble at the same true step is considered as a thrust worthy ensemble and averaged and marked with)红色圆圈(red circles)在情节上.(on the plots.)

该页面的其余部分有意留为空白,因此算法结果可以在1页中看到.(The rest of the page is intentionally left blank so the result of an algorithm can be seen in 1 page.)

BFS算法为所有结果提供指数结果.注意存储的节点数据中的饱和现象.原因是我在BFS算法中使用了历史记录.当历史记录几乎覆盖了整个搜索空间时,由于所有其他节点都已在历史记录中,即它们已经在较低级别访问过,因此只能存储所有扩展节点的一小部分.(The BFS algorithm gives exponential results for everything. Notice the saturation like phenomenon in the stored node data. The reason is the fact that I use history in the BFS algorithm. When the history covers almost the entire search space, only a small portion of all expanded nodes can be stored because all others are already in the history, i.e., they are already visited at a lower level.)

图25:3x3拼图大小下的BFS时间表现(Figure 25: BFS time performance at 3x3 puzzle size)

图26:3x3拼图大小的BFS节点扩展(Figure 26: BFS node expansion at 3x3 puzzle size)

图27:3x3拼图大小的BFS节点存储(Figure 27: BFS node storage at 3x3 puzzle size)对于DFS,请注意步长无关紧要. DFS搜索整个搜索空间,或者它很快找到目标.但是,将数据平均后,DFS性能几乎相同.这个结果与预期的一样.在比较数据中,DFS似乎不如其他数据,但这主要是因为我们通常以非常低的步进解决方案应用数据.如果我们不解之谜,BFS解决时间将持续增加,但DFS平均解决时间仍将是搜索整个搜索空间所需时间的一半.其他属性也一样.(For DFS, notice that the step size does not matter so much. DFS searches the entire search space or it finds the goal very quickly. But when the data is averaged, the DFS performance is almost the same. This result is just as expected. In the comparative figures, DFS seems to be inferior to others but that is mainly because of the fact that we usually apply data at very low step solution. If we would give puzzles at higher step, the BFS solution time would keep increasing but the DFS average solution time would still be almost half the time required for searching the entire search space. The same also applies for other attributes.)

图28:3x3拼图大小下的DFS时间性能(Figure 28: DFS time performance at 3x3 puzzle size)

图29:3x3拼图大小的DFS节点扩展(Figure 29: DFS node expansion at 3x3 puzzle size)

图30:3x3拼图大小的DFS节点存储(Figure 30: DFS node storage at 3x3 puzzle size)与BFS相比,IDFS在更长的时间内找到了解决方案.在IDFS中,节点扩展速率和求解时间均比BFS指数级且差.但是,对于存储节点,IDFS非常优越.它仅在找到解决方案的深度数附近存储节点.因此,对于真正的步骤难题,内存使用情况几乎与步骤成线性关系. IDFS比BFS需要更多的CPU能力,但是您可以从RAM中保存.(IDFS find the solution in a longer time when compared to BFS. In IDFS, node expansion rate and solution times are both exponential and worse than BFS. However, when it comes to stored nodes, IDFS is extremely superior. It only stores nodes around the number of depth the solution is found. So, with true step puzzles, memory usage is almost linear with steps. IDFS requires more CPU power than BFS but you can save from RAM.)

图31:3x3拼图大小下的IDFS时间性能(Figure 31: IDFS time performance at 3x3 puzzle size)

图32:3x3拼图大小的IDFS扩展节点(Figure 32: IDFS expanded nodes at 3x3 puzzle size)

图33:IDFS以3x3拼图大小存储的节点(Figure 33: IDFS stored nodes at 3x3 puzzle size)明智的搜索在整体性能上要比不明智的搜索好得多.尽管IDFS存储的节点数较少,但其解决方案时间永远无法与A 解决方案时间竞争. A 的统计信息仍然是指数的.但是存储节点和扩展节点的级别比BFS和DFS好得多.我们可以轻易得出结论,知情搜索要比不知情的搜索好得多.(Informed searches perform much better than uninformed searches on overall performance. Although IDFS stores less number of nodes, its solution time can never compete with the A solution time. Statistics are still exponential for A. But the level of stored nodes and expanded nodes is much better than BFS and DFS. We can easily conclude that informed search is much better than uninformed ones.)

图34:拼图大小为3x3时的A 错误时间表现(Figure 34: A Mis time performance at 3x3 puzzle size)

图35:拼图大小为3x3的A 错误扩展节点(Figure 35: A Mis expanded nodes at 3x3 puzzle size)

图36:3 * 3拼图大小的A 错误存储的节点(Figure 36: A Mis stored nodes at 3x3 puzzle size)在A * Manhattan距离数据中,我们可以得出结论,一种更好的启发式方法是为实际最佳解决方案成本提供更接近的值.在A 曼哈顿距离情况下,求解时间不会提供太多信息.我注意到数据有些奇怪的周期性增加.这可能是由于操作系统的线程管理所致.但是扩展后的节点和存储的节点数据正确地给出了指数趋势. A * Man在滑动拼图解决方案中证明了其有效性.(In the A Manhattan distance data we can conclude that a better heuristic is the one that gives closer values to the actual optimal solution cost. The solution time in the A Manhattan distance case does not give much information. I noticed some strange periodic increase in the data. That can be due to the Operating System’s thread management. But the expanded nodes and stored nodes data give the exponential trend correctly. A* Man proves its effectiveness in the sliding puzzle solution.*)

图37:拼图大小为3x3时的A 人工表现(Figure 37: A Man time performance at 3x3 puzzle size)

图38:3 * 3拼图大小的A * Man扩展节点(Figure 38: A Man expanded nodes at 3x3 puzzle size*)

图39:3 * 3拼图大小的A 人存储节点(Figure 39: A Man stored nodes at 3x3 puzzle size)### 5.2.拼图大小分析(5.2. Puzzle Size Analysis)

为了观察同一算法上的拼图大小效果,会在特定的真实步骤中创建各种大小(3x3\4x4…10x10)的100个拼图.通过算法求解它们并绘制统计数据.所有数据都绘制在M​​ATLAB图形中(For observing puzzle size effect on the same algorithm, various sized (3x3, 4x4 … 10x10) 100 puzzle lots are created at a specific true step. They are solved with an algorithm and statistics are plotted. All data is plotted on the MATLAB graphs in)蓝点(blue dots).但是,当真实步长的样本数和指定大小的阈值保持在设置为20的阈值之上时,同一真实步长的合奏将被视为值得推力的合奏,并进行平均并标记为(. But when the number of samples at true step and specified size remain above the threshold value which was set to 20, the ensemble at the same true step is considered as a thrust worthy ensemble and averaged and marked with)红色圆圈(red circles)在情节上.(on the plots.)

产生的困惑并不总是在所需的步骤.因此,我只是丢弃了不在所需步骤的数据.因此,将特定步骤的合奏大小和大小从100减少到较小的数字.小拼图尺寸的下降幅度很大.但是请注意,可靠的数据用红色标记.(The generated puzzled was not always at the desired step. So I just discarded the data which was not at the desired step. So the ensemble size at a specific step and size is reduced from 100 to smaller numbers. The drop was drastic in small puzzle sizes. But note that reliable data is marked with red.)

首先,我以20个步骤对A * Man进行了实验.我无法得出有意义的结果,因此以35个步骤重复了A * Man的测试.但是仍然无法提出合理的解释.最后,我用10步拼图和BFS算法重复了测试.我将包括我所有的实验和解释.(First I experimented with A Man at 20 steps. I could not conclude meaningful results and repeated the test with A* Man at 35 steps. But still could not come up with reasonable explanation. Finally, I repeated the test with 10 step puzzles and the BFS algorithm. I will include all of my experiments and my explanations.*)

该页面的其余部分有意留为空白,以便可以在一页中显示与同一步骤相对应并用相同算法求解的难题.(The rest of the page is intentionally left blank so that puzzles corresponding to the same step and solved with the same algorithm can be shown in one page.)

对于拼图大小效果观察,A * Man算法没有给出非常有意义的结果.除了拼图大小为4的数字略高之外,我无法捕获任何数据趋势.似乎对于A * Man来说,更乱洗的拼图更难解决.即使对于大小为4的谜题,搜索空间较小,但与在相同真实步骤中的较大谜题相比,A 仍会更努力地获得结果.(The A Man algorithm did not give very meaningful results for puzzle size effect observation. I could not catch any data trend except slightly high numbers for puzzle size 4. It seems that more shuffled puzzles are harder to solve for A Man. Even though the search space is smaller for size 4 puzzles, A* worked harder to get to the result when compared to the larger puzzles at the same true step.*)

图40:A 人存储的节点数与第20步的拼图大小(Figure 40: A Man stored nodes vs. puzzle size at 20 step)

图41:20步时的A 工时表现与拼图大小(Figure 41: A Man time performance vs. puzzle size at 20 step)

图42:20步时A 人工扩展节点与拼图大小(Figure 42: A Man expanded node vs. puzzle size at 20 step)为了确认A 的结果,我在35步的Monte Carlo Runs中执行了相同的测试. A 似乎不受拼图大小的影响很大.(In order to confirm my results with A, I performed the same test at 35 step Monte Carlo Runs. A does not seem to be affected by the puzzle size a lot.)

图43:35步时的A 工时表现与拼图大小(Figure 43: A Man time performance vs. puzzle size at 35 step)

图44:35步时A 人工展开的节点与拼图大小的关系(Figure 44: A Man expanded node vs. puzzle size at 35 step)

图45:A 人工存储节点与第35步的拼图大小(Figure 45: A Man stored node vs. puzzle size at 35 step)然后,我对BFS进行了相同的测试.我注意到了用于解谜统计的线性指数趋势.我可以得出结论,这是由于有效指数在增加.我的意思是:当拼图大小为3且角落处为空白(4倍)时,该状态具有两个后继;当空白在边缘(4次)时,该状态具有3个后继;当中间为空白时,状态有4个后继(1次).有效指数因子约为2.6.如果我们认为继任者之一引起了循环,那么我的算法将不会将其存储为有效指数因子减小到1.6.但是,当拼图大小为4且角落处为空白(4倍)时,该状态有2个后继对象;当空白在边缘(8次)时,该状态有3个后继;当中间为空白时,该状态有4个后继(4次).有效指数因子为3.如果我们认为继任者中的一个正在引起循环,则当有效指数因子减小到2时,我的算法将不会存储它.因此,我可以得出结论,拼图大小的增加会增加有效指数因子,因此存储量更大节点,更多扩展的节点和更长的求解时间对于较大的难题似乎是合理的.(Then I performed the same test with BFS. I noticed linear-exponential like trends for puzzle solving statistics. I can conclude that this is due to the fact that effective exponential is increasing. What I mean is that: when puzzle size is 3 and blank at the corner (4 times), the state has two successors; when blank is at the edge (4 times), the state has 3 successors; when blank is at the middle, state has 4 successors (1 time). The effective exponential factor is approximately 2.6. If we consider that one of the successors is causing a loop, my algorithms will not store it effective exponential factor decreases to 1.6. But, when puzzle size is 4 and blank at the corner (4 times), the state has 2 successors; when blank is at the edge (8 times), the state has 3 successors; when blank is at the middle, the state has 4 successors (4 times). The effective exponential factor is 3. If we consider that one of the successors is causing a loop, my algorithms will not store it if effective exponential factor decreases to 2. So I can conclude that puzzle size increase increases the effective exponential factor hence more stored nodes, more expanded nodes, and longer solution time is plausible for larger puzzles.)

图46:10步时BFS时间表现与拼图大小(Figure 46: BFS time performance vs. puzzle size at 10 step)

图47:10步时BFS扩展节点与拼图大小(Figure 47: BFS expanded nodes vs. puzzle size at 10 step)

图48:BFS存储的节点与第10步的拼图大小(Figure 48: BFS stored nodes vs. puzzle size at 10 step)## 六,结论(6. Conclusion)

我对滑动拼图问题实施了五种不同的算法.我从这次带回家检查的实施中获得的经验非常宝贵.现在,我已经很清楚这些算法的实际行为.(I have implemented five different algorithms on the sliding puzzle problem. The experience I gained from the implementation of this take home examination is very valuable. Now I am well aware of the real life behavior of these algorithms.)

所有算法都能够找到解决方案.此外,除DFS外,所有算法都可以在我的实现中找到最短(最佳)的解决方案.我的带有历史节点的拼图表示法大大提高了算法的性能,并使该项目的DFS解决方案成为可能.(All algorithms are able to find solutions. Furthermore, all algorithms except DFS can find the shortest (optimal) solution in my implementation. My puzzle representation with history nodes increased the performance of algorithms significantly and made the DFS solution possible for this project.)

BFS的指数特征微不足道,并且在此项目中可以非常清楚地观察到它们.(Exponential characteristics of BFS were trivial and they are observed very clearly on this project.)

同样,DFS的规格很明显,即平均搜索空间的一半就可以找到解决方案.如果我们可以在更高的实际步骤上解决问题,则DFS会比BFS更快地找到解决方案,因为BFS会搜索整个搜索空间,而DFS会平均搜索一半.(Also, the specification of DFS to find the solution at the average of searching half of the search-space was very obvious. If we could give problems at higher true steps, DFS would find the solution quicker than BFS, since BFS would be searching for the entire search space and DFS would be searching for half of it on the average.)

对于我来说,IDFS的重要性还不是很清楚,但是我注意到IDFS以最少的存储需求解决了这个问题,但是却消耗了CPU能力和时间.(The importance of IDFS was not very clear for me in the class but I noticed that IDFS solves the problem with minimal storage requirements at the expense of CPU power and time.)

不出所料,明智的搜索算法在整体解决方案性能上的表现要好得多.具有更好的启发式效果也可以非常明显地提高性能.(As expected, informed search algorithms performed much better on overall solution performance. Having a better heuristic also increased the performance very clearly.)

最后获得的程序使我很满意.到目前为止,它是我编写的最大的代码,其性能确实令人满意.(The program I obtained at the end well satisfied me. It has been the largest piece of code that I have written so far and its performance really is satisfying.)

7.致谢(7. Acknowledgement)

我要感谢OrkunÖgücü对MATLAB数据绘图的支持以及SerhatVarolgünes对C#中多线程的支持.(I would like to thank Orkun Ögücü for his support in MATLAB data plotting and Serhat Varolgünes for his support in multi-threading in C#.)

8.参考(8. References)

[1]人工智能:一种现代方法(3([1] Artificial Intelligence: A Modern Approach (3)rd(rd)版); Stuart Russell,Peter Norvig;(Edition); Stuart Russell, Peter Norvig;) 培生(Pearson)人工智能教育系列(Pearson education series in artificial intelligence) .(.)

9.附录(9. Appendix)

为便于在MATLAB中进行绘图而获得的解码算法比较蒙特卡洛文本数据采用以下格式. " P"代表谜题; " 000"," 001"代表拼图编号; " B"," D"," I"," A"," M"分别代表BFS,DFS,IDFS,A * Mis,A * Man. " ST"代表存储的节点; " SS"代表解决步骤; " EN"扩展节点; " SN"存储的节点.首字母后的数字给出该值的正确数字.蒙特卡洛文本解码的数据实际上是100个难题的,但此处仅给出了3个难题的统计信息.(The decoded algorithm comparison Monte Carlo text data that is obtained for easier plotting in MATLAB is in the following format. “P” for puzzle; “000”, “001” stands for puzzle number; “B”, “D”, “I”, “A”, “M” stand for BFS, DFS, IDFS, AMis, AMan, respectively. “ST” stands for stored node; “SS” stands for solution step; “EN” expanded nodes; “SN” stored nodes. The numbers after initials give the proper number for that value. The Monte Carlo text decoded data was actually for 100 puzzles but only 3 puzzle statistics are given in here.)

P 000 B ST 31 SS 5 EN 43 SN 30
P 000 D ST 39718 SS 129 EN 181323 SN 59444
P 000 I ST 0 SS 5 EN 110 SN 7
P 000 A ST 0 SS 5 EN 7 SN 9
P 000 M ST 0 SS 5 EN 6 SN 7
P 001 B ST 0 SS 5 EN 50 SN 42
P 001 D ST 36442 SS 213 EN 181248 SN 59439
P 001 I ST 0 SS 5 EN 92 SN 7
P 001 A ST 0 SS 5 EN 6 SN 7
P 001 M ST 0 SS 5 EN 6 SN 7
P 002 B ST 15 SS 5 EN 58 SN 41
P 002 D ST 0 SS 13 EN 14 SN 12
P 002 I ST 0 SS 5 EN 77 SN 6
P 002 A ST 0 SS 5 EN 6 SN 7
P 002 M ST 0 SS 5 EN 6 SN 7
P 003 B ST 0 SS 5 EN 49 SN 42
P 003 D ST 69888 SS 215 EN 181247 SN 59439
P 003 I ST 0 SS 5 EN 94 SN 7
P 003 A ST 0 SS 5 EN 6 SN 7
P 003 M ST 0 SS 5 EN 6 SN 7

尺寸比较数据只有一种算法.但它的末尾也有尺寸信息,以" S"表示.以下解码的蒙特卡洛数据属于4号拼图.其中仅显示6个,但一个文件包含100个拼图的数据.(The size comparison data has only one algorithm. But it also has size info denoted by “S” at the very end. The following decoded Monte Carlo Data belongs to size 4 puzzles. Only 6 of them are displayed here but a file contains data for 100 puzzles.)

P 000 M ST 31 SS 31 EN 771 SN 801 S 4
P 001 M ST 0 SS 25 EN 274 SN 274 S 4
P 002 M ST 15 SS 25 EN 319 SN 323 S 4
P 003 M ST 1030 SS 29 EN 10124 SN 10256 S 4
P 004 M ST 172 SS 29 EN 2996 SN 3193 S 4
P 005 M ST 0 SS 25 EN 317 SN 321 S 4

在MATLAB中用于绘图的所有原始解码数据都可以在(All original decoded data that are used for plotting in MATLAB can be found in the)**的MATLAB(MATLAB)**该项目随附的文件夹.(folder presented with this project.)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。