UEA: Diseño de Algoritmos
Trimestre: 2007 Invierno
Entrega: 23 de marzo de 2007 a las 10pm

Esta tarea consiste en programar dos heurísticas para una variante del problema del agente viajero: Sea G = (V, E) una gráfica donde cada arista e une a dos vértices u y v y tiene un costo positivo c. Se desea encontrar un camino cerrado que pase por todos los vértices de G y que tenga costo tan económico como sea posible. En este caso se permite pasar tantas veces como se desee por cualquier vértice o arista. El costo de un camino cerrado es la suma de los costos de las aristas por las que se pase (considerando el número de veces que se pase por cada arista). Por ejemplo, si la gráfica G tiene 4 vértices (u, v, x, z) y 5 aristas (uv, vx, xz, zv, zu) con costos (3, 1, 4, 1, 5) respectivamente, entonces dos posibles soluciones son u-v-x-z-u con costo 3+1+4+5 = 13 y u-v-x-v-z-v-u con costo 3+1+1+1+1+3 = 10. Para los dos programas de abajo, la entrada será un número entero V (el número de vértices) seguido de un número entero E (el número de aristas) seguido de E renglones, cada uno con tres números enteros positivos A, B, C con 1 <= A <= V, 1 <= B <= V, A y B distintos, que representan una arista del vértice A al vértice B con costo C. La salida será un número entero N seguido de un entero M seguido de un renglón con N enteros A₁, A₂, ..., A_N de modo que M es el costo del camino A₁-A₂-...-A_N-A₁. Puede suponer que 2 <= V <= 100 y que siempre habrá solución. Para nuestro ejemplo, una entrada y dos salidas posibles aparecen en la siguiente tabla:

Entrada	Algunas salidas posibles
4 5 1 2 3 2 3 1 3 4 4 4 2 1 4 1 5	4 13 1 2 3 4 6 10 1 2 3 2 4 2

Problema 1: Escriba un programa llamado cercano basado en la siguiente heurística: Comience el camino en el vértice 1 y a cada paso vaya al vértice más cercano al que se encuentre y que no haya sido visitado todavía. Al final regrese al vértice 1. En cada uno de estos pasos debe usar el camino más corto posible. En caso de haber empates, escoja de forma arbitraria. Observe que todos los vértices por los que vaya pasando ya han sido visitados. En nuestro ejemplo el camino comenzaría en 1, seguiría al 2, después podría ir al 3 o al 4 (digamos al 4), después tendría que ir al 3 y de allí regresar al 1 pasando por el 2, de modo que el camino sería 1-2-4-3-2-1 y la salida sería 5 12 seguida de 1 2 4 3 2.

Problema 2: Escriba un programa llamado lejano basado en la siguiente heurística: Comience el camino en el vértice 1 y a cada paso vaya al vértice más lejano al que se encuentre y que no haya sido visitado todavía. Al final regrese al vértice 1. En cada uno de estos pasos debe usar el camino más corto posible. En caso de haber empates, escoja de forma arbitraria. Observe que todos los vértices por los que vaya pasando ya han sido visitados. En nuestro ejemplo el camino comenzaría en 1, después podría seguir al 3 o al 4 (digamos al 3) pasando por el 2, después tendría que ir al 4 pasando por el 2 y de allí regresar al 1 pasando por el 2, de modo que el camino sería 1-2-3-2-4-2-1.