Algoritmo de Christofides
Sign in to savealgorithm that approximates solutions to the travellng salesman problem on a metric space, guaranteeing that its solutions will be within 1½ of the optimal solution length; discovered by Nicos Christofides in 1976
Wikidata facts
- Instance of
- algorithm
Show 1 more fact
- facet of
- travelling salesperson problem
Sources (2)
via Wikidata · CC0
Article · Español
El algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por su acrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular. Fue desarrollado en 1976 por Nicos Christofides, profesor del Imperial College London. Supongamos que representa una instancia del TSP, en donde es un grafo completo definido por: un conjunto de vértices o nodos y una función que asocia un peso o valor real positivo a cada arista del grafo .
Abstract from DBpedia / Wikipedia · CC BY-SA