J'ai écrit une simple recherche de profondeur-première à Scala avec une fonction récursive comme celle-là: où Labyrinthe est une spécification du problème (comme graphique ou autre), le chemin est un chemin Liste qui détient le chemin pris jusqu'à présent et l'objectif est une spécification de l'état de but. La fonction renvoie un chemin vers le but en tant que liste et nul si aucun chemin ne peut être trouvé. P> La fonction se développe, par ex. trouve tous les prochains nœuds suivants appropriés (candidats), puis doit s'appeler récursivement. P> Je fais cela par p> candidates.foldLeft(Nil){
(solution, next) =>
if( solution == Nil )
search( labyrinth, next :: path, goal )
else
solution
}
3 Réponses :
Je ne suis pas sûr de comprendre le désir de court-circuit la boucle. Est-ce cher à itérer à travers les candidats? Est la liste des candidats potentiellement gros?
Peut-être que vous pourriez utiliser la méthode "Rechercher": P>
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)
}
Il n'y aura plus d'empilement de pile sur Rechercher qu'il ya utiliser refinbleft . En utilisant trouver est l'ajustement parfait pour ce qu'il veut: Obtenez le premier candidat pour lequel une solution peut être trouvée.
Droit. Mais, en fonction du domaine problématique, des débordements de pile pourraient être un problème pour ZiggyStar, orthogonalement à la question initiale. Hey, je viens d'avoir une idée pour une question!
Cela ressemble à une bonne solution. Merci beaucoup. Et: les problèmes de recherche ne sont pas gros. La question se pose simplement de la curiosité de la façon de le faire "à droite".
J'aime Solution Mitch Blevins , car il s'agit d'une correspondance parfaite pour votre algorithme. Vous pouvez être intéressé par Ma propre solution à un autre problème de labyrinthe.
OK, il y a donc beaucoup d'interprétations ici, votre question manque de degrés de spécificité.
Je vais essayer de souligner toutes les hypothèses que je vais.
fonction existante: ( Premières hypothèses: Tapez les signatures ) La fonction se développe, par ex. Trouve tous les prochains nœuds suivants appropriés (candidats), puis doivent s'appeler récursivement.
Assomption: le code suivant est dans la recherche Veuillez noter que j'ai omis quelques détails inessayés.
Si mes hypothèses ont été correctes, alors peut-être, mais je devais toujours déduire certaines choses. Ne supposez jamais la nécessité des détails de la mise en œuvre lors de la mise en œuvre de la mise en œuvre, la spécificité facilite la réponse. questions beaucoup plus simples. Y a-t-il un moyen d'éviter cela en brisant le repliement ou peut-être en utilisant une fonction différente au lieu de replier?
Pourquoi ne pas utiliser de récursion? maintenant dès que nous trouvons un chemin "valide", note qu'il n'y a pas de chèque pour cela dans la logique I ont fourni, donc je ne suis pas tout à fait sûr si cela se terminerait comme vous l'avez mis en œuvre et comme je l'ai mis en œuvre, mais les concepts sont toujours valides.
recherche
Qu'essayez-vous d'éviter exactement? Il n'y a pas de copie qui ne va nulle part.
Il ne devrait-il pas entrer au moins un appel de fonction pour chaque élément restant de la liste?
Avec le repli, oui. Mais, encore une fois, Refinbleft est en train d'être plié pour faire quelque chose qu'il n'était pas destiné à.
Découvrez cette réponse: Stackoverflow.com/a/12897950/777833