求解数独的多线程算法?

真的很简单。基本概念是,在回溯解决方案中,当有选择时,您将进行分支。你尝试了一个分支,回溯,然后尝试了另一个选择。

现在,为每个选项生成一个线程,并同时尝试它们。只有当系统中已经有一些线程(这将是您的输入参数)时,才能生成一个新线程,否则只需使用一个简单的(即现有的)单线程解决方案。为了提高效率,请从线程池中获取这些工作线程。

这在很多方面都是一种分而治之的技术,您将这些选择作为一个机会,将搜索空间分成两半,并将一半分配给每个线程。很可能一半比另一半更难,这意味着线程的生命周期将有所不同,但这正是使优化有趣的原因。

处理明显的同步问题的简单方法是复制当前的板状态并将其传递到函数的每个实例中,因此它是一个函数参数。这种复制意味着您不必担心任何共享并发。如果单线程解决方案使用全局变量或成员变量来存储板状态,则需要在堆栈(简单)或每个线程(较难)上复制该变量。您所需要返回的所有功能都是一个板状态以及为达到该状态所采取的一些操作。

调用多个线程进行工作的每个例程应该在有n个工作时调用n-1个线程,执行第n个工作,然后使用同步对象等待,直到所有其他线程完成。然后评估他们的结果-你有n个董事会状态,返回移动次数最少的状态。

多线程在任何情况下都很有用,在这种情况下,一个线程必须等待一个资源,并且您可以同时运行另一个线程。这包括一个等待I/O请求或数据库访问的线程,而另一个线程继续进行CPU工作。

多线程也很有用 如果 单个线程可以被转移到不同的CPU(或核心),因为它们随后真正并发地运行,尽管它们通常必须共享数据,所以仍然存在一些争用。

我不明白为什么多线程数独解算器比单线程解算器更有效,仅仅是因为没有等待资源。一切都将在记忆中完成。

但我记得我在uni做的一些作业,也同样没用(fortran代码是看你在30度的条件下挖了一英里,然后在15度的条件下挖了另一英里,隧道有多深——是的,我已经很老了。关键是要证明你能做到,而不是说它是有用的。

关于算法。

我写了一个单线程求解器,它基本上在每次传递中运行一系列规则来尝试填充另一个正方形。一个示例规则是:如果第1行只有一个正方形可用,那么第1行中所有其他数字的数字都是显而易见的。

所有行、所有列、所有3x3迷你网格都有类似的规则。也有检查行/列相交的规则(例如,如果给定的正方形由于行只能包含3或4,由于列只能包含4或7,那么它是4)。这里有一些更复杂的规则,我不会在这里详细说明,但它们基本上与您手动解决的方法相同。

我怀疑在您的实现中您有类似的规则(因为除了蛮力之外,我无法想到其他方法来解决它,而且如果您使用了蛮力,那么您就没有希望了:—)。

我建议将每个规则分配给一个线程,并让它们共享网格。每个线程都会执行它自己的规则,并且只执行该规则。

更新:

乔恩,根据你的编辑:

[编辑]我忘了提一下,要使用的线程数被指定为程序的参数,据我所知,它与解谜的状态没有任何关系…

此外,可能没有一个独特的解决方案-有效的输入可能是一个完全空的电路板。我必须报告最小值(1000,解决方案数)并显示其中一个(如果存在)

看起来你的老师不希望你根据规则进行拆分,而是基于分叉点(在分叉点可以应用多个规则)。

我的意思是,在解决方案的任何一点上,如果有两个或更多的可能向前移动,您应该将每个可能性分配到一个单独的线程(仍然使用您的规则来提高效率,但同时检查每个可能性)。这将为您提供更好的并发性(假设线程可以在单独的CPU/核心上运行),因为对该板没有争用;每个线程都将获得它自己的副本。

此外,由于您限制了线程的数量,因此必须使用一些线程池魔法来实现这一点。

我建议有一个工作队列和N个线程。当主线程启动所有工作线程时,工作队列最初是空的。然后,主线程将开始的拼图状态放入工作队列。

工作线程只需等待一个状态被放置到工作队列中,其中一个线程将获取该状态进行处理。工作线程是您的单线程求解器,只有一个小的修改:当有x个可能向前移动(x>1)时,您的工作人员将其中的x-1放回工作队列,然后继续处理另一个可能。

所以,假设只有一个解决方案(真正的数独:-)。第一个工作线程将在不找到任何分叉的情况下逐渐消去解决方案,这将与您当前的情况完全相同。

但是在移动27处有两种可能(例如,3或4可以进入左上角的单元格),您的线程将创建另一个具有第一种可能(将3放入该单元格)的板,并将其放入工作队列。然后,它将把4放在自己的副本中并继续。

另一根线将拿起电池中有3个的电路板并继续进行。这样,您就有两个线程同时运行,处理这两种可能性。

当任何线程决定其板是不可溶解的时,它会将其丢弃,并返回工作队列以进行更多的工作。

当任何线程决定解决其板时,它通知可以存储它的主线程,重写任何以前的解决方案(首先找到的是解决方案)或丢弃它(如果它已经得到解决方案(最后找到的是解决方案),然后工作线程返回工作队列以进行更多的工作。在这两种情况下,主线程都应该增加找到的解决方案的数量。

当所有线程都处于空闲状态且工作队列为空时,MAIN要么会有解决方案,要么不会有解决方案。它还将有许多解决方案。

请记住,工作人员和主线程之间的所有通信都需要静音(我假设您根据问题中的信息了解这一点)。

多线程背后的想法是利用多个CPU的优势,使您可以制作多个CPU 计算 同时。当然,每个线程都需要自己的内存,但这通常不是问题。

大多数情况下,您要做的是将可能的解决方案状态划分为尽可能独立的几个子空间(以避免在线程创建开销上浪费太多资源),同时“适应”您的算法(以实际受益于拥有多个线程)。

这里有一个贪婪的蛮力单线程解决方案:

1. 选择下一个空单元格。如果没有空房,胜利!
2. 可能的单元格值=1
3. 检查部分解决方案是否无效(行、列或3x3块中有重复项)。
4. 如果部分解决方案无效,请增加单元格值并返回步骤3。否则,转到步骤1。

如果你看上面的大纲,步骤2和3的组合显然是多线程的候选者。更野心勃勃的解决方案包括创建一个递归探索,生成提交到线程池的任务。

编辑以回答这一点:“我不明白你如何在不维护多个拼图副本的情况下,同时找到同一问题的不同解决方案。”

你不能。这就是重点。然而,一个具体的9线程示例可能会使好处更加明确:

1. 从一个例子开始。
2. 找到第一个空单元格。
3. 创建9个线程,其中每个线程都有自己的问题副本,并且在空单元格中有自己的索引作为候选值。
4. 在每个线程中,在此线程上运行原始的单线程算法本地修改的问题副本。
5. 如果其中一个线程找到答案,则停止所有其他线程。

正如您可以想象的那样,每个线程现在运行的问题空间稍微小一些,并且每个线程都有可能在自己的CPU核心上运行。单凭单线程算法,你就不能从多核机器中获益。

它是否需要从多线程中获益,或者只是利用多线程来学习分配?

如果使用蛮力算法,那么很容易将其拆分为多个线程,并且如果分配的重点是编码线程,那么这可能是一个可接受的解决方案。

当你说出一个给定谜题的所有答案时,你的意思是 最后一个也是唯一的解决方案 拼图?或 不同的到达方式 唯一的解决方案?我明白,根据定义,一个数独游戏只能有一个解决方案…

对于前者,要么 Pax's rule based approach 或 Tom Leys' take on multi-threading your existing backtracking algorithm 可能是去的路。

如果是后者,您可以实现某种分支算法,它为每个可能的移动在拼图的每个阶段启动一个新的线程(有它自己的拼图副本)。

根据单线程求解器的编码方式,您可能能够重新使用逻辑。你可以用一组不同的策略来编写多线程求解器来启动每个线程。

使用这些不同的策略,你的多线程解算器可能会比单线程解算器在更短的时间内找到全部的解集(记住,尽管真正的数独游戏只有一个解……你不是唯一一个必须在课堂上处理那可怕的游戏的人)。

一些要点:我不会并行运行进程,除非1)很容易划分问题2)我知道这样做会有好处-例如,我不会遇到另一个瓶颈。我完全避免在线程之间共享可变值——或者最小化它。有些人足够聪明,可以安全地使用互斥体。我不是。

您需要在您的算法中找到创建自然分支或大型工作单元的点。一旦您确定了一个要工作的单元,您就把它放到队列中,让一个线程接收它。作为一个微不足道的例子。10个要升级的数据库。在所有10台服务器上启动异步升级。等待全部完成。我可以很容易地避免在线程/进程之间共享状态,并且可以很容易地聚合结果。

对于数独游戏来说,一个有效的数独解决方案应该结合2-3(或更多)策略,而这些策略永远不会超过一定的深度。当我做数独的时候,很明显,在任何给定的时刻,不同的算法提供的解的工作量最小。你可以简单地启动一些策略,让他们调查到有限的深度,等待报告。冲洗,重复。这避免了“强行”解决方案。每种算法都有自己的数据空间,但是你要把答案结合起来。

Sciam.com在一到两年前就发表了这篇文章,不过看起来它并没有公开。

你说你用回溯来解决这个问题。您可以做的是将搜索空间拆分为两个,并将每个空间处理为一个线程,然后每个线程都将执行相同的操作,直到到达最后一个节点。我做了一个解决方案,可以找到ww2.cs.uregina.ca/~hmer200a,但是使用单线程,但是使用分支和绑定来分割搜索空间的机制是存在的。

几年前,当我研究解决数独问题时,似乎最优解使用了逻辑分析算法的组合,只有在必要的时候才回归到蛮力。这使得解算器能够很快地找到解,并且如果你想用它来生成一个新的拼图,还可以通过难度来排列棋盘。如果采用这种方法,您当然可以引入一些并发性,尽管让线程实际上一起工作可能很困难。

我有个主意,在这里很有趣。和演员模特一起做吧!我想说用二郎…… 怎样?你从最初的董事会开始,然后……

• 1)首先空单元格创建9个不同编号的儿童,然后自杀
• 2)每个孩子都要检查它是否无效,如果无效,就会自杀,否则
  • 如果有空单元格,请转到1)
  • 如果完成,这个参与者就是一个解决方案

很明显,每一个活着的演员都是问题的解决办法。

只是一个旁注。我实际上实现了一个优化的数独解算器,并研究了多线程,但有两件事阻止了我。

首先,启动线程的简单开销花费了0.5毫秒,而整个分辨率在1到3毫秒之间(我使用Java、其他语言或环境可能会给出不同的结果)。

第二,大多数问题不需要任何回溯。而那些确实需要的,只是在问题解决的后期才需要它,一旦所有的游戏规则都用尽了,我们就需要做一个假设。

这是我自己的一分钱。希望它有帮助。

记住,处理器间/线程间通信是昂贵的。不要多线程,除非你 有 去。如果在其他线程中没有太多的工作/计算需要完成,那么您也可以继续使用单个线程。

尽可能地尝试 避免 在线程之间共享数据。仅在必要时使用

利用 SIMD扩展 尽可能。通过向量扩展,您可以在一个Swoop中对多个数据执行计算。它能帮助你充实。