Θεωρείστε το παιχνίδι με δύο δίσκους και 3 καρφιά (βλέπε σχήμα). Θέλουμε να μετακινήσουμε και τους δύο δίσκους από το αριστερό καρφί στο δεξιό καρφί. Να βρείτε μια λύση:

Α. Με Depth First έρευνα.

Β. Με Breadth First έρευνα.
 

Περιορισμοί:

1. Μόνο ένας δίσκος μπορεί να μετακινηθεί κάθε φορά.

2. Ο μεγάλος δίσκος δεν επιτρέπεται να τεθεί πάνω στο μικρό.

Παρατήρηση: και στις δύο περιπτώσεις εξασφαλείστε ότι κανένας δρόμος δεν περνάει από τον ίδιο κόμβο δύο φορές.
 

Λύση

Προκειμένου να διεξάγουμε μια έρευνα (είτε κατά βάθος είτε κατά πλάτος), πρέπει πριν από οτιδήποτε να γράψουμε τους κανόνες με τους οποίους μεταβαίνουμε από μια κατάσταση σε μια άλλη. Αυτούς τους κανόνες θα τους τηρήσουμε με απόλυτη συνέπεια ως προς τη σειρά διαδοχής τους, έτσι ώστε το δένδρο έρευνας να παραχθεί κατά ένα συστηματικό τρόπο. Τους κανόνες τους οποίους θα βγάλουμε, θα βρίσκονται σε μια διατεταγμένη σειρά με την οποία θα τους εφαρμόσουμε σε κάθε κόμβο. Αυτή τη σειρά μπορούμε να την εκλέξουμε μια φορά (στον ορισμό του προβλήματος) και κατόπιν πρέπει να την ακολουθούμε σαν το ευαγγέλιο.

Έτσι, για τη δεδομένη άσκηση, εκλέγουμε τους κανόνες τοποθέτησης των δίσκων με την ακόλουθη σειρά:

R₁. Τοποθέτησε το δίσκο Α στο καρφί 3.

R₂. Τοποθέτησε το δίσκο Α στο καρφί 2.

R₃. Τοποθέτησε το δίσκο Α στο καρφί 1.

R₄. Τοποθέτησε το δίσκο Β στο καρφί 2.

R₅. Τοποθέτησε το δίσκο Β στο καρφί 3.

R₆. Τοποθέτησε το δίσκο Β στο καρφί 1.

Να επισημάνουμε εδώ, ότι θα μπορούσε να υπάρξει μια διαφορετική εκλογή κανόνων (που θα μπορούσε να οδηγήσει και σε διαφορετικό αριθμό τους) ή διαφορετική σειρά στους παραπάνω κανόνες. Πάντως, τώρα που τους βάλαμε στην παραπάνω σειρά, δεν έχουμε δικαίωμα να εφαρμόσουμε με διαφορετική σειρά κατά την έρευνα κατά βάθος ή πλάτος.

Παρατηρήστε το σχήμα 1 που δείχνει το διάγραμα έρευνας κατά βάθος. Δέστε πως οι κανόνες εφαρμόζονται, σε κάθε επίπεδο, ξεκινώντας πάντα από τον κανόνα νούμερο 1 και προχωρώντας στον επόμενο. Οι κόμβοι είναι αριθμημένοι κατά σειρά επίσκεψης πάνω αριστερά. Όπως φαίνεται από το σχήμα, οι κόμβοι 1, 2, 3, 7 (σκούρο γκρι χρώμα) είναι μη επιτρεπτοί κόμβοι και για αυτό αμέσως μετά την επίσκεψη τους επιστρέφουμε στον κόμβο-πατέρα (διαδικασία backtracking). Οι κόμβοι 6, 8, 9 (κυανό χρώμα) έχουν προηγηθεί (οι κόμβοι 6, 9 ταυτίζονται με τον κόμβο 5, ενώ ο κόμβος 8 ταυτίζεται με τον κόμβο 4), για αυτό και δεν αναλύονται περισσότερο (διαδικασία backtracking). Εντέλει η λύση βρίσκεται στο δρόμο R4-R1-R5 (κίτρινο χρώμα) σύμφωνα πάντα με το σύστημα κανόνων που έχουμε ορίσει.

Στο σχήμα 2 βλέπουμε το διάγραμμα έρευνας κατά πλάτος. Προκειμένου να το φτιάξουμε αυτό, εκτελούμε και τους 6 κανόνες σε κάθε κόμβο και κατόπιν απορρίπτουμε τους μη επιτρεπτούς ή ήδη αναπτυγμένους κόμβους. Εννοείται ότι όταν φθάσουμε στον κόμβο στόχο, σταματάμε την έρευνα. Παρατηρήστε τις διαφορές ως προς το μέγεθος της αναζήτησης των δύο αλγορίθμων. Η μεν έρευνα κατά βάθος ανέπτυξε 10 κόμβους και βρήκε τη λύση σε βάθος 3, ενώ η έρευνα κατά πλάτος ανέπτυξε 23 κόμβους βρίσκοντας τη λύση πάλι σε βάθος 3.

Σχήμα 1: Αναζήτηση κατά βάθος.

 

Λύση - Επιμέλεια : Γιάννης Πανταζόπουλος