Equipo Practica 1 | Parte 1

1.  Generar instancias para el problema del viajero

Un vendedor tiene que recorrer 4 ciudades lejanas para entregar los paquetes que lleva consigo a sus respectivos clientes. Debe encontrar la ruta más corta para no entorpecer la entrega y enfadar a sus clientes. Puede pasar por cualquier ciudad sólo una vez, pero debe regresar al punto de partida.

	Monterrey (M)	Guadalajara (G)	Torreón (T)	Pachuca (P)
Monterrey (M)	0	848	334	920
Guadalajara (G)	848	0	710	559
Torreón (T)	334	710	0	1013
Pachuca (P)	920	559	1013	0

Programa generador de instancias

#include<stdio.h>
#include<time.h>
int main(){
       int m[4][4],i,j;
       srand(clock());
       printf("Ciudades:   A     B     C     D\n");
       for(i=0;i<4;i++){
         for(j=0;j<4;j++){
    if(j!=i){
              m[i][j]=rand()%9999;
          }else{
           m[i][j]=0;
    }
           }
       }
       for(i=0;i<4;i++){
         printf("Ciudad %c",65+i);
         for(j=0;j<4;j++){
    m[j][i]=m[i][j];
             printf("%6d",m[i][j]);
           }
           printf("\n");
       }
       return 0;
}

Instancia Generada

   2.  Resolver la instancia por fuerza bruta.

Nuestro problema del viajero será resuelto por fuerza bruta. Deberán ser 24 rutas distintas, a continuación enlistamos los tamaños de cada recorrido:


1. MGTPM=3491
2. MGPTM=2754
3. MPGTM=2523 *
4. MPTGM=3491
5. MTPGM=2754
6. MTGPM=2523 *
7. GMTPG=2754
8. GMPTG=3491
9. GTMPG=2523 *
10. GTPMG=3491
11. GPTMG=2754
12. GPMTG=2523 *
13. TGMPT=3491
14. TGPMT=2523 *
15. TMPGT=2523 *
16. TMGPT=2754
17. TPMGT=3491
18. TPGMT=2754
19. PTGMP=3491
20. PTMGP=2754
21. PGTMP=2523 *
22. PGMTP=2754
23. PMGTP=3491
24. PMTGP=2523 *

Los caminos más cortos están marcados con un asteriso (*).

c) Pseudocódigo de ACO

1.-Inicio
Do
2.-Salida de hormigas
3.-Camino más optimo para el regreso 
3.-Busqueda de comida
4.-If se encontró comida
5.-Dejar rastro de  feromona
6.-Regresar al origen
7.-Recibir rastro de la feromona 
8.-Hormigas captan el mejor camino percibido por la feromona
9.-Se eliminan rastros anteriores de la feromona se capta el mas aptimo
10.-While se cumple con el objetivo 
11.-Fin 

Fuentes

http://mx.lasdistancias.com/