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:27] 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 95: | Línea 99: | ||
matriz[v][u]=d; | matriz[v][u]=d; | ||
} | } | ||
- | int s=4; // seteamos la ciudad desde la cual queremos empezar | + | int s=0; // seteamos la ciudad desde la cual queremos empezar |
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; | ||
Línea 113: | Línea 117: | ||
} | } | ||
} | } | ||
- | if(best!=INF){ | + | mejorCamino[subcon][c]=best; |
- | mejorCamino[subcon][c]=best; | + | |
- | } | + | |
} | } | ||
} | } | ||
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. |