c++ - 在图遍历中找到最小路径的有效方法

问题描述

我有一大组二进制字符串，长度都一样。我知道每个二进制字符串的 1 步邻域（意思是，所有其他二进制字符串仅相差 1 位）。这种关系本质上创建了一个图表。现在，从图中的任何节点开始，我想知道在基于某些派生值（不是基于二进制字符串）到达不同节点之前我必须采取的最小步骤数。我正在使用一些下面的示例中的虚拟函数 GetABC() ）。如果我们在找到不同节点之前遇到死胡同，我们假设到达不同节点的最小步数是无限的。死胡同是指无法访问新节点（基于访问节点的历史）。如果我们的整个人口具有相同的派生值，那么最坏的情况是我们将访问每个节点然后返回无限（-1）。

我的第一次尝试是使用递归函数，并通过传递对访问节点向量的引用来跟踪所有访问节点。它适用于小型数据集，但使用 100 万个二进制字符串时，我遇到了堆栈溢出错误（字面意思）。

然后，我重构了我的代码以循环运行，而不是通过迭代构建要访问的邻居集，然后遍历所有邻居并检查是否有任何具有不同的派生值（GetABC（）），然后从我们刚刚的所有邻居重新开始参观了。同样，在一个小数据集上工作，但有 100 万条记录，我的代码已经运行了 4 天，但仍未完成（在 12 个线程上使用并行 for_each 对所有节点进行此分析）。

//Previously had this function as a recursive algorithm, but it triggered stack overflow on big dataset
int MyClass::FindDifferentNodeInNeighborhood2(uint64_t node_hash) {
    std::vector<uint64_t> visited;//init empty visited vector
    visited.push_back(node_hash);

    int level = 0;
    bool found_diff_node = false;
    std::unordered_map<int, std::vector<std::pair<uint64_t, uint64_t>>> to_visit;//<level, vec<node_to_visit, parent_node>>

    to_visit[level].push_back(std::make_pair(node_hash, 0));//0 because no parent. Not used in first loop anyway so the value doesn't matter

    while (!found_diff_node && !to_visit[level].empty()) {
        for (auto n : to_visit[level]) {
            //_negihborhood is a member variable of MyClass defined as
            //std::unordered_map<uint64_t, std::unordered_set<uint64_t>> _neighborhood;
            for (const auto neighbor : _neighborhood[n.first]) {
                //make sure we didn't visit this neighbor already
                if (std::find(visited.begin(), visited.end(), neighbor) == visited.end()) {
                    //if not, add to next set of node to visit
                    to_visit[level + 1].push_back(std::make_pair(neighbor, n.first));
                }
            }
        }
        level++;

        for (auto n : to_visit[level]) {
            //auto node = n.first;
            //auto parent = n.second;
            visited.push_back(n.first);
            //_population is the map of the actual binary strings objects
            //We retrieve the object using it's hash
            //GetABC() is just a function that gets a specific value from the node
            if (_population[n.first].GetABC() != _population[n.second].GetABC()) {
                found_diff_node = true;
                break;
            }
        }
    }

    if (!found_diff_node) {
        return -1;
    }
    return level;
}

我将进一步调试，看看它是否不是无限循环的问题，但我想我应该在这里问我是否没有忽略一些可以实现这一目标的简单算法。

谢谢

标签： c++optimizationgraph-traversal

解决方案

visited应更改为unordered_set，并对其使用方式进行相关更改。这将大大减少搜索节点是否已被访问所花费的时间。这可能会增加所需的内存。

to_visit看起来它不需要是一个unordered_map. level在将新节点添加到下一个级别时，您会查看带有 on 的节点。然后，您查看那些新节点，而不再查看以前的节点。将此映射替换为两个std::vector<std::pair<uint64_t, uint64_t>>变量（我将它们称为visit_nowand visit_next。对的引用to_visit[level]将是 into visit_now，而添加到to_visit[level + 1]将是 to visit_next。当您离开第一个循环时，当您递增时level，您可以交换visit_nextand visit_now，然后清除visit_next（或移动下一个进入现在并清除下一个）。

在添加到(aka ) 向量 ( ) 时使用emplace_back而不是。push_backvisit_nextto_visit[level + 1]visit_next.emplace_back(neighbor, n.first));

c++ - 在图遍历中找到最小路径的有效方法

问题描述

解决方案

推荐阅读