c++ - pthread を使用して N クイーン パズルを解く

Question

バックトラッキングと再帰を使用して、n 個のクイーン パズルを解く方法を知っています。

マルチスレッドを使用してこれを最適化する方法を考えていました。

p - スレッドで試しています。

基本的に、どこにスレッドを適用し、どこでスレッドを結合するかを理解できません。

これは再帰であるため、スレッドがここでどのように機能するかを理解することもできません。

--

ありがとう

Alok Kr.

Answer 1

1つの方法は、再帰を実行する代わりに、キューを使用して各拡張をキューに入れることです。拡張をポップしてそれに取り組むスレッドのプールを用意します。

create a state with an empty board and put it into the queue
create N threads with the following function

スレッド関数：

while not done:
  1) pop a state S from the queue (use locks), if queue is empty,
     wait on a semaphore until there is an S
  2) expand state S
  2a) if S has feasible children then put them into the queue 
      except for one state SS, call it S and goto 2 
     (also signal the semaphore)
  2b) if S has no feasible children goto 1
end while

さまざまなアルゴリズムに合わせてこれを変更できます