Επόμενη: SLDNF -Ανάλυση Πάνω Επίπεδο: Ανάλυση Προηγούμενη: SLD -Ανάλυση 

4.7 SLD -Δέντρα

Ο χώρος αναζήτησης μιας SLD- παραγωγής (και άρνησης) μπορεί να αναπαρασταθεί από ένα δέντρο που ονομάζεται SLD- δέντρο. Αν  είναι ένα οριστικό πρόγραμμα, G ένας οριστικός στόχος κι αν υποθέσουμε ότι σε καθεμιά από τις προτάσεις του  αντιστοιχεί ένας μοναδικός αριθμός, ονομάζουμε SLD- δέντρο για το , ένα δέντρο στο οποίο

• Η ρίζα είναι ο στόχος G.
• Κάθε κόμβος είναι είτε ένας οριστικός στόχος είτε η κενή πρόταση.
• Αν


είναι ένας κόμβος του δέντρου με επιλεγμένο άτομο το A_s, , τότε για κάθε πρόταση  του  τέτοια ώστε μια παραλλαγή της C και του A_s να είναι ενοποιήσιμες με mgu , υπάρχει ακριβώς ένας κόμβος - απόγονος (κόμβος - παιδί), ο οποίος είναι το αναλυθέν των  και C και έχει τη μορφή

Η ακμή ανάμεσα στον κόμβο και το παιδί του, έχει για ετικέτα τον αριθμό της πρότασης C.
• Κόμβοι οι οποίοι είναι κενές προτάσεις δεν έχουν παιδιά.

  
Σχήμα 4.7α : SLD- άρνηση με επιλογή του δεξιότερου στόχου
 

'Ενα SLD- δέντρο μπορεί να περιέχει τριών ειδών κλαδιά. Κλαδιά τα οποία είναι μονοπάτια από τη ρίζα σε φύλλα που έχουν την κενή πρόταση για στόχο τους, αντιστοιχούν σε μια άρνηση του  και ονομάζονται κλαδιά επιτυχίας (success branches). Το δεύτερο είδος κλαδιών είναι εκείνα τα οποία είναι μονοπάτια από τη ρίζα σε φύλλα που έχουν μη-κενές προτάσεις για στόχους, από τις οποίες δεν είναι δυνατά περαιτέρω βήματα παραγωγής. Τούτο σημαίνει ότι το επιλεγμένο άτομο σ' έναν τέτοιο στόχο δεν είναι ενοποιήσιμο με καμία κεφαλή πρότασης του προγράμματος. Αυτά τα κλαδιά ονομάζονται κλαδιά αποτυχίας (failure branches). Το τρίτο είδος κλαδιών είναι τα άπειρα - αντιστοιχούν σε άπειρες SLD- παραγωγές και δεν οδηγούν πουθενά. Για παράδειγμα, ας θεωρήσουμε το πρόγραμμα που δώσαμε και προηγούμενα:
 

Το SLD- δέντρο του σχήματος 4.7β , δημιουργήθηκε με χρήση του κανόνα επιλογής (ή υπολογισμού) που επιλέγει πάντοτε το αριστερότερο άτομο σ' ένα στόχο (υπογραμμισμένα). Οι υπολογισμένες απαντήσεις (αντικατάσταση της μεταβλητής x) φαίνονται δίπλα στα δύο κλαδιά επιτυχίας τα οποία τελειώνουν μ' ένα ``κενό'' () φύλλο.

  
Σχήμα 4.7β: SLD- δέντρο ενός απλού προγράμματος
 
 

Mon Apr 5 16:25:43 EEST 1999