我已经实现了DFS搜索8个益智游戏,但是由于某种原因,我无法设法使它正常工作,我的堆栈不断增加并为我的8添加可能的动作益智游戏,但它永远不会减少答案,我不知道它是否正常,但这是我的代码,以防有人可以帮助我。
我知道,代码没有完全优化,我只想知道为什么它不应该作为DFS,谢谢。
function depthFirstSearch(currentState, finalState)
{
var stack = [];
var visited = [];
delete currentState["prev"];
stack.push(currentState);
while(stack.length)
{
var node = stack.pop();
visited.push(node);
if(compare(node, finalState))
{
return visited;
}
else
{
var successors = getSuccessors(node);
for(var i = 0; i < successors.length; i++)
{
delete successors[i]["prev"];
}
var realSuccessors = [];
for(var i = 0; i < visited.length; i++)
{
for(var j = 0; j < successors.length; j++)
{
if(compare(successors[j], visited[i]))
{
continue;
}
else
{
realSuccessors.push(successors[j]);
}
}
}
for(var i = 0; i < realSuccessors.length; i++)
{
stack.push(realSuccessors[i]);
}
console.log(stack.length);
}
}
}
我要回答自己,因为我意识到,考虑到我深度遍历我的图形的组合数可能会导致我达到无限或长的组合,并且永远不会达到解决方案由于我只是朝一个方向朝着一个方向前进,因此我考虑了进行迭代的DFS,该迭代dfs会按级别穿越每个孩子。