使用pthreads解决N皇后拼图

我知道如何解决n皇后拼图，使用回溯和递归。使用pthreads解决N皇后拼图

我在想如何使用多线程来优化它。

我想用p - 线程。

基本上我无法理解顶端应用线程的位置，以及在哪里加入线程。

由于这是递归，我也无法理解线程在这里如何工作。

感谢

阿洛克氪。

来源

2012-06-30 Kumar Alok

我读的书籍为好，但急于找到方法。此外，我无法了解多线程如何与回溯和递归一起工作，它会真正优化吗？ –

它可能。或者可能会让事情变得很慢。这取决于很多事情，包括你如何写它。总之，看一下英特尔的这篇文章，它并行地解决了您的问题 - http://software.intel.com/zh-cn/articles/getting-code-ready-for-parallel-execution-with-intel-parallel -composer/ – 2012-06-30 03:30:35

其实最终的答案是否定的，它不会优化，因为它是一个不规则的问题，递归地执行并且在回溯时同步会导致负载不平衡。因此，它是上述参考资料中Cilk解决方案的一个很好的例子，它将通过工程量测来平衡负载。（这正是Cilk基准测试一直包含此问题的原因） –

一种方法是使用队列将每个扩展放入队列中，而不是进行递归。有一个流行的扩展和它的工作线程池：

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

您可以修改此不同的算法

来源

2012-06-30 03:47:39 perreal

使用pthreads，您可能会使用条件变量而不是信号量在步骤1中等待。 – caf

使用pthreads解决N皇后拼图

回答

相关问题