Алгоритм параллельного рыцарского тура

Question

Алгоритм параллельного рыцарского тура

В настоящее время у меня есть алгоритм тура рыцаря, который работает.

Я использую комбинацию:

Откат
Правило Варнсдорфа

Алгоритм выполняет следующие действия:

Checks to see if the board is solved (all squares visited)
If true: return true
else proceed:

Make a set of possible moves from current positions
Sort the set based on the number of moves available from those positions.

Go through the set. (Recursive call made here)
If returned True:
Set Solution board to appropriate number
Return true
else
go back to last position
return false.

Это работает хорошо. Это не лучшее решение.

Я пытаюсь увеличить скорость, используя распараллеливание, в частности, используя многопоточность C ++ (#include<thread>).

Какой алгоритм для этого? Пока что единственные способы, которыми я пробовал, иметь ложные проблемы с совместным использованием, проблемы с общей памятью или не работать вообще.

0

c++knights-tour multithreading parallel-processing

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Конечно, это для C ++, после вызова #include<thread> заголовок, простой способ создания потоков:

#include <iostream>
#include <thread>

void testThread()
{
std::cout<<"Thread\n";
}

int main(int argc, char * argv[])
{
std::testThread t(testThread);
t.join();

return 0;
}

std::testThread t(testThread); вызывает создание потока в то время как t.join(); присоединяется к ним после завершения. Но это все без использования замков. Если бы я был тобой, я бы просмотрел те же самые примеры в Интернете — есть масса ресурсов — которые показывают, как реализовать блокировки в безопасном поместье.

Стоит отметить, что вы должны убедиться, что последовательная версия кода действительно может быть полезна при параллельном запуске, поскольку создание потоков может быть дорогостоящим.

1