Newsgroup: it.comp.ia
Titolo: Visita alberi in profondità e in larghezza con prolog

Salve a tutti sto studiando per l'esame di intelligenza artificiale
della mia facoltà Scienze dell'Informazione, sono arrivato allo studio
degli alberi e la visita in profondità e in larghezza con Prolog , ma
non riesco a capirci molto.cè qualcuno che può spiegarmi come
funziona oppure darmi il link di qualche sito dove è spiegato in
maniera chiara?
Grazie a tutti anticipatamente

 Grazie a tutti anticipatamente
Temo di non aver capito... ti interessa la visita in profondità in
generale oppure specificatamente in Prolog?
Pier


Entrambi i metodi hanno bisogno di appoggiarsi ad una struttura dati che 
ti indica "quali cose devi ancora fare": in profondita` la struttura 
dati e` una pila (LIFO: Last In First Out), nella ricerca in ampiezza e` 
una coda (FIFO: First In First Out). Ovviamente dipende da come decidi 
di rappresentare gli alberi. Supponiamo di rappresentare un albero 
binario con un termine
	tree(SottoalberoSinistro,Dato,SottoalberoDestro)
e che il simbolo
	[]
rappresenti un albero vuoto.
Ad esempio,
tree(tree([],a,tree([],b,[])),c,tree([],d,[]))
rappresenta l'albero
           c
          / \
         a   d
          \
           b
Per la ricerca in profondita` non hai bisogno di creare tu una struttura 
LIFO, perche' puoi usare lo stack delle attivazioni di Prolog, quindi 
tutto e` molto semplice: scrivi le cose come sono piu` naturali in logica.
Puoi dire:
Ho trovato l'elemento che cerco se la radice dell'albero coincide 
(unifica) con quell'elemento:
	depth(tree(Left,X,Right),X).
In alternativa, ho trovato l'elemento se e` nel sottoalbero di sinistra:
	depth(tree(Left,_,Right),X):- depth(Left,X).
Oppure in quello di destra:
	depth(tree(Left,_,Right),X):- depth(Right,X).
Facendo girare questo programma, ottieni:
	?- depth(tree(tree([],a,tree([],b,[])),c,tree([],d,[])),X).
	X=c ;
	X=a ;
	X=b ;
	X=d ;
	no
Per la ricerca in ampiezza, sei tu che devi costruirti una coda FIFO. 
Allora il predicato breadth potrebbe avere due parametri che sono
1. la coda FIFO
2. il valore da cercare.
Per l'esempio di prima, dovremo poi invocarlo con
	breadth([tree(tree([],a,tree([],b,[])),c,tree([],d,[]))],X).
cioe` mettendo nella lista delle cose da fare la radice dell'albero.
A questo punto potremmo ragionare cosi`:
Se il primo elemento della lista e` un albero vuoto, passo all'elemento 
successivo
	breadth([[]|L],X):- breadth(L,X).
Se il primo elemento della lista e` un albero che nella radice contiene 
il dato che cerco, ho trovato l'elemento:
	breadth([tree(Left,X,Right)|L],X).
In alternativa, devo prendere i 2 figli del nodo radice e metterli in 
fondo alla lista delle cose da fare; posso usare il predicato append che 
collega due liste. Poi, invoco ricorsivamente breadth sulla nuova lista 
di cose da fare:
	breadth([tree(Left,_,Right)|L],X):-
		append(L,[Left,Right],Lnew),
		breadth(Lnew,X).
Nell'esempio di prima ottieni:
	?-breadth([tree(tree([],a,tree([],b,[])),c,tree([],d,[]))],X).
	X=c ;
	X=a ;
	X=d ;
	X=b ;
	no
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Grazie mille per la spiegazione, finalmetne sono riuscito a capire
questi benedetti alberi!!!!!!
Grazie ancora
Ciao Andrea
Marco Gavanelli ha scritto:
