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

102 meneos

3498 clics

¿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.”

50 52 0 K 265

25 comentarios

50 52 0 K 265

#8 aironman

#6 Aquí hay muchos ingenieros de software e informáticos en general.

8 76
#13 CrudaVerdad *

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.

8 56
#17 --165145-- *

#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

3 49
#2 jmav

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

5 42
#1 difuso

No, siguiente pregunta.

5 41
#3 yusavi

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 ...

4 37
#18 CrudaVerdad

#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!

2 31
#5 CuaC

Depende... si es el ordenador cuántico de Seur problablemente no

3 30
#16 --165145--

#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

1 28
#19 --165145-- *

#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.

1 28
#4 shumoreniko19

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).

2 27
#21 --625430-- *

#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.

1 16
#9 --614891--

Qué tontería. De pequeñito mi padre me enseñó que "el camino más corto entre dos puntos es aquel que se conoce".

1 14
#10 jmav

#6 Y que quieren tener.

Si no llegaran estas noticias ni siquiera quieren tener esa puta idea cómo otros.

1 14
#11 Xuanin71

Ya me decía mi cuñado que ser viajante era complicado.y yo sin creérmelo

1 14
#23 CrudaVerdad *

#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

0 11
#6 --214250--

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.

2 9
#7 omegapoint

#3 a mi me ha quedado clarísimo, que no me he enterado de nada.

0 9
#22 AsVHEn

#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

0 9
#25 --3560--

#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.

0 9
#14 JungSpinoza

#2 Con que soluciones el trafico de la M30 ya seria un gran avance

0 8
#20 --214250--

#16 Fíjate que de matemáticas sé un rato y tras tragarme el vídeo entero de Derivando me quedé a cuadros.

0 7
#12 drwatson

Me he quedado igual

0 6
#15 GrogXD

#2 En realidad el problema general sería el QAP Quadratic Assignment Problem, que se puede particularizar al TSP.

0 6
#24 --148836-- *

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.

0 6