打破或Scala中

帶有短路的摺疊我已經寫在Scala中一個簡單的深度優先搜索與這樣的一個遞歸函數：打破或Scala中

search(labyrinth, path, goal)

其中迷宮是問題的規範（如圖形或其他），路徑是一個列表，其中包含目前爲止所採用的路徑，目標是目標狀態的規範。如果找不到路徑，該函數將返回到目標的路徑爲List和Nil。

該功能擴展，例如，找到所有合適的下一個節點（候選），然後必須遞歸調用自己。

我這樣做是通過

candidates.foldLeft(Nil){ 
    (solution, next) => 
    if(solution == Nil) 
     search(labyrinth, next :: path, goal) 
    else 
     solution 
}

請注意，我省略了一些細節unescessary。目前爲止一切正常。但是一旦在foldLeft調用中找到解決方案，這個解決方案就會被if語句的else部分簡單複製。有沒有辦法通過打破foldLeft或使用不同的函數而不是foldLeft來避免這種情況？其實我可以寫一個foldLeft版本，一旦「not Nil」自動返回就會破壞它。但是API裏面有一個嗎？

來源

2009-10-20 ziggystar

你想要完全避免什麼？沒有複製在任何地方發生。 – Apocalisp 2009-10-20 16:23:55

是不是他/她會爲列表中的每個剩餘項目發起至少一個函數調用？ – 2009-10-20 16:37:55

隨着foldLeft，是的。但是，再次，foldLeft正在傾向於做一些它並不打算的事情。 – 2009-10-20 16:59:39

我不確定我是否理解短路迴路的願望。迭代候選人是否昂貴？候選人名單可能很大？

也許你可以使用「find」方法：

candidates.find { c => 
    Nil != search(labyrinth, c :: path, goal) 
} match { 
    case Some(c) => c :: path 
    case None => Nil 
}

如果搜索空間的潛深大，你可能溢出的堆棧（配件，給這個網站的名稱）。但是，這是另一篇文章的主題。

對於傻笑，這裏是一個實際的可運行的實現。我不得不介紹一個局部可變變量（fullPath），大多數情況下都是懶惰，但我相信你可以把它們拿出來。

object App extends Application { 

    // This impl searches for a specific factor in a large int 
    type SolutionNode = Int 
    case class SearchDomain(number: Int) { 
     def childNodes(l: List[Int]): List[Int] = { 
      val num = if (l.isEmpty) number else l.head 
      if (num > 2) { 
       (2 to (num - 1)) find { 
        n => (num % n)==0 
       } match { 
        case Some(i) => List(i, num/i) 
        case None => List() 
       } 
      } 
      else List() 
     } 
    } 
    type DesiredResult = Int 


    def search (labyrinth: SearchDomain, path: List[SolutionNode], goal: DesiredResult): List[SolutionNode] = { 

     if (!path.isEmpty && path.head == goal) return path 
     if (path.isEmpty) return search(labyrinth, List(labyrinth.number), goal) 

     val candidates: List[SolutionNode] = labyrinth.childNodes(path) 
     var fullPath: List[SolutionNode] = List() 
     candidates.find { c => 
      fullPath = search(labyrinth, c :: path, goal) 
      !fullPath.isEmpty 
     } match { 
      case Some(c) => fullPath 
      case None => Nil 
     } 
    } 

    // Is 5 a factor of 800000000? 
    val res = search(SearchDomain(800000000), Nil, 5) 
    println(res) 

}

來源

2009-10-20 16:29:38

不會有任何使用'find'的堆棧溢出比使用'foldLeft'。使用'find'完全符合他想要的：獲得可找到解決方案的第一個候選人。 – 2009-10-20 16:48:16

沒錯。但是，根據問題域，堆棧溢出可能是ziggystar的問題，與原始問題正交。嘿，我只是想了一個問題！ – 2009-10-20 16:57:18

這看起來像一個很好的解決方案。非常感謝你。並且：搜索問題並不大。這個問題僅僅是出於對如何做到「好」的好奇心而引起的。 – ziggystar 2009-10-21 09:41:45

我喜歡Mitch Blevins解決方案，因爲它與您的算法完美匹配。您可能有興趣在my own solution到另一個迷宮問題。

來源

2009-10-20 16:55:42

回答

相關問題