1

所以我为节点树实现了标准深度优先搜索，其中每个节点都封装了我正在解决的问题的状态，我还添加了下面的方法来检查我不会通过扩展一个节点来重复移动封装了我已经在之前的某个节点中检查过的状态。我的问题是：这种方法是否以某种方式改变了算法的时间或空间复杂度，或者它们仍然是 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;
    }
4

1 回答 1

1

空间复杂度

checkForRepeatedMoves似乎不会生成新的对象分配或在堆栈上堆积调用，因此它应该保持 DFS 的整体空间复杂度不变。

时间复杂度

让我们假设checkForRepeatedMoves为树的每个节点调用并且树在每个级别都完全填充（松散地说）。

让我们调用c工作单元来检查正在与父节点进行比较的节点的状态。假设c是恒定的。

让我们分解树的每个级别的成本，从 1（根）到m.

  • 级别1：（0为 1 个节点访问了 0 个父节点）
  • 级别2：（为根的孩子 b.c访问了 1 个父级）b
  • 级别3：（为节点2.b^2.c访问了 2 个父b^2节点）
  • ...
  • 级别m + 1：（为节点m.b^m.c访问了 m 个父b^m节点）

总成本C(m)可以写为总和C(m) = c.S(m)在哪里：S(m)

[1]：S(m) = 0 + b + 2.b^2 + ... + m.b^m

让我们找到 的渐近等价物S(m)。首先，让我们观察一下

[2]：b.S(m) = 0 + b^2 + 2.b^3 + ... + m.b^(m+1)

从 (2) 中减去 (1) 得出：

[3]：(b - 1).S(m) = 0 - b - b^2 - b^3 - ... - b^m + m.b^(m+1)

我们可以在哪里识别几何和 b + b^2 + ... + b^m，这简化为 [4]: (b^(m+1) - 1) / (b - 1) - 1。

将等式 [3] 右侧大小中的几何和替换为 [4]，然后通过递减渐近优势对项进行分组，得到

(b - 1).S(m) = m.b^(m+1) + p.b^m + q其中p和q是关于 的常数m。

当m -> +Inf, 我们有(b - 1).S(m)~ (等价于) m.b^(m+1),

所以S(m) ~ [m/(b - 1)].b^(m+1) ~ m.b^m

因此成本等于C(m) ~ c.m.b^m

所以C(m) = O(m.b^m)。

由于在 时m.b^m“占主导地位” ，因此对于传统的 DFS ，算法的整体复杂度变为。因此增加了时间复杂度。b^mm -> +InfO(m.b^m)O(b^m)

于 2017-11-27T22:26:15.877 回答