Χάνεστε σε ένα δάσος. Πώς βγαίνετε;

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

Ο στόχος σου είναι να βρεις τη συντομότερη διαδρομή για να βγεις έξω, ανεξάρτητα από το αρχικό σου σημείο. Αυτό που ψάχνουμε είναι μια στρατηγική—μια πορεία που να εγγυάται τη μέγιστη απόσταση που θα χρειαστεί να περπατήσεις, ακόμα και στη χειρότερη περίπτωση, να είναι η μικρότερη δυνατή.

Γνωστές Λύσεις

1. Κύκλος: Αν το δάσος είναι κυκλικό, η βέλτιστη στρατηγική είναι απλή: περπατάς σε ευθεία γραμμή προς οποιαδήποτε κατεύθυνση μέχρι να βγεις. Η μέγιστη απόσταση που θα χρειαστεί να διανύσεις είναι η διάμετρος του κύκλου ($2r$, όπου $r$ η ακτίνα). Αυτό είναι το ελάχιστο δυνατό, γιατί αν ξεκινήσεις από τη μία άκρη και πρέπει να φτάσεις στην απέναντι, δεν υπάρχει συντομότερος τρόπος.
2. Τετράγωνο: Εδώ τα πράγματα γίνονται πιο ενδιαφέροντα. Η βέλτιστη στρατηγική περιλαμβάνει το να περπατήσεις με μια συγκεκριμένη σπαστή διαδρομή που ελαχιστοποιεί τη μέγιστη απόσταση στη χειρότερη περίπτωση. Για ένα τετράγωνο με πλευρά μήκους $1$, η απόσταση αυτή είναι περίπου 1.118 (όχι ακριβώς √2, όπως θα περίμενε κανείς intuitive, αλλά μια πιο περίπλοκη τιμή που προκύπτει από βελτιστοποίηση).
3. Τρίγωνο: Και εδώ μπαίνουμε στο άλυτο μυστήριο! Για ένα ισόπλευρο τρίγωνο, ας πούμε με πλευρά 1, οι μαθηματικοί δεν έχουν βρει ακόμα την απόλυτα βέλτιστη στρατηγική. Μια προτεινόμενη διαδρομή είναι να πας προς το κέντρο του τριγώνου και μετά να κατευθυνθείς προς μια κορυφή, αλλά αυτή δεν έχει αποδειχθεί ότι είναι η καλύτερη. Η μέγιστη απόσταση στη χειρότερη περίπτωση εξαρτάται από το πού ξεκινάς, και η ελαχιστοποίηση αυτής της απόστασης παραμένει ανοιχτό πρόβλημα.

Γιατί είναι τόσο δύσκολο;

Το πρόβλημα είναι δύσκολο γιατί:

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

Μια σκέψη για το τρίγωνο

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