在图遍历中寻找最小路径的有效方法

Question

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

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

然后，我将代码重构为运行循环，而不是通过迭代构建要访问的邻居集，然后遍历所有邻居并检查是否有不同的派生值 (GetABC())，然后从我们刚刚访问过的所有邻居重新开始。同样，在一个小数据集上工作，但有 100 万条记录，我的代码已经运行ning 了 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;
}

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

谢谢

Answer 1

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

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

添加到 visit_next（又名 to_visit[level + 1]）向量 (visit_next.emplace_back(neighbor, n.first));) 时使用 emplace_back 而不是 push_back。

Answer 2

发现我的第一个循环，其中多次添加相同的节点，因为从要访问的节点集中，它们中的一些很可能有一些共同的邻居。通过擦除下一个要访问的节点集中的重复项来轻松修复。我也实施了其他答案中提出的建议。这是结果：

int MyClass::FindDifferentNodeInNeighborhood2(uint64_t node_hash) {
    std::unordered_set<uint64_t> visited;//init empty visited vector
    visited.insert(node_hash);
    

    int level = 0;
    bool found_diff_node = false;
    std::vector<std::pair<uint64_t, uint64_t>> visit_now;
    std::vector<std::pair<uint64_t, uint64_t>> visit_next;

    visit_now.emplace_back(std::make_pair(node_hash, 0));

    while (!found_diff_node && !visit_now.empty()) {
        for (auto n : visit_now) {
            for (const auto neighbor : _neighborhood[n.first]) {
                if(visited.find(neighbor) == visited.end()){
                    visit_next.emplace_back(std::make_pair(neighbor, n.first));
                }
            }
        }
        level++;

        //Remove duplicates
        std::sort(visit_next.begin(), visit_next.end());
        visit_next.erase(std::unique(visit_next.begin(), visit_next.end()), visit_next.end());


        visit_now.clear();
        visit_now = std::move(visit_next);
        visit_next.clear();

        for (auto n : visit_now) {
            visited.insert(n.first);
            if (_population[n.first].GetABC() != _population[n.second].GetABC()) {
                found_diff_node = true;
                break;
            }
        }
    }

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

在图遍历中寻找最小路径的有效方法

Efficient way of finding minimum path in graph traversal

c++

optimization

graph-traversal