用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]) 

    } 

我只需要演員，因爲沒有一個程序將立即終止，雖然期貨尚未處理。但是，這個解決方案看起來不是很「優雅」 - 也許有更好的解決方案。但我認爲我不能使用「等待」，因爲我必須指示超時（我事先不知道）

再次，非常感謝！