0

我需要获取树的所有可能路径，所以我实现了这样的 DFS：

void bisearch(std::vector<int> path, int steps,
                           int node, std::vector<std::vector<int>> *paths) {
  int sum = 0;
  if (path.size() == steps) {
    for(std::vector<int>::iterator it=path.begin(); it != path.end(); ++it) {
        sum += (*it);   
    }
    if (sum == node)
        paths->push_back(path);
  }
  else {
    std::vector<int> uPath(path);
    uPath.push_back(1);
    bisearch(uPath, steps, node, paths);
    std::vector<int> dPath(path);
    dPath.push_back(0);
    bisearch(dPath, steps, node, paths);
  }
}

上面的代码为我提供了到某个结束节点的所有路径，以获取长度为“步骤”的树。然后我遍历所有结束节点并运行它以获取每条路径。问题是它需要永远！我正在考虑可能对所有可能的组合进行硬编码以加快速度，当然我不能手动执行此操作，因为例如一棵有 25 个步骤的树将有 2^25 ~= 3500 万种可能的组合，但也许我可以打印搜索的输出并将其用于硬编码？或者有没有人看到我可以做的任何简单的优化会对性能产生很大的影响？谢谢。

编辑：让我澄清一点。我需要路径，即沿树的移动序列，其中 1 代表右手移动，0 代表左手（或上/下，随你喜欢）。因此，例如一个两步树，我需要四个有序对 (1,0) (0,1) (1,1) (0,0)。

4

1 回答 1

1

由于“所有组合”应该只是“在某个级别右转/左转的组合”，您可以循环通过 0 到 2 ^ n - 1，前面用 0 填充的二进制表示可能就是你要。

如果您想要的是左转计数等于某个数字 k 的路径计数，那么这仅等于 k ​​位等于 1 的从 0 到 2 ^ n - 1 的数字，您可以使用它来计算你想要的结果。

于 2013-05-01T13:59:41.043 回答