我的学校作业是制定迭代深化算法来解决 6x6 高峰期难题。我选择使用 JavaScript 是因为我需要练习。然而,我在大幅优化算法时遇到了麻烦。
我尝试解决一个谜题,该谜题的解法在树中有 8 个级别,我发现我访问了 7,350,669 个节点,我的计算机花了近 13 分钟才能解决。
我正在寻找理解算法本身的技巧和帮助。
我创建了 2 个类 - Node 和 Vehicle。这些的实现可能是问题的一部分:
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
}
}
我的假设是否正确,同时拥有网格的“二维”数组和车辆数组是一种矫枉过正?在检查可能的运动时,我会迭代车辆数组,但使用网格来快速检查车辆前方是否有自由路。我将回到我所看到的问题。
我无法公开发布该算法的代码,但以下是我如何理解 IDDFS 并实现该算法:
- 检查当前节点是否为最终状态,如果是则将其添加到解决方案数组中并返回 true。
- 否则检查是否达到 maxDepth,如果达到则返回 false。
- 如果不是,则为处于此状态的每个车辆创建新节点,用于它们可以进行的所有移动(上一次移动的移动除外)
- 访问您刚刚创建的所有子项(返回第 1 步),如果它们返回 false,则将其删除。
- 如果没有一个子节点显示为最终状态,则返回父节点并探索其邻居。否则返回真实的链式 react 。
- 重复直到找到最终状态。如果回到顶部,则将 maxDepth 加 1 并重复整个过程。
我发现的一个问题是我的数据结构可能有点复杂。由于 JavaScript 将对象和对象数组作为引用传递,因此必须使用以下方法深度复制它们:
JSON.parse(JSON.stringify(node))
这里的主要问题是——我错过了什么吗?删除“坏”子节点并在迭代加深算法中一次又一次地遍历整个树是否正确,还是我误解了这一点?它们是否应该被标记为“已检查”,然后返回,然后稍后再传递它们,这样就不必再次生成整个树?
最佳答案
首先,您必须分析代码执行情况。否则这只是猜测,您可能会花费大量时间更改代码以获得 0.1% 的 yield 。
记住上述内容,当您知道对象的结构(如此处的情况)时,通过手动复制每个属性而不是使用 stringify
,您可以更快地克隆对象。
关于javascript - 在 JavaScript 中优化迭代深化高峰时间算法时遇到问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36099478/