Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
algoritmos-oia:problemas-generales:travelling-salesman-problem [2018/01/04 03:22] sebach |
algoritmos-oia:problemas-generales:travelling-salesman-problem [2018/01/04 03:58] (actual) sebach [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 99: | Línea 103: | ||
mejorCamino[(1<<s)][s]=0; | mejorCamino[(1<<s)][s]=0; | ||
forn(i, n){ | forn(i, n){ | ||
- | if(i!=s){ | + | if(i!=s){ |
- | mejorCamino[(1<<s)+(1<<i)][i]=matriz[s][i]; | + | mejorCamino[(1<<s)+(1<<i)][i]=matriz[s][i]; |
- | } | + | } |
- | } | + | } |
forsn(i, 1, (1<<n)){ // no tiene sentido ver el conjunto vacio | 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 | ||
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; | + | 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!=c && (subcon & (1<<a)) ){ | if( a!=c && (subcon & (1<<a)) ){ | ||
Línea 113: | Línea 117: | ||
} | } | ||
} | } | ||
- | if(best!=INF){ | + | mejorCamino[subcon][c]=best; |
- | mejorCamino[subcon][c]=best; | + | |
- | } | + | |
} | } | ||
} | } | ||
Línea 125: | Línea 127: | ||
int terminandoAca = mejorCamino[(1<<n)-1][i] + matriz[i][s]; | int terminandoAca = mejorCamino[(1<<n)-1][i] + matriz[i][s]; | ||
if(ans>terminandoAca){ | if(ans>terminandoAca){ | ||
- | ans=terminandoAca; | + | ans=terminandoAca; |
- | ultima=i; | + | ultima=i; |
- | } | + | } |
} | } | ||
} | } | ||
Línea 136: | 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. |