Menéame: comentarios [3210618]

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

--3560-- — Thu, 14 Nov 2019 09:16:14 +0000

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

» autor: --3560--

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

--148836-- — Wed, 13 Nov 2019 22:12:24 +0000

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.

» autor: --148836--

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

CrudaVerdad — Wed, 13 Nov 2019 21:49:30 +0000

#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

» autor: CrudaVerdad

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

AsVHEn — Wed, 13 Nov 2019 20:33:16 +0000

#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

» autor: AsVHEn

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

--625430-- — Wed, 13 Nov 2019 19:28:36 +0000

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

» autor: --625430--

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

--214250-- — Wed, 13 Nov 2019 19:22:33 +0000

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

» autor: --214250--

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

--165145-- — Wed, 13 Nov 2019 16:12:02 +0000

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

» autor: --165145--

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

CrudaVerdad — Wed, 13 Nov 2019 16:09:00 +0000

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

» autor: CrudaVerdad

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

--165145-- — Wed, 13 Nov 2019 15:57:53 +0000

#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

» autor: --165145--

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

--165145-- — Wed, 13 Nov 2019 15:51:16 +0000

#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

» autor: --165145--

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

GrogXD — Wed, 13 Nov 2019 14:55:55 +0000

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

» autor: GrogXD

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

JungSpinoza — Wed, 13 Nov 2019 13:56:37 +0000

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

» autor: JungSpinoza

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

CrudaVerdad — Wed, 13 Nov 2019 13:17:04 +0000

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.

» autor: CrudaVerdad

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

drwatson — Wed, 13 Nov 2019 12:48:42 +0000

Me he quedado igual

» autor: drwatson

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

Xuanin71 — Wed, 13 Nov 2019 12:02:21 +0000

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

» autor: Xuanin71

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

jmav — Wed, 13 Nov 2019 11:58:35 +0000

#6 Y que quieren tener.

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

» autor: jmav

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

--614891-- — Wed, 13 Nov 2019 11:13:57 +0000

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

» autor: --614891--

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

aironman — Wed, 13 Nov 2019 10:52:49 +0000

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

» autor: aironman

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

omegapoint — Wed, 13 Nov 2019 10:45:53 +0000

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

» autor: omegapoint

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

--214250-- — Wed, 13 Nov 2019 10:37:35 +0000

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.

» autor: --214250--

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

CuaC — Wed, 13 Nov 2019 10:04:30 +0000

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

» autor: CuaC

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

shumoreniko19 — Wed, 13 Nov 2019 09:56:42 +0000

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

» autor: shumoreniko19

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

yusavi — Wed, 13 Nov 2019 09:50:25 +0000

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

» autor: yusavi

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

jmav — Wed, 13 Nov 2019 09:47:55 +0000

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

» autor: jmav

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

difuso — Wed, 13 Nov 2019 09:25:38 +0000

No, siguiente pregunta.

» autor: difuso