问题描述
search（labyrinth，path）在Scala中写入一个简单的深度优先搜索，目标）
迷宫是问题的规范（如图或其他），路径是列出了目前所采用的路径，目标是目标状态的规范。如果找不到路径，该函数将返回到目标的路径为List和Nil。
该功能可以扩展，例如找到所有合适的下一个节点（候选），然后递归调用自己。
candidates.foldLeft（Nil）{
（solution，next）=>
if（solution == Nil）
search（labyrinth，next :: path，goal）
else
solution
}
请注意，我省略了一些不必要的细节。目前为止一切正常。但是一旦在foldLeft调用中找到解决方案，该解决方案就会被if语句的else部分简单复制。有没有办法通过打破foldLeft或使用不同的函数而不是foldLeft来避免这种情况？其实我可以写一个foldLeft版本，一旦not Nil自动返回就会破坏它。但是API里面有一个吗？
我不确定我是否理解短路回路的愿望。迭代候选人是否昂贵？可能你可以使用find方法：
candidates.find {c =>
Nil！= search（labyrinth，c :: path，goal）
} match {
case Some（c）=> c :: path
case None =>无如果潜在的搜索空间深度很大，您可能会溢出您的堆栈（拟合，给出这个网站名称）。但是，这是另一篇文章的主题。
对于咯咯笑，这里是一个实际可运行的实现。我不得不介绍一个本地可变变量（fullPath），主要是因为懒惰，但我相信你可以把它们拿出来。
对象App扩展应用程序{
//这个impl在一个大的int
类型中搜索一个特定的因子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到（num-1））找到{
n => （num％n）== 0
} match {
case Some（i）=> List（i，num / i）
case None => List（）
}
}
else List（）
}
}
类型DesiredResult = Int
def search（迷宫：SearchDomain，路径：List [SolutionNode]，goal：DesiredResult）：List [SolutionNode] = {
if（！path.isEmpty&&path.head == goal ）return path
if（path.isEmpty）return search（labyrinth，List（labyrinth.number），goal）
$ b $ val候选者：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
案例无=>无
}
}
// 5是800000000的一个因子吗？
val res = search（SearchDomain（800000000），Nil，5）
println（res）
}
I have written a simple depth-first search in Scala with a recursive function like that:
search(labyrinth, path, goal)
where labyrinth is a specification of the problem (as graph or whatever), path is a list that holds the path taken so far and goal is a specification of the goal state. The function returns a path to the goal as a List and Nil if no path can be found.
The function expands, e.g. finds all suitable next nodes (candidates) and then has to recursively call itself.
I do this by
candidates.foldLeft(Nil){
(solution, next) =>
if( solution == Nil )
search( labyrinth, next :: path, goal )
else
solution
}
Please note that I have omitted some unescessary details. Everything is working fine so far. But once a solution is found inside the foldLeft call, this solution gets simply copied by the else part of the if-statement. Is there a way to avoid this by breaking the foldLeft or maybe by using a different function instead of foldLeft? Actually I could probably write a version of foldLeft which breaks once "not Nil" is returned myself. But is there one inside the API?
解决方案 I'm not sure I understand the desire to short-circuit the loop. Is it expensive to iterate through the candidates? Is the candidates list potentially large?
Maybe you could use the "find" method:
candidates.find { c =>
Nil != search( labyrinth, c :: path, goal )
} match {
case Some(c) => c :: path
case None => Nil
}
If the potential depth of the search space is large, you could overflow your stack (fitting, given this site name). But, that is a topic for another post.
For giggles, here is an actual runnable implementation. I had to introduce a local mutable variable (fullPath) mostly out of laziness, but I'm sure you could take those out.
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)
}
这篇关于在Scala中折断或缩短折叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！