Portada
mis comunidades
otras secciones
#13:
Fácilmente: tienes tres ciudades A, B, C, los posibles recorridos son:
ABCA
ACBA
BACB
BCAB
CABC
CBAC
Es decir 3! (3 factorial): 3*2*1 = 6
De esas 6 rutas se evalúa cuál es la menos costosa (sumando cuanto cuesta ir de una ciudad a otra y donde el valor del pasaje es distinto, inclusive hay diferencia de costo ir de A a B que de B a A)
¿Y si son 5 ciudades? Entonces son 5! Rutas: 5*4*3*2*1=120 rutas
Hacerlo para 30 ciudades y la cantidad es enorme: 265252859812191058636308480000000
Así un computador evaluará 1 billón de rutas por segundo, tardaría 265252859812191058636 segundos = 8,4111130077E12 años, eso es mucho tiempo.
ABCA
ACBA
BACB
BCAB
CABC
CBAC
Es decir 3! (3 factorial): 3*2*1 = 6
De esas 6 rutas se evalúa cuál es la menos costosa (sumando cuanto cuesta ir de una ciudad a otra y donde el valor del pasaje es distinto, inclusive hay diferencia de costo ir de A a B que de B a A)
¿Y si son 5 ciudades? Entonces son 5! Rutas: 5*4*3*2*1=120 rutas
Hacerlo para 30 ciudades y la cantidad es enorme: 265252859812191058636308480000000
Así un computador evaluará 1 billón de rutas por segundo, tardaría 265252859812191058636 segundos = 8,4111130077E12 años, eso es mucho tiempo.
#2:
Es un problema general y no un problema del ordenador cuántico. El reto es si el ordenador cuántico puede resolverlo, También es una base para resolver otros muchos problemas de dificultad.
https://es.wikipedia.org/wiki/Problema_del_viajante
https://es.wikipedia.org/wiki/Problema_del_viajante
Comentarios
Fácilmente: tienes tres ciudades A, B, C, los posibles recorridos son:
ABCA
ACBA
BACB
BCAB
CABC
CBAC
Es decir 3! (3 factorial): 3*2*1 = 6
De esas 6 rutas se evalúa cuál es la menos costosa (sumando cuanto cuesta ir de una ciudad a otra y donde el valor del pasaje es distinto, inclusive hay diferencia de costo ir de A a B que de B a A)
¿Y si son 5 ciudades? Entonces son 5! Rutas: 5*4*3*2*1=120 rutas
Hacerlo para 30 ciudades y la cantidad es enorme: 265252859812191058636308480000000
Así un computador evaluará 1 billón de rutas por segundo, tardaría 265252859812191058636 segundos = 8,4111130077E12 años, eso es mucho tiempo.
#13, en realidad no es n! sino (n-1)!/2 evaluaciones la necesarias (salvo para n=1 y n=2 ). En concreto en el caso de 3 ciudades solo hay un recorrido, ya que los otros 5 son en realidad equivalentes. Para empezar observa que se da la misma distancia en ABCA que en BCAB y que en CABC, vamos, es el mismo recorrido circular pero partiendo de un punto distitno. Así que podemos fijar cuál es la ciudad de partida y nos quedará solo n-1 para combinar. ¿Y por qué divido entre 2? Pues porque un recorrido y su inverso son iguales de largo. Por tanto ABCA y ACBA son iguales.
En fin, que en el caso de 3 ciudades todos los recorridos son iguales.
En el caso de 5 ciudades tus 120 rutas se reducen a 12.
Para 30 ciudades por tanto divide esos años entre 60, y en menos de 2 meses habrás terminado
#17 si lees mi enunciado, los costos de ir de una ciudad a otra son distintos así:
Ir de A a B cuesta €1
Ir de A a C cuesta €5
Ir de B a A cuesta €3
Ir de B a C cuesta €4
Ir de C a A cuesta €2
Ir de C a B cuesta €6
Tome una ruta: A,B,C,A vale €1+€4+€2=€7
Tome otra ruta: B,A,C,B vale €3+€5+€6=€14
La ruta menos costosa es la primera.
Pero habrá que probar las 6 rutas para estar seguros. Por eso es N!
#18, vale, no sabía que el camino de ida y de vuelta se consideraban que no son igual de costosos, me salté esa línea. Por tanto no se puede eliminar los caminos inversos, pero sí que se podría fijar la ciudad de partida y por tanto las rutas a tener en cuenta serían (n-1)!. En el caso de 3 ciudades solo habría 2 rutas a considerar, A->B->C->A y A->C->B->A. Con eso sería suficiente. La ruta A->B->C->A y la B->C->A->B son igual de costosas pongas el coste que pongas a los viajes entre ciudades.
Para 3 ciudades por tanto 2 rutas.
Para 5 ciudades 60.
Para 30 hay que dividir esos años por 30, menos de 4 meses.
#18
Aunque cuesten diferente se siguen pudiendo eliminar, porque ABCA tiene los mismos viajes que BCAB y que CABC
ABCA BCAB CABC
ABCA BCAB CABC
ABCA BCAB CABC
Y lo mismo para las otras 3.
#19
#22 #32 Tienen razón, pensaba en otro problema similar, en el que el viajero no vuelve a la ciudad de origen, en ese caso si es N! un ejemplo:
Tres ciudades: A, B, C
COSTOS
A->B 9
A->C 10
B->A 11
B->C 1
C->A 8
C->B 2
RUTAS POSIBLES
A->B->C 9 + 1 = 10
A->C->B 10 + 2 = 12
B->A->C 11 + 10 = 21
B->C->A 1 + 8 = 9
C->A->B 8 + 9 = 17
C->B->A 2 + 11 = 13
Son seis rutas y todas con costos distintos, la ruta menos costosa es B->C->A
#13 Debido al crecimiento exponencial de la función, muy pronto encontraríamos otra barrera aun más infranqueable, y es que no habría suficiente energía en el universo para computar todas las probabilidades. Suponiendo que la evaluación de un ruta consumiera exactamente un cuanto de energía, el resultado final sería varios ordenes de magnitud superior a la contenida en el cosmos.
Es un problema general y no un problema del ordenador cuántico. El reto es si el ordenador cuántico puede resolverlo, También es una base para resolver otros muchos problemas de dificultad.
https://es.wikipedia.org/wiki/Problema_del_viajante
#2 Con que soluciones el trafico de la M30 ya seria un gran avance
#2 En realidad el problema general sería el QAP Quadratic Assignment Problem, que se puede particularizar al TSP.
No, siguiente pregunta.
Pongo a Dios por testigo que he intentado leerlo. Yo sería de los que confunden“no determinista" con “no polinómico.” si supiera de que se está hablando ...
#3 a mi me ha quedado clarísimo, que no me he enterado de nada.
Depende... si es el ordenador cuántico de Seur problablemente no
TL;DR: ¿El problema de la decisión TSP es un problema BQP? Nadie lo sabe, pero lo expertos opinan que no lo es (salvo que P=NP).
#20 Para estos vídeos lo mejor es dejar el cerebro en blanco y aparentar ser tonto y querer aprender. Lo mismo que hago para programación. En serio. Si no, me pongo en plan analítico y al final no me sale nada. Y en estas cosas el análisis aparece al final del todo haciendo "flashbacks", no en medio hilando cabos.
Igual es que tengo mentalidad de ingeniería inversa, pero se me da mejor desgranar una cosa "para atrás" que entender los conceptos directamente, me hago demasiadas preguntas.
Qué tontería. De pequeñito mi padre me enseñó que "el camino más corto entre dos puntos es aquel que se conoce".
Ya me decía mi cuñado que ser viajante era complicado.y yo sin creérmelo
Entre los envíos de política y los de la mula Francis se demuestra empíricamente que la gente de meneame vota cosas sobre las que no tiene ni puta idea.
La verdadera España.
#6 Aquí hay muchos ingenieros de software e informáticos en general.
#6 Y que quieren tener.
Si no llegaran estas noticias ni siquiera quieren tener esa puta idea cómo otros.
#6, el otro día envié una demostración de que Pi es irracional y llegó a portada. Diría que el 90% de los que menearon dicha noticia no se enteraron bien de la demostración, por lo que apunta a lo que dices
#16 Fíjate que de matemáticas sé un rato y tras tragarme el vídeo entero de Derivando me quedé a cuadros.
Me he quedado igual
Yo aplicaría un quadtree (o árbol quaternario), lo cual es un proceso recursivo, sobre un plano euclidiano con desplazamiento (1,1). Complejidad: siendo c una constante O(c^O(c)) = O(1), se puede implementar un algoritmo que de hecho sea en tiempo polinomial, dependiendo del grado de detalle.