OpenMP - std::next_permutation

Question

我试图使用C++并行处理自己的旅行推销员问题的OpenMP实现。

我有一个函数来计算道路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！“在我的笔记本上四次，因为它有四个核心。

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

如果简单地编写#pragma omp parallel，代码也会发生同样的情况。您的代码被多次执行，每个线程执行一次。所以你的程序不会更快。如果要将工作划分为线程(每个线程执行不同的操作)，则必须使用类似于#pragma omp parallel for的内容。

现在我们可以看看你的代码了。它不适合并行化。让我们看看为什么。从数组permutation_base开始，计算成本。然后用next_permutation操作next_permutation。实际上，在允许您操作数组之前，您必须等待已完成的成本计算，因为否则成本计算将是错误的。这样整件事就不会在不同的线程上工作了。

一种可能的解决方案是，保留数组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()));
}

Answer 2

最绝对的。

并行化这些排列问题的最大问题是，为了更好地并行化，需要将“索引”“索引”为任意排列。简而言之，你需要找到kth排列。你可以利用一些很酷的数学特性，你会发现：

std::vector<int> kth_perm(long long k, std::vector<int> V) {
    long long int index;
    long long int next;
    std::vector<int> new_v;
    while(V.size()) {
        index = k / fact(V.size() - 1);
        new_v.push_back(V.at(index));
        next = k % fact(V.size() - 1);
        V.erase(V.begin() + index);
        k = next;
    }
    return new_v;
}

因此，您的逻辑可能如下所示：

long long int start = (numperms*threadnum)/ numthreads;
long long int end = threadnum == numthreads-1 ? numperms : (numperms*(threadnum+1))/numthreads;

perm = kth_perm(start, perm); // perm is your list of permutations

for (int j = start; j < end; ++j){
    if (is_valid_tour(adj_list, perm, startingVertex, endingVertex)) {
        isValidTour=true;
        return perm;
    }
    std::next_permutation(perm.begin(),perm.end());
}

isValidTour = false;
return perm;

显然有很多代码，但是并行化的想法可以被我发布的小代码捕获。您可以像这样可视化“索引”：

|--------------------------------|
^        ^                   ^
t1      t2        ...        tn

查找ith排列，让线程调用std::next_permutation，直到找到下一个线程的起点为止。

请注意，您将希望包装包含#pragma omp parallel中底部代码的函数