0

I've never used DFS before and I was wondering how you could use one to find the smallest product of a path if you were to traverse through the following "tree": 

        3
      4   5
    7   6   4
  3   5   7   8
1   2   3   4   4

See comments below to clear any confusion(:

4

1 回答 1

0

您需要构建一个有向图，其中节点是数字，每个节点有 2 条边到下一级的数字/节点。这个特定问题中的图将是一个有向无环图。

然后，您只需在构建的图上运行 DFS。但是，您不会跟踪/检查您之前是否访问过某个节点，因为您想重新访问它们。相反，您只需要检查当前节点是否具有 0 out-degree或节点（因为底部的节点将具有 0 out-degree），并在到达底部的节点时更新当前最小值。（您还可以跟踪当前深度，并在达到深度时更新当前最小值）。我们可以针对这个特定问题这样做，因为所有乘积都是恰好 5 个数字相乘的结果，每个级别一个。

我上面描述的称为 DFS 的树搜索变体，与您跟踪之前是否访问过节点的普通图形搜索变体相比。当图中存在循环时，树搜索 DFS 会卡住，但由于这是一个有向无环图，我们不会遇到这样的问题。

如果这些数字都是非负数，我们可以观察到：无论我们如何从根到达一个节点，前面的最优路径每次都将是相同的。

在这种情况下，从底部节点向后工作会更快。对于与同一“父”节点相邻的每一对，选择较小的一对并与“父”节点相乘。一直这样做，直到你到达根节点，你就会得到结果。

如果数字可以是正数或负数或 0，则需要跟踪 4 个数字：具有最大和最小绝对值的负积，最大和最小正积。并且你还需要跟踪是否可以形成 0 产品。2 个最大的绝对值是针对正 x 负的情况。2 个最小的绝对值适用于正 x 正或负 x 负的情况。在算法开始时，所有这 5 个字段都是未定义的。

如何更新的细节留给读者。检查结果的顺序是：负数绝对值最大，0，正数绝对值最小。如果该字段未定义，则跳过它并检查下一个。

于 2013-02-26T06:54:16.103 回答