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

Esta tarea consiste en programar otras dos heurísticas para la variante del problema del agente viajero descrita en la Tarea 5.

Problema 1: Escriba un programa llamado elige basado en la siguiente heurística: Comience el camino en el vértice 1. A cada paso elija de forma aleatoria alguno de los vértices que no haya visitado todavía y vaya a él. La probabilidad de escoger un vértice deberá ser inversamente proporcional a su distancia al vértice actual. 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.

Problema 2: Escriba un programa llamado arbol basado en la siguiente heurística: Encuentre un árbol abarcador de costo mínimo de la gráfica. Haga un recorrido en profundidad del árbol obtenido comenzando en el vértice 1, sustituyendo cada arista vista por el camino más corto posible que una a sus extremos. En caso de haber empates, escoja de forma arbitraria. En nuestro ejemplo el árbol abarcador de costo mínimo consistiría de las aristas 12, 23 y 24. Un recorrido en profundidad de este árbol comienza en el vértice 1, sigue al 2, de allí podría ir al 3 o al 4 (digamos al 3), de allí iría al 2, de allí iría al 4, de allí iría al 2 y de allí regresaría al 1, de modo que el camino encontrado sería 1-2-3-2-4-2-1.