Πώς ο Βοηθός Πιλότου Ανακάλυψε Συντομότερη Διαδρομή: Το Μάθημα του Traveling Salesman Problem

Φανταστείτε το εξής σκηνικό:

Στην αυστραλιανή ενδοχώρα υπάρχουν 20 ράντσα που επισκέπτεται κάθε μήνα ένας κτηνίατρος με μικρό αεροπλάνο. Σε μία από αυτές τις πτήσεις, ο βοηθός του, που πετάει μαζί του, παρατηρεί κάτι από το παράθυρο:

«Μόλις περάσαμε από μια διαδρομή που είχαμε ξαναπεράσει πριν λίγες ώρες. Άρα υπάρχει σίγουρα πιο σύντομη διαδρομή από αυτή που κάνουμε τώρα.»

Ο κτηνίατρος χαμογελά και του λέει ότι:

1. Υπάρχουν πάνω από
   $2.4 \times 10^{18}$ διαφορετικές δυνατές περιηγήσεις στα 20 ράντσα (όλες οι δυνατές σειρές επίσκεψης).

2. Ο βοηθός δεν ξέρει ποια ακριβώς διαδρομή ακολουθούν.

3. Ο βοηθός δεν έχει ξαναπετάξει καμία τέτοια πλήρη διαδρομή στο παρελθόν.

Κι όμως… ο βοηθός έχει δίκιο. Και μάλιστα μπορεί να το αποδείξει χωρίς να ξέρει τη διαδρομή και χωρίς να κάνει κανέναν τεράστιο υπολογισμό.

Πώς γίνεται αυτό;

Δείτε την απάντηση εδώ.