OpenMP — std :: next_permutation
Я пытаюсь распараллелить мою собственную реализацию задачи коммивояжера на C ++ с использованием OpenMP.
У меня есть функция для расчета стоимости дороги cost() и вектор [0,1,2, …, N], где N — количество узлов дороги.
В main()Я пытаюсь найти лучшую дорогу:
do
{
cost();
} while (std::next_permutation(permutation_base, permutation_base + operations_number));
Я пытался использовать #pragma omp parallel распараллелить этот код, но это только сделало его более трудоемким.
Есть ли способ распараллелить этот код?
Решение
#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()));
}
Другие решения
Вероятнее всего.
Большая проблема с распараллеливанием этих проблем перестановок состоит в том, что для того, чтобы хорошо распараллелить, вам нужно «проиндексировать» произвольную перестановку. Короче говоря, вам нужно найти 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