-
7 votesanswersviews
8难题：可解决性和最短的解决方案
我使用广度优先搜索构建了一个8拼图解算器 . 我现在想要修改代码以使用启发式 . 如果有人能回答以下两个问题，我将不胜感激： Solvability 我们如何确定8拼图是否可以解决？ （给定起始状态和目标状态）这就是维基百科所说的： 不变量是所有16个方格的排列的奇偶校验加上从右下角开始的空方格的出租车距离（行数加上列数）的奇偶校验 . 不幸的是，我无法理解这意味着什么 . 理解起来有点复杂 ... -
4 votesanswersviews
我的A *搜索8-Puzzle有什么问题？
我试图使用这些启发式的A *搜索来解决8-Puzzle： - h1：错位瓦片的数量 - h2：总曼哈顿距离 - h3：以上的总和 移动的图块称为0 . 我的目标是解决这些问题： 4 1 2 5 8 3 7 0 6 和 8 6 7 2 5 4 3 0 1 我遇到的问题是，通过我目前的A *实现，它能够解决第一个问题，但不能解决第二个问题 . 所以请帮助我理解我的A *代码有什么问题： in... -
16 votesanswersviews
什么是解决8拼图问题的有效方法？
8拼图是一个有9个位置的方板，由8个编号的瓷砖和一个间隙填充 . 在任何时候，与间隙相邻的瓦片可以移动到间隙中，从而产生新的间隙位置 . 换句话说，间隙可以与相邻（水平和垂直）瓦片交换 . 游戏中的目标是从任意配置的瓷砖开始，然后移动它们以使得按升序排列的编号瓷砖在电路板的周边运行或从左到右排序，左上角为1 - 手的位置 . 我想知道什么方法可以有效地解决这个问题？ -
1 votesanswersviews
用Java编写的* 8拼图不适用于某些初始状态
我不得不使用A *算法和两个启发式实现一个8拼图求解器 . 第一个启发式只是不合适的瓦片的总和，第二个是目标状态的所有瓦片的曼哈顿距离的总和，我们将其定义为： 0 1 2 3 4 5 6 7 8 我们给出了不同深度的样本测试 . 我使用第一个启发式的实现传递了所有这些情况，但是第二个启发式一旦达到14的深度就不会通过某些测试用例： (52) !Test Case failed! for init... -
1 votesanswersviews
用Java解决n-puzzle
我正在尝试实现一个解决n-puzzle problem的程序 .我在Java中编写了一个简单的实现，它具有一个问题状态，其特征在于表示tile的矩阵 . 我还能够自动生成给出起始状态的所有状态的图形 . 然后，在图表上，我可以使用BFS来查找目标状态的路径 .但问题是我的内存不足，甚至无法创建整个图形 . 我尝试了2x2瓷砖，它的工作原理 . 还有一些3x3（它取决于起始状态和图中有多少个节点） ...