Αλγόριθμος Χριστοφίδη
Ο αλγόριθμος Χριστοφίδη είναι ένας αλγόριθμος για την εύρεση λύσεων κατά προσέγγιση στο πρόβλημα πλανόδιου πωλητή, στις περιπτώσεις όπου οι αποστάσεις σχηματίζουν ένα μετρικό χώρο (είναι συμμετρικές και ακολουθούν την τριγωνική ανισότητα).[1] Είναι ένας αλγόριθμος προσέγγισης που εγγυάται ότι οι λύσεις θα είναι εντός συντελεστή 3/2 του μήκου βέλτιστης λύσης, και είναι ονομάστηκε από τον Νίκο Χριστοφίδη, που τον δημοσίευσε το 1976.[2] Από το 2017, αυτός είναι ο καλύτερος ρυθμός προσέγγισης που έχει αποδειχθεί για το πρόβλημα του περιπλανώμενου πωλητή, σε γενικούς μετρικούς χώρους, αν και καλύτερες προσεγγίσεις είναι γνωστές για κάποιες ειδικές περιπτώσεις.
Αναφορές[Επεξεργασία | επεξεργασία κώδικα]
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), «18.1.2 The Christofides Approximation Algorithm», Algorithm Design and Applications, Wiley, σελ. 513–514.
- ↑ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.