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。在您允許操作數組之前，您實際上必須等待完成的成本計算，否則成本計算就會出錯。所以整個事情不會在單獨的線程上工作。

一個可能的解決方案是，保持數組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

絕對是。

並行化這些排列問題的一個大問題是，爲了很好地並行化，您需要「索引」爲任意排列。總之，你需要找到第k個排列。您可以利用一些很酷的數學性質的，你會發現這一點：

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 

查找第i個置換，並讓一個線程調用std::next_permutation直到找到下一個線程的起點。

注意，你會想換一個包含#pragma omp parallel