Solucionando el clásico problema del vendedor viajero paralelizando usando paso de mensajes

Resumen

Se resuelve el problema del vendedor viajero, en su versión asimétrica (Asymmetric TSP) mediante la técnica de paso de mensajes asíncronos, la cual, junto con el paso de mensajes sincrónicos, llamadas a procedimientos remotos (RPC) y rendezvous son los cuatro mecanismos básicos para comunicación y sincronización de programas distribuidos.

El problema se paralelizó no mediante programas distribuidos, sino que mediante hilos de una misma aplicación Java, para lo cual tuvimos que simular el paso de mensajes asíncronos entre ellos.

Problema

Se trata del problema del vendedor viajero en su versión asimétrica, cuya mayor diferencia respecto del problema del vendedor viajero clásico es que las distancias de ida y de vuelta entre ciudades pueden tener valores distintos.

Pueden echar un vistazo a los detalles del problema y cómo tendremos que solucionarlo aquí.

Generando una solución 

En resumidas cuentas, la clave de la solución fue la creación de la clase de objetos Canal que implementa la funcionalidad esperada de un canal, en particular los métodos send y receive dispuestos de manera de contar con paso de mensajes asíncronos.

Con lo anterior, el hilo principal de la aplicación echa a correr a 1 hilo administrador más cierta cantidad de hilos trabajadores (cantidad que en nuestro caso definimos como igual a la cantidad de ciudades del problema), que resuelven el problema comunicándose y sincronizándose por medio del envío y recepción de mensajes (algunos de ellos nulos) a través de un par de canales.

Finalmente el hilo administrador manda mensajes nulos que terminan con la vida de los hilos trabajadores, muere a su vez el hilo administrador, y recién entonces el hilo principal exhibe la solución al problema concreto.

Mayores detalles se hallan en la bitácora.

Solución 

La solución al problema es una aplicación en Java 6: pueden consultar el código y probarlo por Uds. mismos; además está el manual de usuario de la aplicación.

Evaluando la solución

La mejor manera de evaluar la solución presentada es comparándola con la solución generada por otros alumnos, que debía resolver este mismo problema.

Debido a que cumplía su propósito de manera estable, fue una de las mejores: