📌 Το Πρόβλημα
Η πράκτορας του FBI, Άλις, καταδιώκει τον διαβόητο χάκερ Μπομπ, ο οποίος έχει βρει καταφύγιο σε μία από τις 17 σπηλιές. Οι σπηλιές είναι διατεταγμένες σε ευθεία γραμμή.
- Κάθε νύχτα, ο Μπομπ μετακινείται σε μια γειτονική σπηλιά: είτε αριστερά είτε δεξιά.
- Η Άλις μπορεί να ψάχνει δύο οποιεσδήποτε σπηλιές κάθε μέρα.
Ερώτημα: Ποιος είναι ο ελάχιστος αριθμός ημερών που χρειάζεται η Άλις για να είναι βέβαιη ότι θα πιάσει τον Μπομπ, ανεξάρτητα από το πού ξεκινά ή πώς κινείται;
🧠 Η Λύση
Αυτό το πρόβλημα είναι κλασικό παράδειγμα καταδίωξης κινούμενου στόχου με περιορισμένες ενέργειες. Παρόμοια προβλήματα εμφανίζονται στην πληροφορική, την τεχνητή νοημοσύνη και τις θεωρίες αναζήτησης.
Η βασική ιδέα είναι να εφαρμόσουμε μια στρατηγική σάρωσης των σπηλιών, όπου κάθε μέρα η Άλις ελέγχει δύο σπηλιές με τρόπο που "παγιδεύει" τον Μπομπ, όποιες κι αν είναι οι κινήσεις του.
Αν η Άλις ακολουθήσει την κατάλληλη στρατηγική, τότε:
- Θα είναι εγγυημένο ότι θα τον πιάσει
- Και αυτό θα συμβεί σε το πολύ 9 ημέρες!
Απάντηση: Ο ελάχιστος εγγυημένος χρόνος για τη σύλληψη είναι 9 ημέρες.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου