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 · Português
O algoritmo de Christofides é um algoritmo para encontrar soluções aproximadas para o problema do caixeiro-viajante, nos casos em que as distâncias formam um espaço métrico (são simétricas e obedecem a desigualdade triangular).É um algoritmo de aproximação que garante que suas soluções estão a um fator máximo de 3/2 do tamanho da solução ótima. Seu nome vem do autor Nicos Christofides, que publicou o algoritmo em 1976. Até 2017 esta é a melhor razão de proximação já comprovada para o problema do caixeiro viajante em espaços métricos, embora aproximações melhores sejam conhecidas para alguns casos especiais.
Abstract from DBpedia / Wikipedia · CC BY-SA