Sobre lo que hace el programa cabe comentar que trata de dar solución al problema del agente viajero usando el algoritmo del vecino más cercano donde voy visitando la ciudad más cercana a la que estoy actualmente y eliminando las ciudades ya visitadas hasta llegar a la ciudad de origen.
Agradecería mucho sus opiniones y consejos.
Código
/***************************************************************************** * Programa que busca la ruta mas corta entre 5 y 20 ciudades dadas por el * usuario. * * Hecho por: Joel Gonzalez * Fecha de elaboracion: 20 / 05 / 2014 * * Modificaciones: - [23 / 05 / 2014] * Uso de estructuras para reducir el numero de argumentos * a pasar en las funciones PedirCaminos, BuscarRutaOptima * y BuscarEnFila (recomendado por eferion). * * - [25 / 05 / 2014] * Cambio en la implementacion de la funcion PedirCaminos * (recomendada por eferion). * * - [25 / 05 / 2014] * Uso de las directivas de preprocesador #ifdef, #else y #endif * para hacer compatible a la funcion system("cls") de Windows * con Linux y Unix por medio de la funcion system("clear") * * - [25/ 05 / 2014] * Uso de la cabecera stdbool.h para ocupar los valores booleanos * true y false en vez de usar definiciones de preprocesador * (#define) para crearlas * *****************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #ifdef _WIN32 #define LIMPIAR_PANTALLA system("cls"); #else #define LIMPIAR_PANTALLA system("clear"); #endif /*Definiciones de estructuras*/ typedef struct { int G[20][20]; int num_ciudades; } Datos; /*Prototipos de funciones hechas por mi*/ int RutaOptima (void); void PedirCaminos (Datos *); void BuscarRutaOptima (Datos *,int [20][2]); int BuscarEnFila (Datos *,int, int[20][2]); void GuardarCiudad (int [20][2], int); void GuardarValor (int [20][2], int); void QuitarCiudadesVisitadas (Datos *, int [20][2], int, bool); void ImprimirRutaOptima (int [20][2], int); int SumarTrayectorias (int [20][2], int); void RepetirPrograma (void); void Flush_in (void); /*se explica su uso al final del codigo*/ /*Funcion principal*/ int main() { RutaOptima(); return 0; } /*Funciones hechas por mi*/ int RutaOptima(void) { int ruta[20][2]= {0}; Datos datos = {0,0}; do { LIMPIAR_PANTALLA Flush_in(); if (datos.num_ciudades < 5 || datos.num_ciudades > 20) { } } while (datos.num_ciudades < 5 || datos.num_ciudades > 20); PedirCaminos(&datos); BuscarRutaOptima(&datos, ruta); ImprimirRutaOptima(ruta, datos.num_ciudades); RepetirPrograma(); return 0; } void PedirCaminos(Datos *datos) { int i, j; LIMPIAR_PANTALLA printf("\n\n\tA continuacion escriba la distancia en kilometros de las siguientes\n\ttrayectorias:\n\n"); for (i = 0; i < (datos -> num_ciudades); i++) { datos -> G[i][i] = 0; for (j = i + 1; j < (datos -> num_ciudades); j++) { Flush_in(); datos -> G[j][i] = datos -> G[i][j]; } } } void BuscarRutaOptima(Datos *datos, int r[20][2]) { int i, inicio, indice_del_menor; do { LIMPIAR_PANTALLA Flush_in(); if (inicio < 1 || inicio > (datos -> num_ciudades)) { } }while(inicio < 1 || inicio > (datos -> num_ciudades)); r[0][0] = inicio; inicio--; for (i = 0; i < (datos -> num_ciudades); i++) { if(i == 0) { indice_del_menor = BuscarEnFila(datos, inicio, r); QuitarCiudadesVisitadas(datos, r, indice_del_menor, false); } else { if (i == (datos -> num_ciudades) - 2) { indice_del_menor = BuscarEnFila(datos, indice_del_menor, r); QuitarCiudadesVisitadas(datos, r, indice_del_menor, true); } else { indice_del_menor = BuscarEnFila(datos, indice_del_menor, r); QuitarCiudadesVisitadas(datos, r, indice_del_menor, false); } } } } int BuscarEnFila(Datos *datos, int inicio, int r[20][2]) { int j, menor = 999999, indice_del_menor; for (j = 0; j < (datos -> num_ciudades); j++) { if ( (datos -> G[inicio][j]) != 0 ) { if ( (datos -> G[inicio][j]) < menor ) { menor = datos -> G[inicio][j]; indice_del_menor = j; } } } GuardarCiudad(r ,indice_del_menor); GuardarValor(r, menor); return indice_del_menor; } void GuardarCiudad(int r[20][2] , int indice_del_menor) { int i, num_ciudades_visitadas; i= 0; num_ciudades_visitadas = 0; while(r[i][0] != 0) { i++; num_ciudades_visitadas++; } r[num_ciudades_visitadas][0] = indice_del_menor + 1; } void GuardarValor(int r[20][2], int menor) { int i, num_ciudades_visitadas; i=0; num_ciudades_visitadas = 0; while(r[i][1] != 0) { i++; num_ciudades_visitadas ++; } r[num_ciudades_visitadas][1] = menor; } void QuitarCiudadesVisitadas(Datos *datos, int r[20][2], int indice_del_menor, bool penultimo) { int i, num_ciudades_visitadas, aux; i = 0; num_ciudades_visitadas = 0; while(r[i][1] != 0) { i++; num_ciudades_visitadas++; } if (penultimo == true) { for (i = num_ciudades_visitadas; i >= 1; i--) { aux = r[i][0]; aux = aux - 1; datos -> G[indice_del_menor][aux] = 0; } } else { for (i = num_ciudades_visitadas; i >= 0; i--) { aux = r[i][0]; aux = aux - 1; datos -> G[indice_del_menor][aux] = 0; } } } void ImprimirRutaOptima(int ruta[20][2], int n) { int i, total; total = SumarTrayectorias(ruta, n); for (i = 0; i < n + 1; i++) { if (i == n) else } for (i = 0; i < n; i++) { if (i == n-1) else } } int SumarTrayectorias(int r[20][2], int n) { int i, total=0; for (i = 0; i < n; i++) total += r[i][1]; return total; } void RepetirPrograma(void){ int opcion; do { LIMPIAR_PANTALLA Flush_in(); switch(opcion) { case 1: RutaOptima(); break; case 2: LIMPIAR_PANTALLA break; default: break; } } while (opcion < 1 || opcion > 2); } /* La funcion Flush_in sustituye a la funcion fflush(stdin) ya que aquella * no funciona correctamente en linux y lo que hace es limpiar el buffer * del teclado. La funcion Flush_in la uso especificamente para limpiar la * basura que contiene el buffer del teclado al usar la funciones como scanf */ void Flush_in (void) { char caracter; }