Practica #1: ACO (avance)

Practica #1
Parte 1

a) Generar instancias para el problema del viajero (programa)  

 

(b) Resolver una instancia por fuerza bruta 

• Introduccion

  En este ejercicio se resolverá una instancia del problema del viajero.

Resolverlo por fuerza bruta consiste en probar una a una todas o la mayor parte de las posibles respuestas y al final compararlas para ver cuál es la más adecuada tomando en cuenta todas las restricciones que el problema nos plantea.

El método de fuerza bruta no es el más indicado ya que suele tomar mucho tiempo, el tiempo que tardes en resolverlo depende de la cantidad de posibles respuestas que contenga el problema.

• Instrucciones:

En este ejemplo tomaremos el problema del viajero para resolverlo por el método ya mencionado. El problema del viajero consiste en encontrar el camino más corto (barato) que pase por todas las ciudades del mapa una vez y que termine en la ciudad donde comenzaste.

• Respuestas:

Para intentar llegar a la respuesta se analizaron los siguientes caminos posibles.

A,B,C,D 4+2+5=11
A,B,D,C 4+6+5=15
A,C,D,B 1+5+6=12 
A,C,B,D 1+2+6=9
A,D,C,B 2+5+2=9
A,D,B,C 3+6+2=11

B,A,C,D 4+1+5=10
B,A,D,C 4+3+5=12
B,D,C,A 6+5+1=12
B,D,A,C 6+2+1=8
B,C,A,D 2+1+3=6
B,C,D,A 3+5+3=11

C,A,B,D 1+4+6=11
C,A,D,B 1+3+6=10
C,B,D,A 2+6+3=11
C,B,A,D 2+4+3=9
C,D,A,B 5+3+4=12
C,D,B,A 5+6+4=15

D,A,B,C 3+4+2=9
D,A,C,B 3+1+2=6
D,B,A,C 6+4+1=11
D,B,C,A 6+2+1=9
D,C,A,B 5+1+4=10
D,C,B,A 5+2+4=11

Hay dos posibles respuestas, aún hay más caminos posibles pero se descartaron ya que a simple vista son más largos (caros).

Este método es más tardado y complejo según el tamaño de la instancia, y te deja mucho marguen de error.

(c) Generar pseudocódigo o diagrama de flujo para ACO 

• Diagrama de flujo

 

• Pseudocodigo

1. Inicio 
2. Inicio de parámetros
3. if (condición del Fin)
4. Búsqueda de soluciones
5. búsqueda local
6. actualización de una feromona
7. else (fin)