Hamilton y el viajante

Por Clara Grima, el 20 marzo, 2013. Categoría(s): Tareas ✎ 3

—Nos paramos a tomar algo, ¿chicos? —preguntó Mati a los chicos.

—Huy, pues sí —dijo el gafotas —. Estoy un poco cansado.

—Yo quiero un zumo de naranja, sí —añadió el pequeño Ven.

—¡Guauuuu!

Nuestros amigos salieron de paseo para ver su nuevo libro en las librerías. Para optimizar el recorrido, Mati les ha enseñado a diseñar el árbol de recorridos mínimos que conecta su casa con cada una de las librerías que querían visitar. Ahora necesitan un rato de descanso…

 

Mati20Min_46p

 

 

—Mati —dijo de pronto Sal —, el árbol que nos has dibujado con el algoritmo de Dijkstra está muy bien,

dijkstra_final

 

pero para ir de la librería Richter a la librería Euler, tenemos que pasar de nuevo por nuestra casa, ¿no se puede diseñar un camino que desde casita vaya a todas las librerías sin tener que pasar otra vez por casa y que sea lo más corto posible? 

—¡Toma! —dijo el pequeño —De la librería Hilbert a la librería Celsius, también hay que volver a pasar por la librería Fahrenheit

—Es cierto —dijo Sal —, lo que necesitamos es un recorrido que empezando y terminando en casa, pase por todas las librerías, sin repetir ninguna, y que sea lo más corto posible. 

—Bueno, bueno, bueno —dijo Mati con car de sorprendida —, lo que acabas de plantear es un problema muy famoso conocido como el Problema del viajante

—Querrás decir del viajero… —interrumpió el gafotas.

—No, del viajante —continuó ella —. Un viajero es una persona que viaja o que relata un viaje. Un viajante, aunque puede ser también alguien que viaja, es un vendedor comercial que hace viajes para negociar sus ventas o sus compras.

—Ah, vale —asintió Sal.

—Pues bien —siguió ella —, en el Problema del viajante se plantea cómo diseñar un recorrido que empiece y termine en el mismo sitio, la oficina del viajante por ejemplo o su hotel en una determinada ciudad, y que pase por todos los puntos que necesita visitar sin repetir ninguno y con la menor longitud posible.

—¿Cómo se resuelve, Mati? —preguntó el pequeño Ven.

—Siento deciros —anunció Mati con voz de drama —que es un problema tremendamente complicado de resolver.

—¿Porque somos pequeños? —siguió indagando Ven.

—No, no —dijo ella —porque es un problema que a partir de, por ejemplo,  25 puntos, 25 puntos que visitar en el recorrido, no se puede resolver ni con el ordenador más potente del mundo.

—¡Tomaaaaaaaaaaaaaa! —se extrañó Ven.

—¿Por qué, Mati? —quiso saber Sal.

—Porque la cantidad de caminos posibles que habría que comparar —dijo ella —es inabordable incluso para una máquina. Es lo que se conoce como un problema NP-duro, pero de esos problemas os hablaré cuando seáis un poco mayores.

—¿Y qué hacen entonces? —preguntó el pequeño apenado.

—Existen estrategias para dar buenas aproximaciones al camino más corto en esas condiciones —respondió la pelirroja —, pero no existe ningún método para calcular el mejor. En cualquier caso, esas estrategias sí son un poco complicadas para vosotros.

—Mati —preguntó Sal saliendo de una ensoñación que lo había mantenido ausente unos segundos —, ¿y si no queremos que sea el más corto posible? Quiero decir, ¿se puede diseñar un recorrido que empiece y termine en nuestra casa y que pase por todas las librerías sin repetir ninguna?

—Vaya —bromeó ella —, esta tarde va de problemas difíciles.

Los niños se quedaron mirando a Mati extrañados, ella siempre sabe resolver cualquier cosa. Gauss bostezó.

—Sí, chicos —continuó —. Lo que Sal plantea ahora es encontrar en este  grafo

dijkstra_1

 

 

lo que se conoce como un circuito  hamiltoniano, en honor a Hamilton. 

—¡Toma! ¡Claro! —exclamó Ven —El de la Fórmula 1…

—¡Jajajajajajajajaja! —Mati no pudo reprimir la risa —No, este circuito no tiene nada que ver con Lewis Hamilton, sino con William Rowan Hamilton, al que seguro que nuestro amigo Fis conoce muy bien porque le gusta la mecánica cuántica.

—¿Qué es un circuito hamiltoniano, Mati? —preguntó Sal curioso.

—Un circuito o ciclo hamiltoniano en un grafo —dijo ella —es un camino formado por aristas   (los segmentos azules de nuestro grafo) adyacentes que empieza y termina en un vértice (punto rojo) y pasa por todos los demás vértices (los demás puntos rojos de nuestro grafo) sin repetir ninguno.

—¿Cómo se hace, Mati? —preguntó Sal —¿Por qué ‘dices que es un problema difícil?

—Pues porque el problema de saber si existe o no  un ciclo hamiltoniano en un grafo —dijo ella —es un problema que tampoco pueden resolver ni los ordenadores más potentes para grafos con más de, por ejemplo, 50 vértices. Este es un problema NP-completo.

—Pues vaya —dijo Ven con penita.

—Y en nuestro grafo, ¿podemos dibujar un ciclo hamiltoniano? —preguntó Sal.

—Bueno —dijo ella —, en este grafo seguro que vosotros podéis intentar encontrarlo, si existe, hay muy pocos vértices…

Los niños se pusieron a mirar el grafo, al cabo de unos minutos el pequeño Ven gritó:

—¡Toma, toma, toma! ¡Cómo mola! ¡Sí se puede dibujar un circuito de Hamilton! ¡Mira, Mati!

—No, Ven —interrumpió ella y añadió con un guiño —. No lo dibujes, vamos a dejar a nuestros amigos lectores que lo intenten. Nosotros tenemos que seguir nuestro paseo.

 

 



3 Comentarios

  1. ¿No se podría abordar por partes, tomando grupos alejados de puntos, como si fueran pequeñas galaxias, resolviendo localmente y luego buscar la mejor conexión entre las distintas galaxias?.

  2. Efectivamente, Manuel, una posible aproximación es resolver el problema parcialmente para lo que es conocido como «clusters» de puntos y tratar de agrupar las soluciones particulares. Pero se pueden dar ejemplos en los que ese método no siempre da la solución óptima. Una cosa que hay que aclarar es que el problema es complicado no porque no se sepa la solución sino porque existe una demostración matemática probando que el problema es complicado (pero entrar a definir qué es NP-duro puede que se salga de la temática de Mati).

  3. ¡Lo hice, al fin lo logré!.
    Me fui hacia abajo,
    en dos tiempos,
    y a Hilbert me desplacé;
    luego fueron F, C,
    F, V, G y E;
    oí un ladrido cercano,
    me giré, miré un momento,
    y con Gauss me encontré,
    que movía el rabo contento.

Deja un comentario

Por Clara Grima, publicado el 20 marzo, 2013
Categoría(s): Tareas