Jon*_*Jon 18 java algorithm multithreading sudoku
我有一个家庭作业来编写一个多线程的数独求解器,它找到给定谜题的所有解决方案.我以前写过一个非常快速的单线程回溯数独求解器,所以我不需要任何帮助解决数独问题.
我的问题可能与不真正的并发性有关,但我不知道这个问题如何从多线程中受益.我不明白如何在不保留拼图的多个副本的情况下同时找到同一问题的不同解决方案.鉴于这种假设(请证明它是错误的),我没有看到多线程解决方案如何比单线程更有效.
我很感激,如果有人能给我一些算法的开始建议(请,没有代码......)
我忘了提到,要使用的线程数被指定为程序的参数,所以据我所知,它与任何方式的拼图状态无关......
此外,可能没有一个独特的解决方案 - 有效的输入可能是一个完全空的板.我必须报告min(1000, number of solutions)并显示其中一个(如果存在)
Tom*_*eys 18
真的很简单.基本概念是,在您的回溯解决方案中,您可以在有选择时进行分支.你试过一个分支,回溯然后尝试了另一个选择.
现在,为每个选择产生一个线程并同时尝试它们.如果系统中已存在<某些线程数(这将是您的输入参数),则只生成一个新线程,否则只使用一个简单的(即您现有的)单线程解决方案.为了提高效率,请从线程池中获取这些工作线程.
在许多方面,这是一种分而治之的技术,您将选择作为将搜索空间分成两半并为每个线程分配一半的机会.很可能一半比另一半更难,因为线程生命周期会有所不同,但这就是使优化变得有趣的原因.
处理明显的同步问题的简单方法是复制当前的板状态并将其传递到函数的每个实例中,因此它是一个函数参数.这种复制意味着您不必担心任何共享并发.如果您的单线程解决方案使用全局或成员变量来存储板状态,则需要在堆栈(简单)或每个线程(更难)上复制此类.您需要返回的所有功能都是电路板状态以及为达到它而采取的一些措施.
调用多个线程进行工作的每个例程应该在有n个工作时调用n-1个线程,执行第n个工作,然后等同同步对象直到所有其他线程完成.然后你评估他们的结果 - 你有n个板状态,返回移动次数最少的那个.
多线程在单个线程必须等待资源并且在此期间可以运行另一个线程的任何情况下都很有用.这包括等待I/O请求或数据库访问的线程,而另一个线程继续CPU工作.
如果各个线程可以被分配到不同的CPU(或核心),因为它们然后真正同时运行,多线程也很有用,尽管它们通常必须共享数据,因此仍然存在一些争用.
我看不出任何理由为什么多线程数独求解器比单线程求解器效率更高,只是因为没有等待资源.一切都将在记忆中完成.
但是我记得我在Uni做过的一些功课,它同样没用(Fortran代码看看当你在30度下一英里然后15度再挖一英里时隧道有多深 - 是的,我很漂亮老:-).关键是要表明你可以做到,而不是它有用.
关于算法.
我编写了一个单线程解算器,它基本上在每个传递中运行一系列规则来尝试填充另一个方块.一个示例规则是:如果第1行只有一个正方形,则第1行中的所有其他数字都可以看出这个数字.
所有行,所有列,所有3x3迷你网格都有类似的规则.还有一些检查行/列相交的规则(例如,如果给定的正方形由于行而只能包含3或4,而由于该列则为4或7,那么它是4).有更复杂的规则,我不会在这里详述,但它们基本上与您手动解决的方式相同.
我怀疑你的实施中有类似的规则(因为除了暴力之外,我认为没有其他方法可以解决它,如果你使用蛮力,你就没有希望了:-).
我建议将每个规则分配给一个线程并让它们共享网格.每个线程都会执行自己的规则并且只执行该规则.
更新:
Jon,基于您的编辑:
[编辑]我忘了提到,要使用的线程数被指定为程序的参数,所以据我所知,它与任何方式的拼图状态无关......
此外,可能没有一个独特的解决方案 - 有效的输入可能是一个完全空的板.我必须报告min(1000,解决方案的数量)并显示其中一个(如果存在)
看起来您的老师不希望您根据规则进行拆分,而是根据叉点(可以应用多个规则)进行拆分.
我的意思是,在解决方案的任何一点,如果有两个或更多可能的前进,你应该将每种可能性分配给一个单独的线程(仍然使用你的效率规则,但同时检查每种可能性).这将为您提供更好的并发性(假设线程可以在不同的CPU /内核上运行),因为不会对板进行争用; 每个线程都会获得它自己的副本.
此外,由于您限制了线程数,因此您必须使用一些线程池魔术才能实现此目的.
我建议的是有一个工作队列和N个线程.当主线程启动所有工作线程时,工作队列最初为空.然后主线程将起始拼图状态放入工作队列.
工作线程只是等待一个状态放在工作队列中,其中一个抓取它进行处理.工作线程是您的单线程解算器,只有一个小的修改:当有X个可能向前移动(X> 1)时,您的工作人员将X-1放回到工作队列中,然后继续处理另一种可能性.
所以,让我们说只有一个解决方案(真正的数独:-).第一个工作线程将在没有找到任何叉子的情况下缩小解决方案,这将与您当前的情况完全相同.
但是在第27步中有两种可能性(例如,3或4可以进入左上角单元格),你的线程将创建另一个具有第一种可能性的板(将3放入该单元)并将其放入工作队列中.然后它将4放在自己的副本中并继续.
另一个线程将在该单元中拾取3个板并继续.这样,您有两个并发运行的线程来处理这两种可能性.
当任何线程决定其板不可溶时,它会抛弃它并返回工作队列以进行更多工作.
当任何线程决定其板已经解决时,它会通知可以存储它的主线程,覆盖任何先前的解决方案(首先找到解决方案)或者如果它已经有解决方案则扔掉(最后找到解决方案)然后工作线程返回工作队列以进行更多工作.在任何一种情况下,主线程都应增加找到的解决方案的数量.
当所有线程都空闲且工作队列为空时,main将会或者不会有解决方案.它也将有一些解决方案.
请记住,工作人员和主要线程之间的所有通信都需要互斥(我假设您根据问题中的信息知道这一点).
多线程背后的想法是利用多个CPU,允许您同时进行多次计算.当然每个线程都需要自己的内存,但这通常不是问题.
大多数情况下,您要做的是将可能的解决方案状态划分为多个子空间,这些子空间尽可能独立(避免在线程创建开销上浪费太多资源),并且"适合"您的算法(实际受益)从多个线程).