Held-Karp

propuesto por josejuan

Implementar el algoritmo de Held-Karp para TSP simétrico.

Enunciado
Por ejemplo para las siguientes coordenadas del grafo total con las distancias como costes.

20833.3333, 17100.0000
20900.0000, 17066.6667
21300.0000, 13016.6667
21600.0000, 14150.0000
21600.0000, 14966.6667
21600.0000, 16500.0000
22183.3333, 13133.3333
22583.3333, 14300.0000
22683.3333, 12716.6667
23616.6667, 15866.6667
23700.0000, 15933.3333
23883.3333, 14533.3333
24166.6667, 13250.0000
25149.1667, 12365.8333
26133.3333, 14500.0000
26150.0000, 10550.0000
26283.3333, 12766.6667
26433.3333, 13433.3333
26550.0000, 13850.0000
26733.3333, 11683.3333
27026.1111, 13051.9444
27096.1111, 13415.8333
27153.6111, 13203.3333
27166.6667,  9833.3333
27233.3333, 10450.0000

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

2 Soluciones

Dar mi solución

0votos
Held-Karp en C
por

josejuan

hace 5 años

Si sólo queremos el coste final, se puede reducir la memoria a O(n!/((n/2)!)^2) que es mucho menos que O(2^n) (aprox. un factor de 1/ln x). Aun se podría analizar el nº de MAXCOST que aparecen en un grafo total, xq no hace falta almacenarlos.

Dar mi solución