OpenMP - std::next_permutation

Question

我正在尝试使用 OpenMP 并行化我自己的 C++ 实现的旅行商问题。

我有一个函数来计算道路cost()和向量 [0,1,2,...,N] 的成本，其中 N 是道路的节点数。

在main()，我试图找到最好的道路：

do
{
    cost();
} while (std::next_permutation(permutation_base, permutation_base + operations_number));

我试图用来#pragma omp parallel并行化该代码，但它只会让它更耗时。有没有办法并行化该代码？

Answer 1

#pragma omp parallel不会在单独的线程上自动划分计算。如果要划分计算，则需要另外使用#pragma omp for，否则将进行多次孔计算，每个线程一次。例如，以下代码打印“Hello World！” 在我的笔记本电脑上四次，因为它有 4 个内核。

int main(int argc, char* argv[]){
    #pragma omp parallel
    cout << "Hello World!\n";
}

如果您简单地编写#pragma omp parallel. 您的代码被多次执行，每个线程执行一次。因此你的程序不会更快。如果您想将工作划分到线程上（每个线程做不同的事情），您必须使用类似#pragma omp parallel for.

现在我们可以查看您的代码。它不适合并行化。让我们看看为什么。您从数组开始permutation_base并计算成本。然后你permutation_base用next_permutation. 您实际上必须等待完成的成本计算，然后才能操作数组，否则成本计算将是错误的。所以整个事情不会在单独的线程上工作。

一种可能的解决方案是，保留 array 的多个副本permutation_base，并且每个可能的排列基仅通过所有排列的一部分。例如：

vector<int> permutation_base{1, 2, 3, 4};
int n = permutation_base.size();
#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    // Make a copy of permutation_base
    auto perm = permutation_base;
    // rotate the i'th  element to the front
    // keep the other elements sorted
    std::rotate(perm.begin(), perm.begin() + i, perm.begin() + i + 1);
    // Now go through all permutations of the last `n-1` elements. 
    // Keep the first element fixed. 
    do {
        cost() 
    }
    while (std::next_permutation(perm.begin() + 1, perm.end()));
}