Ο άπληστος κύκλος μέσω ενός συνόλου σημείων είναι η διαδρομή που ακολουθεί ένας περιοδεύων πωλητής (TSP - Travelling Salesman Problem) με τον εξής απλό, «άπληστο» κανόνα:
Ξεκινάει από ένα σημείο και κάθε φορά πηγαίνει στο πλησιέστερο μη επισκεφθέν σημείο, μέχρι να τα επισκεφθεί όλα και να επιστρέψει στο αρχικό σημείο για να ολοκληρώσει τον κύκλο.
❓Πρόκληση:
Μπορείτε να τοποθετήσετε έξι σημεία μέσα στο μοναδιαίο τετράγωνο [0,1]×[0,1] έτσι ώστε ο άπληστος κύκλος (ξεκινώντας από ένα από αυτά τα σημεία) να έχει συνολικό μήκος τουλάχιστον 5,25;
Μπορείτε να το δείτε ως μια αναζήτηση των “πιο κακοτοποθετημένων” έξι σημείων, ώστε το greedy TSP μονοπάτι να γίνει όσο το δυνατόν μακρύτερο.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου