[PROLOG]Chiarimenti e piccolo problema

[D4rkAng3l]

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

[yorkeiser]

Provo a risponderti cercando di rispolverare qualche antico neurone sopito.
Hai intuito bene; senza addentrarmi nei dettagli, il Prolog crea a runtime degli alberi and-or su cui va a cercare tutte le soluzioni, facendo back-tracking nel caso in cui un ramo dell'albero fallisca e continuando a cercarne sugli altri rami. In sostanza, nel tuo programma (che mi sembra corretto concettualmente) la ricorsione è già implementata nell'istruzione

connesso(Iniziale, Finale):- arco(Iniziale, Intermedio), arco(Intermedio, Finale).

e non mi sembra tu debba aggiungere altro. Sul perchè il compilatore ti dica che i nodi non sono connessi, boh... Che compilatore stai usando? Purtroppo non ho attualmente un interprete Prolog installato qui. Se la memoria non m'inganna, sull'interprete che si usava noi all'uni (non ricordo assolutamente quale fosse) per farti ritornare la risposta dovevi far precedere l'asserzione da un punto di domanda:

? connesso(a,e)

[marco.r]

Originariamente inviato da D4rkAng3l

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).

Il codice che riporti presenta un problema: permette di cercare nodi distanti al piu' due archi.
Per renderlo generico devi farlo effettivamente ricorsivo, qualcosa del tipo

connesso(Iniziale, Finale):- arco(Iniziale, Finale).
connesso(Iniziale, Finale):- arco(Iniziale, Intermedio), connesso(Intermedio, Finale).

Ma il meccanismo di ricorsione è implementato direttamente nel prolog? (cioè tipo in C dovrei scrivere io in modo tale che ci sia una ricorsione....)

si'

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?

Quando tu scrivi connesso(a,e) l'interprete cerca di "unificare" il tuo input con una qualsiasi definizione del predicato "connesso", andando in ordine di inserimento. Quindi per prima cosa prova

connesso(Iniziale, Finale):- arco(Iniziale, Finale).

Con a ed e al posto di Iniziale e Finale. Il tuo predicato dice che connesso(a,e) e' vero se e' vero arco(a,e), cosa che non gli risulta per cui il tentativo fallisce. A questo punto viene fatto il backtracking e rifatto il tentativo di con la definizione successiva, e via cosi'.

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?

Per l'errore di cui parlavo sopra: a->b->c->e non lo trovi con la tua versione del codice (tre archi ).

[D4rkAng3l]

ah è vero che deficiente che sono...grazie della correzione e delle chiarificazioni...solo una cosa mi potresti chiarire il concetto di unificazione?

Grazie
Andrea

[marco.r]

Originariamente inviato da D4rkAng3l

ah è vero che deficiente che sono...grazie della correzione e delle chiarificazioni...solo una cosa mi potresti chiarire il concetto di unificazione?

Grazie
Andrea

Detto in modo "un po'" informale, unifichi due termini quando riesci a sostituire le variabili libere in modo da ricondurli entambi ad uno stesso terzo termine.
Ad esempio se io cerco di unificare i predicati arco(a,B) e arco(C,d) ottengo che devo sostituire la variabile C con a e la B con d, ottenendo arco(a,d)
Ovviamente se invece di variabili ho da entrambi i lati qualcosa che non sia una variabile, l'unico modo perche' questo possa accadere e' che i due termini siano uguali. Posso fare tutti i salti mortali che voglio, ma non riusciro' mai ad unificare arco(a,B) con arco(c,D) perche' a e c sono atomi diversi.

[D4rkAng3l]

Grazie,
spiegazione perfetta :-) ora ho capito, si lo aveva detto anche il professore...mannaggia a me che mi rivedo gli appunti con una settimana di ritardo e poi mi sfuggono alcune cose