El problema del viajante
20 11 2006Es un problema de dificil solución y visto que os gustan los rompecabezas os lo pongo. No os voy a dar más datos de los necesarios para que no lo mandeis a la mierda demasiado pronto, así, sin prejuicios, lo mismo sale algo interesante. El problema en cuestión es: – Tenemos una serie de ciudades conectadas entre sí por caminos. – Estos caminos son de igual longitud en un sentido que en el otro. – No hay caminos de valor negativo. – No hay dos caminos diferentes entre las mismas dos ciudades. – La distancia entre una ciudad y ella misma es 0 (obvio, pero hay que decirlo). Lo que queremos es encontrar la ruta de menor longitud que pase por todas las ciudades, empezando en una cualquiera y volviendo a esa misma. La ciudad por la que se empieza da igual puesto que el camino mínimo será el mismo desde todas ellas. No se puede pasar dos veces por la misma ciudad (en realidad he visto dos versiones diferentes, esta y otra que dice que no se puede pasar dos veces por el mismo camino aunque sí por la misma ciudad) Creo que con esto ya vale. La solución obvia es la de probar todos los posibles recorridos apuntando el menor de todos ellos para ir comparando con él. Lo que buscamos es una solución diferente de esta puesto que así se convierte en un problema de complejidad exponencial y eso no nos gusta nada. Queremos algo de complejidad polinómica o por el estilo. Pues ahí lo teneis, podeis comentar lo que querais en los comentarios. Podeis preguntar y aportar vuestras soluciones. Suerte con la búsqueda !!
que pesado eres….quieres que hagamos tu trabajo…eso es lo que tienes, o tenias que hacer para clase….buuuuuuuu
hombre, sé de sobra que no lo vais a hacer. os lo proponía como juego. es un problema que hasta el momento no tiene solución. si un buen puñado de matemáticos rayados no han sido capaces de conseguirlo, siendo realistas, no creo que vayais a conseguirlo vosotros.
pero nada, nada, no vuelvo a poner algo así, descuida ;)
x cierto, q todos estemos como hachisvertas me parece una mierda xq no se sabe quién ha comentado
no me fije en el nombre…
no dejes de poner cosas…una cosa no influye en la otra…
Pero cada uno puede poner las ciudades cómo le dé la gana?? No entiendo bien…
se supone que te las dan y a partir de ahi lo haces. es decir, tiene que valer para cualquier disposición sin saberla a priori, ya sean 3 o 300 ciudades con 3 o 300 caminos (si se considera que no se puede pasar 2 veces por la misma ciudad entonces no siempre es resoluble;) )
pues la práctica ya está hecha. nosotros el procedimiento que hemos seguido es ir creando el árbol de rutas posibles e irlo solucionando…cada vez que se llega a una rama que se pasa de un camino bueno conseguido se poda (se desecha) para no seguir con ella ya que cualquier camino que venga por ahí será mayor que el mejor que tenemos.
os pondría un post inmenso sobre el programa. cómo está hecho, en qué se basa, cómo simula cada una de las cosas….creo que sería inmensamente interesante…pero ninguno de vosotros lo va a leer (de hecho este comentario lo verá koko y quizá alguien de rebote dentro de unos meses) con lo cual no voy a molestarme ;)
salud
Yo se hacerlo pero con cadenas de ADN, tal como lo hizo Adleman en su época :)
Además, es mucho más rápido que tu C de toda la vida :p
más rápido sólo con gran cantidad de nodos, pero puede fallar la respuesta ;)