D4rkAng3l
02-11-2007, 18:16
Invia un messaggio MSN a D4rkAng3l
PROLOG, ricerca connessione su un grafo
ed ecco quà i primi dubbietti su questo astruso sistema.
Allora col prolgo è facile rappresentare i grafi...basta rappresentare le connessioni tra i vari nodi quindi magari potrei avere un coso del genere nella dichiarazione dei fatti:
arco(a, g).
arco(a, b).
arco(b, c).
arco(b, f).
arco(c, d).
arco(c, e).
Poi nella dichiarazione delle regole dichiaro due regole che mi dicono se un certo nodo è connesso ad un altro nodo
connesso(Iniziale, Finale):- arco(Iniziale, Finale).
connesso(Iniziale, Finale):- arco(Iniziale, Intermedio), arco(Intermedio, Finale).
La prima regola corrisponde alla situazione più semplice possibile (ed è il caso base della ricorsione) cioè che i due nodi di cui mi chiedo se c'è un cammino che mi porti dal primo al secondo sono connessi direttamente tra loro.
Il secondo caso invece presuppone che ci siano una serie di nodi intermedi e si usala ricorsione per cercare un cammino...ma non mi torna del tutto e ho dei dubbi.
Ma il meccanismo di ricorsione è implementato direttamente nel prolog? (cioè tipo in C dovrei scrivere io in modo tale che ci sia una ricorsione....)
Sull'esempio che ho che fa riferimento a quel grafo fà il caso che voglio scoprire se c'è un cammino a partire dal nodo A che mi porta nel nodo E e c'è scritto:
si chiede se A è direttamente connesso con E e la prima regola fallisce (ok...)
Allora prova con G come nodo intermedio ma fallisce (fallisce perchè G è foglia?)
allora prova ad usare B come nodo intermedio ma B non è connesso direttamente con E quindi considera C che è connesso con E e può dire che esiste un percorso tra A ed E
Ma questo meccanismo di ricorsione in pratica come cavolo funziona?
La mia ipotesi è che per esempio: prova a connettere A e C usando come nodo intermdio B ma C non è il nodo finale, allora B diventa (ricorsivamente) il nodo iniziale, C quello intermedio e C è connesso ad E. Se il cammino non portava ad un nodo finale tornava indietro e provava un altro cammino...funziona così la ricorsione in PROLOG o mi manca qualcosa? mmm se non stò dicendo minchiate mi viene da supporre che abbia nativo un meccanismo di ricorsione e back tracking o sbaglio?
Altra cosa che non mi funziona a livelli pratico:
se nell'interprete lancio il comando:
connesso(a,e).
mi dice di NO anche se è connesso ed in teoria dovrebbe funzionare...why?
Grazie
Andrea
PROLOG, ricerca connessione su un grafo
ed ecco quà i primi dubbietti su questo astruso sistema.
Allora col prolgo è facile rappresentare i grafi...basta rappresentare le connessioni tra i vari nodi quindi magari potrei avere un coso del genere nella dichiarazione dei fatti:
arco(a, g).
arco(a, b).
arco(b, c).
arco(b, f).
arco(c, d).
arco(c, e).
Poi nella dichiarazione delle regole dichiaro due regole che mi dicono se un certo nodo è connesso ad un altro nodo
connesso(Iniziale, Finale):- arco(Iniziale, Finale).
connesso(Iniziale, Finale):- arco(Iniziale, Intermedio), arco(Intermedio, Finale).
La prima regola corrisponde alla situazione più semplice possibile (ed è il caso base della ricorsione) cioè che i due nodi di cui mi chiedo se c'è un cammino che mi porti dal primo al secondo sono connessi direttamente tra loro.
Il secondo caso invece presuppone che ci siano una serie di nodi intermedi e si usala ricorsione per cercare un cammino...ma non mi torna del tutto e ho dei dubbi.
Ma il meccanismo di ricorsione è implementato direttamente nel prolog? (cioè tipo in C dovrei scrivere io in modo tale che ci sia una ricorsione....)
Sull'esempio che ho che fa riferimento a quel grafo fà il caso che voglio scoprire se c'è un cammino a partire dal nodo A che mi porta nel nodo E e c'è scritto:
si chiede se A è direttamente connesso con E e la prima regola fallisce (ok...)
Allora prova con G come nodo intermedio ma fallisce (fallisce perchè G è foglia?)
allora prova ad usare B come nodo intermedio ma B non è connesso direttamente con E quindi considera C che è connesso con E e può dire che esiste un percorso tra A ed E
Ma questo meccanismo di ricorsione in pratica come cavolo funziona?
La mia ipotesi è che per esempio: prova a connettere A e C usando come nodo intermdio B ma C non è il nodo finale, allora B diventa (ricorsivamente) il nodo iniziale, C quello intermedio e C è connesso ad E. Se il cammino non portava ad un nodo finale tornava indietro e provava un altro cammino...funziona così la ricorsione in PROLOG o mi manca qualcosa? mmm se non stò dicendo minchiate mi viene da supporre che abbia nativo un meccanismo di ricorsione e back tracking o sbaglio?
Altra cosa che non mi funziona a livelli pratico:
se nell'interprete lancio il comando:
connesso(a,e).
mi dice di NO anche se è connesso ed in teoria dovrebbe funzionare...why?
Grazie
Andrea