Modificación en el algoritmo de Held & Karp

  1. Pacheco Bonrostro, Joaquín A.
Revista:
Cuadernos de estudios empresariales

ISSN: 1131-6985

Año de publicación: 1996

Número: 6

Páginas: 267-282

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Cuadernos de estudios empresariales

Resumen

El trabajo describe un conjunto de variaciones en el algoritmo de held & karp para el tsp simétrico. Este es uno de los problemas mas estudiado de la matemática combinatoria en las ultimas décadas. La obtención de la solución optima para este problema requiere un tiempo de computación habitualmente excesivo, sobre todo si el numero de ciudades es alto. Con estas variaciones se consigue reducir enormemente el tiempo de computación en el algoritmo de held & karp original. De esta forma se obtiene un procedimiento que alcanza la solución exacta, para problemas de 100 nodos en ordenadores personales, en un tiempo razonable.

Fuente de los datos: Dialnet