ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΒΟΣΚΟΥ

Ένας βοσκός βρίσκεται στην άκρη ενός ποταμού έχοντας ένα πρόβατο, σανό και ένα κακό λύκο. Το πρόβατο τρώει το σανό και ο λύκος το πρόβατο, αλλά όταν είναι και ο βοσκός μαζί κάθονται φρόνιμα. Θέλουν να περάσουν ένα ποτάμι με μια βάρκα η οποία χωράει μόνο 2 άτομα. Πώς θα περάσουν χωρίς να έχουμε απώλειες;

ΘΑ ΠΑΡΕΙ ΠΡΩΤΑ ΤΟ ΠΡΟΒΑΤΟ ΘΑ ΤΟ ΠΕΡΑΣΕΙ ΑΠΕΝΑΝΤΙ.
ΜΕΤΑ ΘΑ ΠΑΡΕΙ ΤΟΝ ΛΥΚΟ ΘΑ ΤΟΝ ΠΑΕΙ ΑΠΕΝΑΝΤΙ.
ΜΟΛΙΣ ΤΟΝ ΠΑΕΙ,
ΘΑ ΠΑΡΕΙ ΤΟ ΠΡΟΒΑΤΟ ΘΑ ΤΟ ΓΥΡΙΣΕΙ ΠΙΣΩ.
ΜΕΤΑ ΘΑ ΠΑΡΕΙ ΚΑΙ ΤΟ ΣΑΝΟ
ΘΑ ΤΟΝ ΠΕΡΑΣΕΙ ΑΠΕΝΑΝΤΙ.
ΘΑ ΓΥΡΙΣΕΙ ΠΙΣΩ ΘΑ ΠΑΡΕΙ ΚΑΙ ΤΟ ΠΡΟΒΑΤΟ ΚΑΙ ΕΤΟΙΜΟΣ!

Το πρόβλημα του βοσκού αποτελεί ένα κλασσικό πρόβλημα λογικής (puzzle). Σε μια όχθη ενός ποταμού υπάρχουν ένας βοσκός, ένας λύκος ένα πρόβατο και ένα δεμάτι σανός. Η διαθέσιμη βάρκα χωρά μόνο δύο αντικείμενα κάθε φορά. Αν υποθέσουμε ότι σε κάθε στιγμή ο λύκος και το πρόβατο, καθώς και το πρόβατο και το δεμάτι δεν μπορούν να είναι μόνα τους σε μία όχθη (χωρίς τον βοσκό), ποια είναι η ακολουθία κινήσεων η οποία πρέπει να γίνει για να περάσουν όλοι απέναντι; Το παραπάνω πρόβλημα είναι ουσιαστικά ένα πρόβλημα σχεδιασμού κινήσεων (Planning). Στα προβλήματα της κατηγορίας αυτής, μια λύση είναι η αναζήτηση στο χώρο των καταστάσεων του κόσμου του προβλήματος. Κάθε τέτοια κατάσταση περιγράφει τον "κόσμο" του προβλήματος την συγκεκριμένη χρονική στιγμή. Οι μεταβάσεις από μια συγκεκριμένη κατάσταση σε μια επόμενη γίνονται μέσω τελεστών.

Αριστoτέλειο Πανεπιστήμιο Θεσσαλονίκης