CULTURA, CIENCIA, DIVULGACIóN
100 meneos
3477 clics
¿Puede un ordenador cuántico resolver el problema del viajante de forma eficiente?

¿Puede un ordenador cuántico resolver el problema del viajante de forma eficiente?

El problema del viajante (TSP por Traveling Salesperson Problem) consiste en “dado cierto número de ciudades en un mapa conectadas por cierto número de carreteras, encontrar el camino más corto que un viajante de comercio debe tomar para visitar todas las ciudades exactamente una sola vez y retornar a la ciudad de origen.”

| etiquetas: hemeroteca , informática , computación cuántica , complejidad computacional
48 52 0 K 265
48 52 0 K 265
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 :-P ). 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…   » ver todo el comentario
#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.

es.wikipedia.org/wiki/Problema_del_viajante
#2 Con que soluciones el trafico de la M30 ya seria un gran avance :troll:
#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 xD
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 :-P
#16 Fíjate que de matemáticas sé un rato y tras tragarme el vídeo entero de Derivando me quedé a cuadros.
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.
Me he quedado igual

menéame