所以我为节点树实现了标准深度优先搜索,其中每个节点都封装了我正在解决的问题的状态,我还添加了下面的方法来检查我不会通过扩展一个节点来重复移动封装了我已经在之前的某个节点中检查过的状态。我的问题是:这种方法是否以某种方式改变了算法的时间或空间复杂度,或者它们仍然是 DFS O(b^m) 和 O(bm) 的典型方法(这里 b - 分支因子和 m - 最大深度)。
//additional method which prevents us from repeating moves
public boolean checkForRepeatedMoves(Node node) {
Node nodeBeingChecked = node;
//if the current node's state is the same as the state of its parent or its parent's parent and so on.. then we are repeating a move
while (node.getParent() != null) {
if(node.getParent().getState().isEqualTo(nodeBeingChecked.getState())) {
return true;
}
node = node.getParent();
}
//if we have reached the root and no repetition is detected - return false
return false;
}