Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:problemas-generales:travelling-salesman-problem [2018/01/04 03:50]
sebach
+++ algoritmos-oia:problemas-generales:travelling-salesman-problem [2018/01/04 03:58] (actual)
sebach [Enunciado]
@@ Línea 20: / Línea 20: @@
-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=12$, $O(n!) = O(4*10^8)$, que es lo mismo que nuestra solución para $n=20$.
+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í.

OIA-Wiki