Herramientas de usuario
algoritmos-oia:problemas-generales:travelling-salesman-problem
Diferencias
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:25] 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 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 | ||
| Línea 107: | Línea 111: | ||
| 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: | ||
| } | } | ||
| } | } | ||
| - | mejorCamino[subcon][c]=best; | + | mejorCamino[subcon][c]=best; |
| } | } | ||
| } | } | ||
| Línea 123: | 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 134: | 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.1515036313.txt.gz · Última modificación: 2018/01/04 03:25 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
