elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Viajante comercio		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Viajante comercio  (Leído 9,729 veces)
Dato Vagabundo

Desconectado Desconectado

Mensajes: 18



Ver Perfil
Viajante comercio
« en: 5 Septiembre 2016, 18:26 pm »
Lo esencial del problema. Segun la matriz que he introducido, deberia calcular el minimo de la primera fila, excluyendo siempre el cero, seleccionar el 0,2 que es el minimo y borrar las columnas de ambos numeros. Luego iria a la fila 2, buscaria el minimo que esta en el 2,3 y borraria de nuevo columnas. El problema es que a partir de ahi no avanza y entra en bucle cuando deberia seguir con 3,1 y acabar.


Código
  1. int matriz[n][n];
  2. int minimo;
  3. list <int> vertice;//Subconjunto solución
  4.  
  5. /*--------------------------------------------------*/
  6. // Rellenamos matriz a ceros
  7.  
  8. for(int i=0; i<n; i++){
  9.     for(int j=0; j<n; j++){
  10.               matriz[i][j] = 0;
  11.     }
  12. }
  13.  
  14. matriz[0][1]=5;
  15. matriz[0][2]=2;
  16. matriz[0][3]=3;
  17. matriz[1][0]=5;
  18. matriz[1][2]=4;
  19. matriz[1][3]=5;
  20. matriz[2][0]=2;
  21. matriz[2][1]=4;
  22. matriz[2][3]=1;
  23. matriz[3][0]=3;
  24. matriz[3][1]=5;
  25. matriz[3][2]=1;
  26.  
  27. bool aumento;
  28. int contador;
  29. int contador2;
  30. int val1,val2;
  31.  
  32. for(int i=0; i<n; i=val2){
  33.     aumento = true;
  34.     contador2 = 0;
  35.     for(int j=0; j<n; j++){
  36.  
  37.         if (aumento){
  38.             contador = 0;
  39.  
  40.             while (matriz[i][contador]==0){
  41.                 contador++;
  42.             }
  43.  
  44.             minimo = matriz[i][contador]; 
  45.             //cout << "\nMINIMO INICIAL EN FILA " << i << " : " << minimo << endl;
  46.             aumento = false;
  47.         }
  48.  
  49.         contador2++;
  50.         if(matriz[i][j]!=0){
  51.             if(matriz[i][j] < minimo){
  52.                 minimo = matriz[i][j]; 
  53.                 val1 = i;
  54.                 val2 = j;
  55.                 //cout << "MINIMO DE LA FILA " << i << ": " << minimo << endl;
  56.                 cout << "POSICION " << "("<<val1<<","<<val2<<")"<<endl;
  57.  
  58.             }
  59.         }
  60.         //cout << "CONTADOR2 : " << contador2 << endl;
  61.  
  62.         if (contador2 == n){
  63.  
  64.             vertice.push_back(val1);
  65.                 vertice.push_back(val2);
  66.  
  67.              for(int j=0; j<n; j++){
  68.  
  69.                           matriz[j][val1]=0;
  70.                           matriz[j][val2]=0; 
  71.             }
  72.  
  73.             // cout << "POSICION " << "("<<val1<<","<<val2<<")"<<endl;
  74.         }
  75.     }
  76. }

MOD EDIT: Etiquetas GeSHi.
« Última modificación: 6 Septiembre 2016, 12:53 pm por MCKSys Argentina » En línea
bengy


Desconectado Desconectado

Mensajes: 501


mis virtudes y defectos son inseparables


Ver Perfil WWW
Re: Viajante comercio
« Respuesta #1 en: 5 Septiembre 2016, 18:43 pm »
disculpa y tu pregunta?
En línea
usuario desde el 2011
https://www.youtube.com/channel/UCK478eq4-FJUjxnNaorjFBA
JonaLamper


Desconectado Desconectado

Mensajes: 394



Ver Perfil
Re: Viajante comercio
« Respuesta #2 en: 6 Septiembre 2016, 10:23 am »
Lo que ocurre es que el Viajante de comercio no se resuelve así. Es una buena idea (e incluso podría parecer óptima) el ir cogiendo los caminos mínimos desde un punto inicial hasta que vuelves otra vez al punto de partida, pero como he dicho, esa no es la forma de resolver el Viajante de comercio (te podría poner un ejemplo muy fácil donde tu algoritmo no es óptimo).

En el problema del viajante actualmente sólo puede resolverse de una forma: explorando todos los caminos posibles y quedándote con la ruta mínima. Lo cual supone un tiempo exponencial (que es muchísimo) y por eso el problema del viajante pertenece a la clase de complejidad NP.

Lo que tú estás intentando hacer se llama algoritmo de Dijkstra.


Posdata: no he visto el código, sólo he leído lo que has dicho. Por cierto, intenta usar las etiquetas de código porque no se entiende nada.
« Última modificación: 6 Septiembre 2016, 10:26 am por JonaLamper » En línea
Utilizar palabras para hablar de palabras es como utilizar un lápiz para hacer un dibujo de ese lápiz sobre el mismo lápiz.
Dato Vagabundo

Desconectado Desconectado

Mensajes: 18



Ver Perfil
Re: Viajante comercio
« Respuesta #3 en: 6 Septiembre 2016, 20:06 pm »
He encontrado este codigo por internet pero no se porque no me hace bien los caminos,
soy principiante no me juzgueis  ;D



Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define N 4					// Numero de ciudades
  5. #define CIUDAD_ORIGEN 0		
  6.  
  7.  
  8. #define TRUE (1 == 1)
  9. #define FALSE (1 != 1)
  10.  
  11. char ciudades[4] = {'0', '1', '2', '3'};
  12.  
  13. int d[4][4]={{0,20,40,60},
  14.    			{30,0,50,25},
  15.             {20,25,0,50,},
  16.             {20,30,0,0}};	// Matriz de distancias
  17. int visitadas[N];			// Ciudades visitadas por el algoritmo
  18. int suma = 0;				// Suma de costes
  19. int optima = 999999;		// Solucion optima inicial
  20. int iteraciones = 0;		// Numero de iteraciones
  21. int solucion[N];			// Vector con el trayecto realizado
  22.  
  23.  
  24.  
  25. void busqueda_profundidad (int nivel, int origen, int suma, int visitadas[]) {
  26. 	visitadas[origen] = TRUE;
  27. 	solucion[nivel - 1] = origen;
  28. 	iteraciones++; 
  29. 	for (int destino = 0; destino < N; destino++) {
  30. 		if (visitadas[destino] == FALSE) {			
  31. 			suma = suma + d[origen][destino];
  32. 			if (suma < optima) {				
  33. 				busqueda_profundidad(nivel + 1, destino, suma, visitadas);
  34. 			}
  35. 			if (nivel == (N - 1)) {							
  36. 				suma = suma + d[destino][CIUDAD_ORIGEN];
  37. 				if (suma < optima) {
  38. 					optima = suma;
  39. 					printf ("Estableciendo nueva solucion optima, coste = %6d\n", optima);
  40. 					printf ("Solucion = { ");
  41. 					for (int i = 0; i < N; i++) {
  42. 						printf (" %c, ", ciudades[ solucion[i] ]);
  43. 					}
  44. 					printf (" %c }\n\n", ciudades[CIUDAD_ORIGEN]);
  45. 				} 
  46. 			} else {
  47. 				suma = suma - d[origen][destino];
  48. 			}
  49. 			visitadas[destino] = FALSE;
  50. 		}
  51. 	}
  52. }
  53.  
  54. int factorial (int n) {
  55. 	int f = 1;
  56. 	for (int i = n; i > 1; i--) {
  57. 		f = f * i;
  58. 	}
  59. 	return f;
  60. }
  61.  
  62. int main (void) {	
  63. 	printf ("RESOLUCION DEL PROBLEMA DEL VIAJANTE DE COMERCIO\n");
  64. 	printf ("(c) Alejandro Portero Gimeno 2015\n\n");
  65.  
  66. 	//matriz_distancias();
  67.  
  68. 	for (int i = 0; i < N; i++) {
  69. 		visitadas[i] = FALSE;	
  70. 	}
  71.  
  72. 	printf ("\nNum. ciudades = %d\n\n", N);
  73.  
  74. 	busqueda_profundidad (1, CIUDAD_ORIGEN, suma, visitadas);
  75.  
  76. 	printf ("Iteraciones            = %12d\n", iteraciones);
  77. 	printf ("Soluciones totales     = %12d\n", factorial(N));
  78. 	printf ("Soluciones descartadas = %12d\n", factorial(N) - iteraciones);
  79.  
  80. 	system("pause");
  81. 	return 0;
  82. }
  83.  

MOD EDIT: Etiquqtas GeSHi (por 2da vez).
« Última modificación: 6 Septiembre 2016, 20:32 pm por MCKSys Argentina » En línea
JonaLamper


Desconectado Desconectado

Mensajes: 394



Ver Perfil
Re: Viajante comercio
« Respuesta #4 en: 6 Septiembre 2016, 21:22 pm »
No sirve de mucho coger código por Internet, menos aún si estás aprendiendo y no sabes un concepto un poco avanzado como un DFS Depth First Search (búsqueda en profundidad). Yo te recomiendo que intentes hacer esto: debes establecer un punto de origen. En tu primer ejemplo había 4 pueblos (pueblo 0, pueblo 1, pueblo 2 y pueblo 3), vamos a suponer que queremos resolver el problema del viajante desde el pueblo 0 (o sea, partimos desde matriz[0][0]). De lo que se trata es de explorar todos los caminos y de VOLVER otra vez al origen (o sea, al pueblo 0). Con lo cual, vamos a tener que hacer las siguientes rutas:

Ruta 1: 0, 1, 2, 3, 0.
Ruta 2: 0, 1, 3, 2, 0.
Ruta 3: 0, 2, 1, 3, 0.
Ruta 4: 0, 2, 3, 1, 0.
Ruta 5: 0, 3, 2, 1, 0.
Ruta 6: 0, 3, 1, 2, 0.

Los números obviamente representan el pueblo al que vamos. Ahora bien, en tu matriz tenías: matriz[0][1] = 5, es decir, hay 5 km (por ejemplo) desde el pueblo 0 al pueblo 1. Pues bien, te animo a que intentes lo siguiente: recorre todas esas rutas que he puesto y quédate con la menor ruta. Cuando tengas la menor ruta, habrás resuelto el problema del viajante.

Por cierto, el número de combinaciones es n!, donde n es el número de ciudades a las que tienes que ir (sin contar el origen). En este caso: 3! = 6 rutas posibles.
« Última modificación: 6 Septiembre 2016, 21:24 pm por JonaLamper » En línea
Utilizar palabras para hablar de palabras es como utilizar un lápiz para hacer un dibujo de ese lápiz sobre el mismo lápiz.
alex64128

Desconectado Desconectado

Mensajes: 1


Ver Perfil
Re: Viajante comercio
« Respuesta #5 en: 13 Noviembre 2016, 18:30 pm »
Hola, publique el algoritmo del viajante de comercio en c en mi blog. Puedo afirmar que funciona para matrices simétricas puesto que resuelve un problema del viajante de comercio simétrico donde el coste entre A y B es igual que el de entre B y A.
Por favor, cuando copiéis código de un blog, quitarle por lo menos el copyright o el autor quedará mal si lo habéis modificado... para intentarlo hacer no simétrico.
Saludos, comunidad informática.
Código
  1. /* SOLUCIÓN OPTIMA VIAJANTE DE COMERCIO SIMÉTRICO */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define N 8					// Numero de ciudades
  6. #define MIN 1				// Distancia minima
  7. #define MAX 9				// Distancia maxima
  8. #define CIUDAD_ORIGEN 0		// Ciudad origen = A
  9. #define SEMILLA 1024		// Semilla para repetir el experimento
  10.  
  11. #define TRUE (1 == 1)
  12. #define FALSE (1 != 1)
  13.  
  14. char ciudades[18] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R'};
  15.  
  16. int d[N][N];				// Matriz de distancias
  17. int visitadas[N];			// Ciudades visitadas por el algoritmo
  18. int suma = 0;				// Suma de costes
  19. int optima = 999999;		// Solucion optima inicial
  20. int iteraciones = 0;		// Numero de iteraciones
  21. int solucion[N];			// Vector con el trayecto realizado
  22.  
  23. void matriz_distancias (void) {
  24. 	srand(SEMILLA);	
  25. 	for (int i = 0; i < N; i++) {
  26. 		for (int j = 0; j < N; j++) {
  27. 			if (i == j) {
  28. 				d[i][j] = 0;
  29. 			} else {
  30. 				d[i][j] = (rand() % MAX) + MIN;
  31. 				d[j][i] = d[i][j];
  32. 			}				
  33. 		}				
  34. 	}
  35.  
  36. 	for (int i = 0; i < N; i++) {
  37. 		for (int j = 0; j < N; j++) {
  38. 			printf ("%3d", d[i][j]);
  39. 		}
  40. 		printf ("\n");
  41. 	}
  42. }
  43.  
  44. void busqueda_profundidad (int nivel, int origen, int suma, int visitadas[]) {
  45. 	visitadas[origen] = TRUE;
  46. 	solucion[nivel - 1] = origen;
  47. 	iteraciones++; 
  48. 	for (int destino = 0; destino < N; destino++) {
  49. 		if (visitadas[destino] == FALSE) {			
  50. 			suma = suma + d[origen][destino];
  51. 			if (suma < optima) {				
  52. 				busqueda_profundidad(nivel + 1, destino, suma, visitadas);
  53. 			}
  54. 			if (nivel == (N - 1)) {							
  55. 				suma = suma + d[destino][CIUDAD_ORIGEN];
  56. 				if (suma < optima) {
  57. 					optima = suma;
  58. 					printf ("Estableciendo nueva solucion optima, coste = %6d\n", optima);
  59. 					printf ("Solucion = { ");
  60. 					for (int i = 0; i < N; i++) {
  61. 						printf (" %c, ", ciudades[ solucion[i] ]);
  62. 					}
  63. 					printf (" %c }\n\n", ciudades[CIUDAD_ORIGEN]);
  64. 				} 
  65. 			} else {
  66. 				suma = suma - d[origen][destino];
  67. 			}
  68. 			visitadas[destino] = FALSE;
  69. 		}
  70. 	}
  71. }
  72.  
  73. int factorial (int n) {
  74. 	int f = 1;
  75. 	for (int i = n; i > 1; i--) {
  76. 		f = f * i;
  77. 	}
  78. 	return f;
  79. }
  80.  
  81. int main (void) {	
  82. 	printf ("RESOLUCION DEL PROBLEMA DEL VIAJANTE DE COMERCIO\n");
  83. 	printf ("(c) Alejandro Portero Gimeno 2015\n\n");
  84.  
  85. 	matriz_distancias();
  86.  
  87. 	for (int i = 0; i < N; i++) {
  88. 		visitadas[i] = FALSE;	
  89. 	}
  90.  
  91. 	printf ("\nNum. ciudades = %d\n\n", N);
  92.  
  93. 	busqueda_profundidad (1, CIUDAD_ORIGEN, suma, visitadas);
  94.  
  95. 	printf ("Iteraciones            = %12d\n", iteraciones);
  96. 	printf ("Soluciones totales     = %12d\n", factorial(N-1));
  97. 	printf ("Soluciones descartadas = %12d\n", factorial(N-1) - iteraciones);
  98.  
  99. 	system("pause");
  100. 	return 0;
  101. }
  102.  
  103.  

MOD: No hacer doble post. Usar el botón modificar.
« Última modificación: 24 Abril 2017, 00:08 am por MCKSys Argentina » En línea
jca1

Desconectado Desconectado

Mensajes: 59


Ver Perfil
Re: Viajante comercio
« Respuesta #6 en: 16 Octubre 2022, 22:00 pm »
Hola, yo hice un programa que resuelve el problema del viajante de comercio sin necesidad de probar todas las posibilidades; usando programación lineal.
Depende de cada caso su tiempo de ejecución.
En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Problema viajante de comercio dinamico
Java 		josnick 0 3,141 Último mensaje 31 Mayo 2014, 01:23 am
por josnick
Problema viajante de comercio (TSP)
Programación General 		jca1 2 3,157 Último mensaje 19 Febrero 2021, 17:15 pm
por jca1
Problema del viajante de comercio - Branch and Bound « 1 2 3 4 »
Programación General 		jca1 30 26,393 Último mensaje 24 Mayo 2022, 18:37 pm
por jca1
Metodos de resolver el problema del "viajante de comercio" mediante programación lineal
Programación General 		jca1 1 4,536 Último mensaje 8 Junio 2023, 23:52 pm
por Serapis
Variante del problema del viajante de comercio o TSP
Programación General 		jca1 0 755 Último mensaje 10 Agosto 2024, 12:54 pm
por jca1
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines