Herramientas de usuario
algoritmos-oia:problemas-generales:travelling-salesman-problem
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Próxima revisión | Revisión previa | ||
|
algoritmos-oia:problemas-generales:travelling-salesman-problem [2018/01/04 02:30] sebach creado |
algoritmos-oia:problemas-generales:travelling-salesman-problem [2018/01/04 03:58] (actual) sebach [Enunciado] |
||
|---|---|---|---|
| Línea 1: | Línea 1: | ||
| - | === Travelling salesman problem === | + | ===== Travelling salesman problem ===== |
| ==== Enunciado ==== | ==== Enunciado ==== | ||
| Línea 19: | Línea 19: | ||
| ... | ... | ||
| + | |||
| + | Primero, como comentario, veamos que hay $(n-1)!$ caminos posibles, ya que al principio podemos ir a cualquiera de las otra $n-1$ ciudades, desde allí a la restantes $n-2$, ectétera. Por lo que la complejidad del algoritmo más "bruto" posible, que mire todos los caminos, será $O(n*(n-1)!) = O(n!)$, ya que para implementarlo tenemos que guardar qué ciudades ya visitamos. Si bien la complejidad de nuestra solución, que será $O(2^n*n^2)$, parece grande, cuando $n=11$, $O(n!) = O(4*10^7)$, que es lo mismo que nuestra solución para $n=17$. Y la solución en tiempo $n!$ necesitaría aproximadamente $1$ año para resolver el problema, contra $1$ segundo de nuestra solución. | ||
| + | |||
| + | Ahora sí. | ||
| ==== Solución ==== | ==== Solución ==== | ||
| Línea 35: | Línea 39: | ||
| - | Acá ya podemos ver que la complejidad es $\large O(2^n*n^2}$, ya que tenemos $2^n*n$ estados, y para calcular el valor de cada uno tenemos que hacer $O(n)$ pasos (ya que los valores que usamos adentro ya fueron calculadas previamente). | + | Acá ya podemos ver que la complejidad es $\large O(2^n*n^2)$, ya que tenemos $2^n*n$ estados, y para calcular el valor de cada uno tenemos que hacer $O(n)$ pasos (los valores que usamos adentro ya fueron calculadas previamente). |
| Línea 53: | Línea 57: | ||
| ==== Implementación ==== | ==== Implementación ==== | ||
| + | |||
| + | Si todavía no leyeron el link que dejé arriba de programación dinámica en subconjuntos, léanlo ahora. Ahí se ve cómo formar los subconjuntos, cómo saber si una ciudad está en un subconjunto, cómo escribir subconjuntos con un solo elemento y todo lo necesario para entender el código y la breve explicación de acá abajo. | ||
| + | |||
| Veamos que para un estado, siempre vamos a necesitar muchos estados donde el subconjunto tiene una ciudad menos que el estado actual. Entonces, si calculamos las respuestas recorriendo en orden según la cantidad de elementos del subconjunto, vamos a poder obtener bien todas las respuestas. | Veamos que para un estado, siempre vamos a necesitar muchos estados donde el subconjunto tiene una ciudad menos que el estado actual. Entonces, si calculamos las respuestas recorriendo en orden según la cantidad de elementos del subconjunto, vamos a poder obtener bien todas las respuestas. | ||
| + | En vez de recorrerlos ordenados por tamanio, podemos simplemente recorrer desde el número $1$ en adelante, que si lo vemos como subconjuntos estamos mirando: | ||
| + | $00....001$, | ||
| + | $00....010$, | ||
| + | $00....011$, | ||
| + | $00....101$, | ||
| + | $00....110$, | ||
| + | $00....111$. ... | ||
| - | Si todavía no leyeron el link que dejé arriba de programación dinámica en subconjuntos, léanlo ahora. Ahí se ve cómo formar los subconjuntos, cómo saber si una ciudad está en un subconjunto, cómo escribir subconjuntos con un solo elemento y todo lo necesario para entender el código de abajo. | + | Entonces cuando vemos un subconjunto, todos los subconjuntos de ese subconjunto ya los habremos visto, ya que sabemos que un subconjunto de un conjunto se representa como el conjunto inicial menos la suma de $2$ elevado a la posición de cada elemento que sacamos, por lo que en esta representación el subconjunto será menor, y si vamos en orden como dijimos, garantizamos haber visto a todos los subconjuntos del subconjunto. |
| + | También, hay que tener el cuidado de que todos los subconjuntos que nos interesan deben incluir a nuestra ciudad $s$. | ||
| + | Y además, cuando tengamos $2$ ciudades, vamos a querer como anteúltima ciudad a $a$; pero si estamos en un subconjunto con más de $2$ ciudades, no tiene sentido decir que la ciudad $s$ está como anteúltima porque debe estar primera. | ||
| + | Esto lo podemos manejar o en un $if$, ver que la anteúltima no sea $s$ o sea $s$ y el subconjunto tenga $2$ ciudades, o podemos definir al principio los valores de la dinámica cuando el subconjunto tiene $2$ ciudades, que será simplemente la distancia entre $s$ y cada ciudad, y luego prohibir que la anteúltima sea $s$. | ||
| ==== Código ==== | ==== Código ==== | ||
| Línea 85: | Línea 102: | ||
| vector< vector<int> > mejorCamino((1<<n), vector<int>(n, INF)); | vector< vector<int> > mejorCamino((1<<n), vector<int>(n, INF)); | ||
| mejorCamino[(1<<s)][s]=0; | mejorCamino[(1<<s)][s]=0; | ||
| - | forsn(i, 1, (1<<n)){ | + | forn(i, n){ |
| + | if(i!=s){ | ||
| + | mejorCamino[(1<<s)+(1<<i)][i]=matriz[s][i]; | ||
| + | } | ||
| + | } | ||
| + | forsn(i, 1, (1<<n)){ // no tiene sentido ver el conjunto vacio | ||
| int subcon=i|(1<<s); // Si o si tengo que incluir a s | int subcon=i|(1<<s); // Si o si tengo que incluir a s | ||
| forn(c, n){ // quiero terminar en c | forn(c, n){ // quiero terminar en c | ||
| - | int best = INF; | ||
| if( c!=s && (subcon & (1<<c)) ){ // tiene sentido terminar ahi solo si esta en subcon | if( c!=s && (subcon & (1<<c)) ){ // tiene sentido terminar ahi solo si esta en subcon | ||
| + | int best = INF; | ||
| forn(a, n){ // pruebo que la ciudad a sea la anteultima | forn(a, n){ // pruebo que la ciudad a sea la anteultima | ||
| - | if( a!=s && a!=c && (subcon & (1<<a)) ){ | + | if( a!=c && (subcon & (1<<a)) ){ |
| - | best=min(best, mejorCamino[subcon-(1<<a)][a] + matriz[a][c]); | + | best=min(best, mejorCamino[subcon-(1<<c)][a] + matriz[a][c]); |
| } | } | ||
| } | } | ||
| + | mejorCamino[subcon][c]=best; | ||
| } | } | ||
| - | mejorCamino[subcon][c]=best; | ||
| } | } | ||
| } | } | ||
| int ans=INF; | int ans=INF; | ||
| + | int ultima; | ||
| forn(i, n){ | forn(i, n){ | ||
| if(i!=s){ | if(i!=s){ | ||
| - | ans=min(ans, mejorCamino[(1<<n)][i] + matriz[i][s]); | + | int terminandoAca = mejorCamino[(1<<n)-1][i] + matriz[i][s]; |
| + | if(ans>terminandoAca){ | ||
| + | ans=terminandoAca; | ||
| + | ultima=i; | ||
| + | } | ||
| } | } | ||
| } | } | ||
| - | cout<<ans<<endl; | + | cout<<"El camino más corto mide "<<ans<<" y termina en la ciudad "<<ultima<<endl; |
| } | } | ||
| Línea 111: | Línea 138: | ||
| - | Piense cómo se podría reconstruir el camino. Intenten usar estrategias similares a las de Dijkstra por ejemplo para la reconstrucción del camino. | + | Pensar cómo se podría reconstruir el camino. Intenten usar estrategias similares a las de Dijkstra por ejemplo para la reconstrucción del camino. |
algoritmos-oia/problemas-generales/travelling-salesman-problem.1515033006.txt.gz · Última modificación: 2018/01/04 02:30 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
