Το δένδρο υπολογισμού της Prolog
Όπως τονίσαμε στη προηγούμενη ενότητα, όταν κάνουμε μία ερώτηση στη Prolog ο μηχανισμός ελέγχου «ψάχνει» σειριακά (από πάνω προς τα κάτω) τη βάση δεδομένων για να βρει γεγονότα ή/και κανόνες που κάνουν τα γεγονότα της πρότασης της ερώτησης αληθή. Ο καλύτερος τρόπος για να δούμε πως πραγματοποιείται αυτό το «ψάξιμο» είναι να σχεδιάσουμε το δέντρο υπολογισμού τής συγκεκριμένης ερώτησης.
Το δέντρο υπολογισμού μίας ερώτησης αναπαριστά τον τρόπο με τον οποίο η Prolog ψάχνει μέσα στη βάση δεδομένων για να βρει μία απάντηση.
Παράδειγμα
Εισάγετε τα ακόλουθα γεγονότα και κανόνες χρησιμοποιώντας έναν editor και μετά κάντε consult:
/*1*/ road(thessaloniki,kozani,3).
/*2*/ road(kozani,lamia,2).
/*3*/ road(kozani,ioannina,3).
/*4*/ road(ioannina,preveza,2).
/*5*/ road(ioannina,arta,1).
/*6*/ road(arta,athina,6).
/*7*/ road(arta,rio,6).
/*8*/ road(rio,athina,6).
/*8*/ road(lamia,athina,3).
/*9*/ findroad(X,Y,Ttotal):- road(X,Y,Ttotal).
/*10*/findroad(X,Y,Ttotal):-
road(X,Z,T),
findroad(Z,Y,NewT),
Ttotal is T+NewT.
Η σχέση road(Node1, Node2, T) αναπαριστά: (α) το γεγονός ότι υπάρχει δρόμος (μονής κατευθύνσεως) μεταξύ των κόμβων Node1 και Node2 και (β) ότι ο χρόνος που χρειάζεται κάποιος για να διανύσει τον δρόμο αυτό είναι ίσος με T.
Η διαδικασία findroad(X,Y,Ttotal) βρίσκει όλους τους πιθανούς δρόμους (μονής κατευθύνσεως) μεταξύ των κόμβων Χ, Υ καθώς και τον συνολικό χρόνο που χρειάζεται κανείς για να τους διασχίσει Ttotal.
Στη ερώτηση «Σε ποίες πόλεις μπορώ να πάω από τα Ιωάννινα και με ποιο κόστος?» η Prolog μας δίνει πέντε εναλλακτικές απαντήσεις:
?- findroad(ioannina, P, X).
P = preveza
X = 2;
P = arta
X = 1;
P = athina
X = 7;
P = rio
X = 7;
P = athina
X=13;
No
Πως όμως βρήκε αυτές τις πέντε απαντήσεις? Διασχίζοντας κατά βάθος το ακόλουθο δέντρο υπολογισμού μπορείτε να δείτε πως η Prolog δίνει αυτές τις απαντήσεις. Παρατηρήστε ότι κάθε κόμβος του δένδρου αναπαραστά τη τρέχουσα κατάσταση του σώματος ενός από τους παραπάνω δύο κανόνες και ότι περιέχει πάντα τη μεταβλητή P.
Σύμβολα |
|
 |
Επιτυχία. Η Prolog δίνει μία απάντηση. Aν πατήσετε το πλήκτρο ";" θα συνεχίσει τη κατά βάθος αναζήτηση για να βρει την επόμενη λύση (δηλαδή κάνει backtracking). |
 |
Αποτυχία. Η Prolog κάνει αυτόματα backtracking προσπαθώντας να βρει μία λύση. |
| (N) | Ο αριθμός του κανόνα ή του γεγονότος που ικανοποιείται ή προσπαθεί να ικανοποιήσει. |
| (?-) | Η τρέχουσα ερώτηση που κάνει η Prolog και για την οποία προσπαθεί να βρει μία λύση. |
| ({…}) | Οι ενοποιήσεις των μεταβλητών της τρέχουσας ερώτησης (και μόνο αυτής) που πραγματοποιεί η Prolog χρησιμοποιώντας το μηχανισμό ενοποίησης. |
| Κόμβος δένδρου: | Συμβολίζει μία στοίβα που η Prolog χρησιμοποιεί για να αποθηκεύει τις τρέχουσες ερωτήσεις. Τα παιδιά κάθε κόμβου αντιστοιχούν σε ταυτοποιήσεις του πρώτου στοιχείου της στοίβας. Αν η ταυτοποίηση γίνεται με ένα γεγονός της Prolog τότε γράφουμε μόνο τις τιμές που έχουν πάρει οι μεταβλητές αλλιώς αν η ταυτοποίηση γίνεται με έναν κανόνα τότε εισάγουμε στο πάνω μέρος της στοίβας το σώμα του κανόνα. |
| Τελευταία ενημέρωση σελίδας: 25/11/2006 |