在 JavaScript 中优化 Iterative Deepening Rush Hour 算法时遇到问题

Question

我有一项学校作业要求制定迭代加深算法来解决 6x6 高峰时间拼图。我选择使用 JavaScript of all things 因为我需要练习。然而，我在优化算法方面遇到了麻烦。

我试图解决一个谜题，它的解决方案在树中有 8 个级别，我发现我访问了 7,350,669 个节点，我的计算机花了将近 13 分钟来解决。

我正在寻找技巧和帮助来理解算法本身。

我制作了 2 个类- 节点和载具。这些的实施可能是问题的一部分：

class Vehicle {
  constructor(x,y,length,horizontal){
    this.x = x; //X position of the upper/left block of the vehicle
    this.y = y; //y postion
    this.length = length; //length of the vehicle
    this.horizontal = horizontal; //boolean - false if vertical
  }
}

class Node {
  constructor(grid,vehicles,moved,depth){
    this.grid = grid; //A 6x6 char array grid
    this.vehicles = vehicles; //array of vehicles on the game board
    this.moved = moved; //index of vehicle moved in last turn
    this.depth = depth; //Depth of this node
  }
}

我的假设是否正确，既有一个 "two-dimensional" 阵列用于网格，又有一个车辆阵列是不是有点矫枉过正？在检查可能的移动时，我遍历了车辆数组，但使用 gird 来快速检查车辆是否有前方的自由路。我将回到我看到的问题。

我不能post公开算法的代码，但这是我理解 IDDFS 和实现算法的方式：

检查当前节点是否为最终状态，如果是则将其添加到解决方案数组并且return为真。
否则检查您是否达到了 maxDepth，如果是 return false。
如果不是，则为处于此状态的每辆车辆创建新节点，用于它们可以进行的所有移动（上次移动的移动除外）
访问您刚刚创建的所有子项（返回步骤 1），如果它们 return 为假，则将其删除。
如果 none 个子节点显示为最终状态，则返回父节点并探索其邻居。否则 return 真正的连锁反应随之而来。
重复直到找到最终状态。如果回到顶部，则将 maxDepth 增加 1 并重复整个过程。

我看到的一个问题是我的数据结构可能有点复杂。因为 JavaScript 将对象和对象数组作为引用传递，所以必须使用以下方法对它们进行深度复制：

JSON.parse(JSON.stringify(node))

这里的主要问题是——我错过了什么吗？删除 "bad" 个子节点并在迭代加深算法中一次又一次地遍历整个树是否正确，还是我误解了？它们是否应该被标记为 "checked" 然后 returned 以便稍后通过它们以便不必再次生成整棵树？

Answer 1

首先，您必须分析代码执行情况。否则就是猜测，您可能会花费大量时间更改代码以获得 0.1% 的收益。

牢记以上几点，当您知道对象的结构（就像这里的情况一样）时，您可以通过手动复制每个属性而不是使用 stringify.[=11 来更快地克隆对象=]

在 JavaScript 中优化 Iterative Deepening Rush Hour 算法时遇到问题

Having trouble optimizing Iterative Deepening Rush Hour algorithm in JavaScript

javascript

arrays

algorithm

iterative-deepening