💧 Ο Αλγόριθμος Λύσης

Το Πρόβλημα

Δίνονται δύο δοχεία χωρητικότητας Α και Β λίτρων και μια πηγή με άφθονο νερό. Επιτρέπονται μόνο τρεις ενέργειες: γέμισμα ενός δοχείου μέχρι πάνω, άδειασμά του εντελώς, και μεταφορά νερού από το ένα στο άλλο μέχρι να γεμίσει ή να αδειάσει το πηγαίο.

Ζητείται να μετρήσουμε ακριβώς Στόχος λίτρα σε κάποιο από τα δύο δοχεία.

Πότε Λύνεται — Πότε Όχι

Ο Αλγόριθμος (BFS / Εξαντλητική Αναζήτηση)

Η γενική μέθοδος αντιμετωπίζει το πρόβλημα ως αναζήτηση γράφου. Κάθε κατάσταση είναι ένα ζεύγος (waterA, waterB) και οι ακμές είναι οι έξι δυνατές ενέργειες. Χρησιμοποιούμε BFS (Breadth-First Search) για να βρούμε το συντομότερο μονοπάτι από (0, 0) στην πρώτη κατάσταση που περιέχει τον στόχο.

• Ξεκινάμε από (0, 0) και προσθέτουμε στην ουρά.
• Για κάθε κατάσταση εφαρμόζουμε και τις 6 ενέργειες.
• Αν η νέα κατάσταση δεν έχει επισκεφθεί, την προσθέτουμε.
• Σταματάμε όταν βρούμε κατάσταση με waterA = Στόχος ή waterB = Στόχος.
• Το BFS εγγυάται ότι βρίσκουμε τη λύση με τις λιγότερες κινήσεις.

Η «Αριθμητική» Μέθοδος (Εκτεταμένος Αλγόριθμος Euclid)

Υπάρχει και αναλυτική κατανόηση: με επαναλαμβανόμενο γέμισμα του Α και άδειασμα στο Β (ή αντίστροφα), παράγουμε όλα τα πολλαπλάσια του ΜΚΔ(Α,Β) μέχρι το lcm(Α,Β). Αυτό είναι η ουσία του θεωρήματος Bézout: υπάρχουν ακέραιοι x,y ώστε:

Άρα κάθε πολλαπλάσιο του ΜΚΔ είναι εφικτό. Η πρακτική εφαρμογή:

• Στρατηγική Α→Β: Γέμισε Α, άδειασε στο Β. Όταν γεμίσει το Β, άδειασέ το εντελώς. Επανάλαβε.
• Στρατηγική Β→Α: Το ίδιο ξεκινώντας από Β. Συχνά δίνει διαφορετικό πλήθος κινήσεων.

Παραδείγματα

Πολυπλοκότητα

Ο χώρος καταστάσεων έχει (Α+1)×(Β+1) κόμβους, άρα ο BFS τρέχει σε O(Α·Β) χρόνο και μνήμη — πρακτικά στιγμιαίο για τα μεγέθη του παιχνιδιού.

🏆 Κατάταξη Παικτών