用akka解决n皇后难题

Question

我对scala和akka编程相对陌生，我试图用akka actors为n皇后问题写一个解决方案。 不幸的是，我的想法并不奏效：与顺序方法相比，计算所有 解决方案花费的时间更长，并且程序永不终止。然而，一些正确的解决方案被打印到控制台。 这里是我的代码：

case class Work(list: List[Point]) 
    case class Reply(list: List[Point]) 

    class QueenWorker(val master: ActorRef) extends Actor { 
     override def preStart() = { 
     println("new worker") 
    } 
    def receive = { 
     case Work(list) => 
     val len = list.length 
     if (len < size) { 
      val actors = for (
      i <- 0 until size if (!list.exists(_.y == i)) 
     ) yield (context.actorOf(Props(new QueenWorker(master))), i) 
      actors.foreach { case (actor, pos) => actor ! Work(list :+ (new Point(len, pos))) } 

    } else { 
      if (check(list)) { //check() checks whether the solution is valid 
      master ! Reply(list) 
      println("solution found!") 
      } 
      //else sender ! Reply(List[List[Point]]()) 
     } 
     //context.stop(self) //when do I have to use it? 
     //println("worker stopped - len "+len) 
    } 
    } 

    class QueenMaster extends Actor { 
    override def preStart() = { 
     println("preStart") 
     context.actorOf(Props(new QueenWorker(self))) ! Work(List[Point]()) 
    } 

     def receive = {//print solution to console 
     case Reply(list) => 
     for (x <- 0 until size) { 
      for (y <- 0 until size) { 
      if (list.exists(p => p.x == x && p.y == y)) print("x ") else print("o ") 
      } 
      println() 
     } 
     println() 
    } 
    } 

def runParallel { 
    val system = ActorSystem("QueenSystem") 
    val queenMaster = system.actorOf(Props[QueenMaster]) 
    } 

我的目的是创建为每个新回溯迭代一个新的演员。如果演员找到了有效的解决方案，则发送给主控人员，并将其打印到控制台。

• 程序永不终止。但是，如果我在//context.stop（self）周围删除注释，则根本找不到解决方案。我该如何解决这个问题？
• 我的整个做法似乎都是错误的。什么可能是更好的？
• 有可能找到一个使用期货而不是演员的并行解决方案吗？

提前感谢！

Answer 1

经过一些调整，我设法运行你的程序并获得size=8的结果。出于调试目的在runParallel添加以下两行：

readLine() 
system.shutdown() 

当程序完成 - 按回车 - 这将导致调用shutdown方法和程序将退出。

我在8核i7 2.2Ghz机器上运行 - 所以你的结果可能会有所不同。

关于业绩，这是非常低效的解决方案，这是为什么： 在回溯过程中每一步 - 这是每一个试图解决部分问题 - 要创建和演员，做一个简单的循环产生更多的参与者为下一个提出的解决方案。

现在，在阿卡创造一个演员的速度相当快，但我敢说，在你的情况下，创造一个演员的开销比它正在做的实际工作更大（甚至可能是一个数量级） - 我没有没有经过测试，但很可能。

这里分析的部分解决方案的数量是板子大小的指数。那就是你创建了一个指数级的角色 - 这是很大的开销，你肯定会失去通过并行计算解决方案而获得的任何优势。

我们该如何做到这一点？那么，举个例子，我们可以创建少数几个演员。

让我们创建一个QueenWorker actors的固定池（与您计算机中的核心数量相同），并将它们放在SmallesMailboxRouter之后。

当你的员工检查处理Work消息，而不是创建新的角色，他们将在新提出的解决方案发送到路由器，而路由器将派遣这些新Work消息给它routees，一种统一的方式在当前的解决方案。

工人演员现在可以处理更多的部分解决方案，而不仅仅是一个，就像现在一样。这是一个比以前更好的实际工作/ akka_housekeeping比率。

我们可以做得更好，然后呢？我想我们可以，如果你以不同的方式模拟你的问题。在女王问题中，一般来说，在回溯中，你正在探索一种局部解决方案。 在您的算法的每一步当您从现有的生成更多的部分解决方案时，您正在分支您的树。你的方法存在的问题是，当你在算法中分支时，你也在并发流程中分支 - 我在这里指的是你发送一个新的工作信息以被另一个演员处理。这很好，但如果你添加数字，你会发现这是一个很大的开销，这不会给你带来任何时间优势。

那是因为你的Work任务的粒度很小。在发送消息之间你做的工作很少 - 这会影响你的表现。在生成新的Work消息之前，您可以让您的工作人员探索更多的部分解决方案。

例如，如果你有一个8核心的CPU，并且问题有size=8那么你最好创建8个工作者并且给工作者K以任务来计算具有位于列K中的女王的解决方案第一行。现在每个工作人员只执行一个Work任务，这个任务大约占全部工作的1/8，这会得到更好的结果。

关于与期货的解决方案 - 你当然可以这样做，但我觉得节目的时间将是大致相同，与演员的固定池演员的解决方案。但我鼓励你尝试，因为我可能是错的。

Answer 2

非常感谢您的回答。 你说得对 - 主要的问题是找到一个解决方案，有效地分割问题，但不会产生太多的参与者或消息。 即使是SmallesMailboxRouter解决方案也不能很好地工作，因为我创建了太多的消息。 然而，我发现，第一皇后的每个位置创建一个新的演员（像你这样的决定）这实际上比顺序处理速度更快的解决方案，不足之处是，这个问题是“唯一”的分成N（N =在chessfield）件的大小（但总比没有好） 下面是一些代码：

class QueenActor extends Actor { 
    override def preStart { 
     val start = System.currentTimeMillis() 
     val listOfFutures = (for (i <- 0 until size) yield Future { doIt2(List[Point](new Point(0, i))) }).toList 
     val futureOfLists = Future.sequence(listOfFutures) 
     futureOfLists.onSuccess { 
     case lists => 
      var solutions = 0 
      for (list <- lists.flatten) { 
      solutions += 1 
      println(solutions + ":") 

      for (x <- 0 until size) { 
       for (y <- 0 until size) { 
       if (list.exists(p => p.x == x && p.y == y)) print("x ") else print("o ") 
       } 
       println() 
      } 
      println() 
      } 

      println("Time: " + (System.currentTimeMillis() - start)) 
      System.exit(0) 

     } 

    } 
    def receive = { 
     case _ => 
    } 
    } 

    def runParallelFutures { 
    val system = ActorSystem("QueenSystem") 
    val queenMaster = system.actorOf(Props[QueenActor]) 

    } 

我只需要演员，因为没有一个程序将立即终止，虽然期货尚未处理。但是，这个解决方案看起来不是很“优雅” - 也许有更好的解决方案。但我认为我不能使用“等待”，因为我必须指示超时（我事先不知道）

再次，非常感谢！