Prolongé en Prolog

Question

Quelle est l'idée générale d'utiliser breadth-first sur le schéma de recherche en profondeur par défaut dans Prolog?

Vous ne prenez pas les branches infinies?

Y at-il de façon générale à utiliser en largeur en Prolog? J'ai été googler autour et je n'ai pas trouvé trop d'informations utiles pour un novice.

Answer 1

L'avantage de largeur d'abord est que vous trouverez toutes les solutions. Avec la profondeur d'abord, vous pouvez rester coincé dans une branche infinie.

L'inconvénient est que largeur d'abord utilise beaucoup de mémoire, il est donc généralement pas utilisé pour l'exécution.

Si vous voulez l'utiliser, vous aurez besoin de mettre en œuvre explicitement avec une sorte de file d'attente.

Éditer: Si vous voulez avoir les avantages de la recherche étendue sans utiliser beaucoup de mémoire, vous pouvez utiliser l'approfondissement itératif. C'est une recherche en profondeur d'abord avec une limite de profondeur, que vous augmentez successivement. Cela provoque des calculs en double, mais si votre espace de recherche n'a pas de longs segments linéaires sans ramification, alors cette duplication est petite.

Answer 2

Il ya quelque chose que je dois savoir que "agenda recherche". En parcourant l'arbre (des données, des relations, des règles, ...) vous maintenez un "agenda" (une liste) de ce qu'il faut faire ensuite. Lorsque vous entrez dans un nœud, vous mettez ses enfants à l'ordre du jour, puis vous continuez avec le premier élément de l'agenda, que vous affichez. De cette façon, si vous mettez de nouveaux éléments à la fin de l'ordre du jour, vous obtenez la largeur d'abord. Si vous les mettez en avant de l'ordre du jour, vous obtenez la profondeur d'abord.

Il est facile à implémenter avec Prolog.

EDIT: Je pourrais tout aussi bien donner une indication de mise en œuvre ici. C'est une implémentation très basique de l'algorithme de recherche d'agenda.

agenda_search([N|T],Mode):- 
    doWithNode(N),   % do whatever you do the searching for 
    getNodeChildren(N,C), 
    (Mode=bf ->    % bf or df (depth-first) 
     append(T,C,A); 
     append(C,T,A)), 
    agenda_search(A,Mode). 

Il repose sur des prédicats externes doWithNode qui est synonyme de l'action que vous souhaitez effectuer à chaque noeud (par exemple comparer les données de noeud à un terme de recherche, sérialiser contenu du nœud, asf.). Et getNodeChildren qui va lier la liste des enfants du nœud donné à C (c'est-à-dire que ce prédicat connaît réellement la structure arborescente et comment trouver des nœuds enfants). Bien sûr, le prédicat doWithNode pourrait avoir besoin de paramètres supplémentaires pour faire son travail, ce qui apparaîtrait également dans la liste des arguments de agenda_search.

Vous pouvez l'appeler comme ceci:

agenda_search([RootNode], bf) % for breadth-first search 

et

agenda_search([RootNode], df) % for depth-first search 

J'ai aussi trouvé un peu d'explication de l'ordre du jour la recherche on this web page. La bonne chose avec la recherche d'agenda est que vous pouvez facilement basculer entre les deux variantes df et bf et jouer avec les résultats. L'algorithme est assez bien comporté en mémoire, car l'ordre du jour, les nœuds qu'il reste à explorer, ne capture qu'une (plus ou moins) petite fraction de nœuds dans l'arbre à la fois (la frange).

Answer 3

Le code pour agenda_search devrait fonctionner correctement. Pour plus d'efficacité, vous pouvez envisager d'utiliser une autre infrastructure de données; en effet, en mode largeur d'abord, toute la liste des nœuds (T) sera traversée par append (T, C, A). Vous pouvez par exemple utiliser le module de bibliothèque (files d'attente) de SICStus. La largeur de la première recherche serait alors la suivante (paramétrée par les prédicats start/1, le prédicat successeur s/2 et le goal goal goal/1). Remarque, j'ai également ajouté la vérification de la boucle.

 
bfs(Res) :- start(Start), empty_queue(EQ), 
    queue_append(EQ,[e(Start,[])],Q1), 
    bfs1(Q1,Res). 

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue), 
    bfs2(Next,Path,NQ,Res). 

bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res). 
bfs2(H,Path,NQ,Res) :- 
       findall(e(Succ,[H|Path]), 
         (s(H,Succ),\+ member(Succ,Path)),AllSuccs), 
       queue_append(NQ,AllSuccs,NewQueue), 
       bfs1(NewQueue,Res). 

(. Vous pouvez également essayer de remplacer/compléter le composant de chemin par une meilleure structure de données, par exemple, AVL arbres) Un exemple de problème à résoudre serait:

 
start(env(0,0)). 
s(env(X,Y),env(X1,Y)) :- X1 is X+1. 
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1. 
goal(env(3,3)). 

Vous pouvez également remplacez la file d'attente par une file d'attente prioritaire et calculez la priorité en utilisant une fonction heuristique. Vous obtenez alors une recherche A * (qui peut émuler la profondeur en premier, la largeur en premier, la meilleure en premier, ...). Le livre de Bratko (Programmation logique pour l'intelligence artificielle) devrait être une bonne source pour lire ce matériel.