Trimestre 2011 Otoño
Entrega: 5 de diciembre de 2011 a las 22:00.
Esta examen 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 A1, A2, ..., AN de modo que M
es el costo del camino A1-A2-...-AN-A1.
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.