Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 133 vistas

    Viajero - Ieee Fuerza Bruta

    Cargado por

    Frank Cornejo
    Este documento presenta el código de un algoritmo de fuerza bruta para resolver el problema del agente viajero utilizando permutaciones. Genera pares ordenados (x,y) aleatorios que representan ciudades, y calcula todas las rutas posibles visitando cada ciudad una vez mediante next_permutation. Devuelve la ruta óptima con la distancia total mínima.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd

    Viajero - Ieee Fuerza Bruta

    Cargado por

    Frank Cornejo
    133 vistas2 páginas
    Este documento presenta el código de un algoritmo de fuerza bruta para resolver el problema del agente viajero utilizando permutaciones. Genera pares ordenados (x,y) aleatorios que representan ciudades, y calcula todas las rutas posibles visitando cada ciudad una vez mediante next_permutation. Devuelve la ruta óptima con la distancia total mínima.

    Título original

    Viajero_ieee Fuerza Bruta

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    DOC, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta el código de un algoritmo de fuerza bruta para resolver el problema del agente viajero utilizando permutaciones. Genera pares ordenados (x,y) aleatorios que representan ciudades, y calcula todas las rutas posibles visitando cada ciudad una vez mediante next_permutation. Devuelve la ruta óptima con la distancia total mínima.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    133 vistas2 páginas

    Viajero - Ieee Fuerza Bruta

    Cargado por

    Frank Cornejo
    Este documento presenta el código de un algoritmo de fuerza bruta para resolver el problema del agente viajero utilizando permutaciones. Genera pares ordenados (x,y) aleatorios que representan ciudades, y calcula todas las rutas posibles visitando cada ciudad una vez mediante next_permutation. Devuelve la ruta óptima con la distancia total mínima.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    de 2

    PROGRAMACION LOGICA Y FUNCIONAL, INGENIERIA DE SISTEMAS, UNIVERSIDAD NACIONAL DE SAN AGUSTIN

    Algoritmos de Fuerza Buta y el Problema del Agente Viajero


    CODIGO DEL ALGORITMO.
    #include <stdio.h> #include <stdlib.h> #include <time.h> #include <iostream> #include <algorithm> #include <math.h> using namespace std; void tsp(int Nnodes, int* x, int* y, char* nodes) {//paso por referencia unsigned long long tmpcost, cheapest_cost;//declaracion de variables del tipo long long positivos (unsigned) char tmp[Nnodes]; char cheap_path[Nnodes]; int i; //PERMUTACIONES do { //*//cout<<"el valor de cheapest : "<<cheapest_cost<<endl; //*//cheapest_cost variable del tipo log grandeee tmpcost = 0; cout<<endl; cout << "permutacion :"; for(i=0; i<Nnodes; i++) {cout <<(int)nodes[i] <<" ";} cout<<endl; for(i=0; i<Nnodes; i++) { tmp[i] = nodes[i];//nodes[i] es la permutacion del vector posicion //printf(" %d ", nodes[i]); if(i!=0) { //*//cout<<"cual es el valor de i : "<<i<<endl; //el costo es igual a la diferencia entre los dos puntos en la cuadrcula cartesiana tmpcost += sqrt( ( pow( x[(int)nodes[i]] - x[(int)nodes[i-1]], 2) ) + ( pow( y[(int)nodes[i]] - y[(int)nodes[i-1]] ,2) ) ); } } cout<<"La suma de las distancias es :"<<tmpcost<<endl; //----------------------------------------------------if( cheapest_cost!=0 && cheapest_cost > tmpcost ) {//si la distancia calcula es menor que la que se obbtuvo enteriormente entra al if cheapest_cost = tmpcost;//guarda el valor de la menor distancia //se almacena la mejor distancia encontrada en cada iteracion for (i=0; i<Nnodes; i++) { cheap_path[i] = tmp[i];//se almacena la permutacion (camino) de la menor distancia calculada } } printf(" --> cost = %u", tmpcost); printf("\n"); //permutaciones de los numeros } while(next_permutation(nodes,nodes+Nnodes)); // Para calcular todas las rutas posibles se encuentran todas //las permutaciones mediante el uso de next_permutation funcin de la libreria <algorithm> //Devuelve true si una permutacin se efectu, false si no. //Imprimir los resultados cout<<"------------------------------------------"<<endl; printf("RESULTADOS \nEl mejor camino es : "); for (i=0; i<Nnodes; i++) { printf("%i ", cheap_path[i]); } printf("\n SU COSTO ES : %d\n Fin!!!!!!!", (int)cheapest_cost); } int main() { cout<<"----------Inteligencia Artificial----------"<<endl; cout<<"---------------Agente Viajero--------------"<<endl; cout<<"----------------Fuerza Bruta---------------"<<endl; cout<<endl; int Nnodes; //numeros de nodos o ciudades cout<<"Introdusca el numero de Nodos : "; cin>>Nnodes; cout<<endl; int x [Nnodes]; int y [Nnodes]; char nodes [Nnodes]; //valores de x e y al azar int i; srand(time(NULL)); cout<<"Los pares ordenados (x,y) aleatorios son :"<<endl; cout<<"------------------------------------------"<<endl; for(i=0; i<Nnodes; i++) { nodes[i] = i; x[i] = rand()%10+1; cout<<"("<<x[i]<<", "; y[i] = rand()%10+1; cout<<y[i]<<") , "; } cout<<endl; cout <<"El vector X es : [ "; for(i=0; i<Nnodes; i++) {cout <<(int)x[i] <<" ";}

    PROGRAMACION LOGICA Y FUNCIONAL, INGENIERIA DE SISTEMAS, UNIVERSIDAD NACIONAL DE SAN AGUSTIN

    cout<<"]"<<endl; cout <<"El vector Y es : [ "; for(i=0; i<Nnodes; i++) {cout <<(int)y[i] <<" ";} cout<<"]"<<endl; cout <<"El vector de posiciones es : [ "; for(i=0; i<Nnodes; i++) {cout <<(int)nodes[i] <<" ";} cout<<"]"<<endl; cout<<"------------------------------------------"<<endl; tsp(Nnodes,x,y,nodes); return 0; }

    También podría gustarte