Αλγόριθμος Χριστοφίδη

Ο αλγόριθμος Χριστοφίδη είναι ένας αλγόριθμος για την εύρεση λύσεων κατά προσέγγιση στο πρόβλημα πλανόδιου πωλητή, στις περιπτώσεις όπου οι αποστάσεις σχηματίζουν ένα μετρικό χώρο (είναι συμμετρικές και ακολουθούν την τριγωνική ανισότητα).
Είναι ένας αλγόριθμος προσέγγισης που εγγυάται ότι οι λύσεις θα είναι εντός συντελεστή 3/2 του μήκου βέλτιστης λύσης, και είναι ονομάστηκε από τον Νίκο Χριστοφίδη, που τον δημοσίευσε το 1976. Από το 2017, αυτός είναι ο καλύτερος ρυθμός προσέγγισης που έχει αποδειχθεί για το πρόβλημα του περιπλανώμενου πωλητή, σε γενικούς μετρικούς χώρους, αν και καλύτερες προσεγγίσεις είναι γνωστές για κάποιες ειδικές περιπτώσεις.

Αναφορές 

Αλγόριθμοι γράφων