In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation es un libro sobre el problema del viajante , de William J. Cook , publicado en 2012 por Princeton University Press , con una reimpresión en rústica en 2014. [1] The Basic Library El Comité de listas de la Asociación de Matemáticas de América ha sugerido su inclusión en las bibliotecas de matemáticas de pregrado. [2]
Temas
El problema del viajante pide encontrar el recorrido cíclico más corto de una colección de puntos, en el plano o en espacios matemáticos más abstractos. Debido a que el problema es NP-difícil , es poco probable que se garantice que los algoritmos que toman tiempo polinomial encuentren su solución óptima; [3] por otro lado, una búsqueda de fuerza bruta de todas las permutaciones siempre resolvería el problema exactamente, pero tomaría demasiado tiempo para ser utilizable para todos los problemas excepto los más pequeños. [4] Colocar un término medio entre estos tiempos de ejecución demasiado rápidos y demasiado lentos, y desarrollar un sistema práctico que pueda encontrar la solución exacta de instancias más grandes, plantea cuestiones difíciles de ingeniería de algoritmos , [5] [3] que han provocado el desarrollo de "muchos de los conceptos y técnicas de optimización combinatoria". [3]
El capítulo introductorio del libro explora los límites del cálculo del problema, desde problemas de 49 puntos resueltos a mano a mediados de la década de 1950 por George Dantzig , DR Fulkerson y Selmer M. Johnson hasta un problema con 85,900 puntos resueltos de manera óptima en 2006. por el Concorde TSP Solver , que Cook ayudó a desarrollar. Los próximos capítulos cubre la historia temprana del problema y de los problemas relacionados, incluyendo Leonhard Euler 's de trabajo en los siete puentes de Königsberg , William Rowan Hamilton ' s juego icosian , [6] y Julia Robinson primera nombrar el problema en 1949. [ 7] En otro capítulo se describen las aplicaciones del problema en el mundo real, [6] que van "desde la secuenciación del genoma y el diseño de procesadores informáticos hasta la organización de la música y la búsqueda de planetas". [8] El crítico Brian Hayes cita "la revelación más encantadora" del libro como el hecho de que una de esas aplicaciones del mundo real ha sido la planificación de rutas para los vendedores ambulantes reales a principios del siglo XX. [4]
Los capítulos cuatro al siete, "núcleo del libro", discuten los métodos para resolver el problema, que van desde la heurística y metaheurística , la relajación de programación lineal y los métodos de plano de corte , hasta el método de bifurcación y enlace que combina estas técnicas y es utilizado por Concorde. Los dos capítulos siguientes también cubren material técnico, sobre el desempeño de las implementaciones informáticas y sobre la teoría de la complejidad computacional del problema. [6] [9]
Los capítulos restantes están más centrados en el ser humano, cubriendo estrategias de resolución de problemas humanos y animales, y la incorporación de soluciones TSP en las obras de arte de Julian Lethbridge , Robert Bosch y otros. [6] [10] Un breve capítulo de resumen final sugiere posibles direcciones futuras, incluida la posibilidad de progreso en el problema P versus NP . [6] [11]
Audiencia
El libro está destinado a un público no especializado, evita los detalles técnicos [3] [5] [12] y está escrito "en un estilo fácil de entender". [13] Incluye muchos apartados históricos, ejemplos, aplicaciones e información biográfica y fotografías de actores clave en la historia, haciéndola accesible a lectores sin conocimientos matemáticos. [10] [12]
Aunque In Pursuit of the Travelling Salesman no es un libro de texto, el revisor Christopher Thompson sugiere que parte de su material sobre el uso de la programación lineal y las aplicaciones del problema "sería adecuado para el uso en el aula", citando en particular la forma en que vincula varios campos, incluido el análisis numérico , la teoría de grafos , el diseño de algoritmos , la lógica y la estadística . [14]
El crítico Stan Wagon escribe que "cualquier lector interesado en los algoritmos combinatorios encontrará mucho valor en este libro". [5] Jan Karel Lenstra y David Shmoys escriben que "La escritura es relajada y entretenida; la presentación es excelente. Disfrutamos mucho leyéndola". [3] Y el crítico Haris Aziz concluye: "El libro se recomienda encarecidamente a cualquier persona con curiosidad matemática e interés en el desarrollo de ideas". [10]
Obras relacionadas
Se pueden encontrar más detalles del trabajo de Cook con Concorde, adecuado para investigadores más serios sobre el problema y temas relacionados, en un libro anterior de Cook con David Applegate , Robert E. Bixby y Václav Chvátal , The Travelling Salesman Problem: A Computational Study (2007). [2] [4] [10] Otros libros sobre el problema del vendedor ambulante, también más técnicos que En busca del vendedor ambulante , incluyen El problema del vendedor ambulante: una visita guiada de optimización combinatoria (por Lawler, Lenstra, Rinnooy Kan y Shmoys, 1985) y El problema del viajante y sus variaciones (por Gutin y Punnen, 2006). [10]
Referencias
- ^ Zbl 1301.00021
- ^ a b Gittleman, Art (febrero de 2012), "Review of In Pursuit of the Travelling Salesman " , MAA Reviews , Asociación Matemática de América
- ^ a b c d e Lenstra, Jan Karel ; Shmoys, David (2016), "Review of In Pursuit of the Travelling Salesman ", Notices of the American Mathematical Society , 63 (6): 635–638, doi : 10.1090 / noti1397 , MR 3495222
- ^ a b c Hayes, Brian (mayo-junio de 2012), "Viajes matemáticos por carretera (revisión de In Pursuit of the Travelling Salesman )", American Scientist , 100 (3): 252–254, JSTOR 23223051
- ^ a b c Wagon, Stan (2012), "Review of In Pursuit of the Travelling Salesman ", American Mathematical Monthly , 119 (9): 808–811, doi : 10.4169 / amer.math.monthly.119.09.808 , JSTOR 10.4169 / amer. matemáticas.119.09.808 , MR 3013985
- ^ a b c d e Werner, Frank (2012), "Revisión de En busca del vendedor ambulante ", Revisiones matemáticas , MR 2866515
- ^ Schuessler, Jennifer (15 de marzo de 2012), "Willy Loman, ¿Dónde estás? (Revisión de En busca del vendedor ambulante )" , The New York Times
- ^ Benker, Hans, "Revisión de En busca del vendedor ambulante ", zbMATH , Zbl 1236.00007
- ^ Baldacci, Roberto (julio-agosto de 2013), "Review of In Pursuit of the Travelling Salesman ", Interfaces , 43 (4): 391, JSTOR 23481217
- ^ a b c d e Aziz, Haris (agosto de 2012), "Review of In Pursuit of the Travelling Salesman ", ACM SIGACT News , 43 (3): 51, doi : 10.1145 / 2421096.2421108
- ^ McGonigal, Francis (enero de 2012), "Review of In Pursuit of the Travelling Salesman " , Reseñas de libros de IMA , Instituto de Matemáticas y sus Aplicaciones
- ^ a b Tirado Domínguez, Gregorio (noviembre de 2012), "Review of In Pursuit of the Travelling Salesman " , EMS Reviews , European Mathematical Society
- ^ Schaefer, Robert (enero de 2012), "Review of In Pursuit of the Travelling Salesman " , New York Journal of Books
- ^ Thompson, Christopher (febrero de 2012), "Review of In Pursuit of the Travelling Salesman ", Convergence , Asociación Matemática de América , doi : 10.4169 / loci003821
Otras lecturas
- Ellenberg, Jordan (10 de marzo de 2012), "El camino difuso puede ser más corto (revisión de En busca del vendedor ambulante )" , The Wall Street Journal
- McLemee, Scott (21 de marzo de 2012), "Algoritmo de un vendedor (revisión de En busca del vendedor ambulante )" , Inside Higher Education