스도쿠 병렬 처리와 MPI

Question

스도쿠 솔버 프로그램을 MPI와 병렬 처리하고 싶습니다. 현재 직렬 코드는 깊이 우선 검색으로 역 추적에 의존합니다. 나는 약간의 연구를했지만 아직도 어떻게하는지 잘 모릅니다. 프로그램에서 마스터 프로세스에서 일부 데이터를 가져온 다음이 데이터와 함께 슬레이브 프로세스를 사용하려면 너비 우선 검색을 수행해야한다고 말하는 사람들도 있습니다. 따라서 슬레이브 프로세스는이 데이터를 사용하여 깊이 우선 검색을 수행합니다.

또한 깊이 우선 검색 병렬화 예제는 작업 공유 또는 도용 방법을 사용하는 것으로 나타났습니다. 그러나 스도쿠의 경우,이 기술을 사용하면 스도쿠의 해결 방법 때문에 프로세스 관계, 작업 대기열 및 프로세스 크기를 처리 할 수 ​​있는지 확신하지 못합니다.

아이디어가 있으십니까?

감사합니다.

Answer 1

이것은 수독에 관한 대답이 아니며, 직렬 알고리즘을 지정하면 깊이 우선 검색을 사용합니다. Depth-first search는 '본질적으로 연속적'인 것처럼 보이지는 않지만 difficult to parallelize으로 알려진 문제입니다.

그러나 병렬 DFS 구현이 있습니다. 예를 들어 1987 paper은 병렬 DFS 알고리즘을 제공합니다. 일반적인 원칙은 각 프로세서가 리프 (또는 임의의 검색 깊이)에 도달 할 때까지 다른 경로 집합을 검색하고 경로 집합을 완료하면 새로운 비경로 분기를 선택한다는 것입니다.

병렬 DFS를 구현하고 싶다면이 기사를 읽고 해당 알고리즘을 구현하는 것이 좋습니다. 그러나 DFS를 사용하지 않는 지능형 병렬 스도쿠 알고리즘이 더 많이 존재한다고 생각합니다. 예를 들어 제약 전파 (Constraint Propagation)를 사용하여 해결할 수 있습니다.