Me refiero a cuando desde todas se puede ir a las demás sin que haya obstáculos.
Me han propuesto practicar resolver este tipo de problemas pero parecen obvios. Demostrar que una solución es la correcta, parece aburrido también.
Un ejemplo: En ese caso esos números no parecen reflejar las distancias, el dibujo está mal hecho o se refiere a costes de traslado, que es otra cosa (ruta menos costosa). Si el dibujo está bien hecho parece que se ve a simple vista la solución o que es practicamente lo mismo qué camino se siga.
Como en Flash se complica un poco medir una línea diagonal, se me complica comprobarlo. Aquí hice algunos: - Veo que si se empieza desde el centro o similar es más complicado. - En los que tienen fondo celeste no sé si hay diferencia, acortar por un lado hace que se alargue por otro. - El que está debajo de esos tiene un camino más óptimo creo, es decir que sí fallé al intentar resolverlo "a ojo". - En el que está en verde me costó decidir por dónde empezar.
Bueno, supongo que sí tiene su ciencia y no es tan obvio como pensé, algún día quizá intente resolverlo con programación.
¿Qué cuentan al respecto? ¿qué casos son los más difíciles? ¿en general a ojo cómo los resuelven? Por ejemplo una buena estrategia parece 1ero pensar dónde se ha de terminar, que suele ser un punto alejado de los demás ¿no? ¿cuales serían los siguientes pasos? Hablo de hacerlo a ojo, resolverlo con fuerza bruta es otro tema.
En mi caso intentaria crear un array de dos dimensiones con todas las posibles cantidades de distancia en orden y luego guardaria el resultado de cada distancia en otro array y lo ordenaria de menor a mayor, luego eso deberia decirme cual ruta es la mas corta dependiendo de cual tenga la menor cantidad de recorrido.
La complicacion deberian ser dos, la primera es intentar resolver como calcular el arbol de posibles caminos y lo otro es como manejar cantidades de posibles caminos, por ejemplo, en la primera imagen se ve facil porque son pocas opciones pero en los de abajo se ve que deben haber muchos caminos y esto podria generar una cantidad de posibles caminos exponencialmente grande y llevar eso a un array en memoria puede ser no conveniente en temas de uso de hardware.
Para resolver lo de las cantidades se me ocurre crear un archivo plano de resultados, nada estructural como json que requiera de cargarse todo en memoria, por ejemplo, un csv, o sea, valores separados por coma y saltos de linea por cada posible ruta, eso deberia generarte por ejemplo, un archivo de 1gb de posibles caminos.
Ahora que tienes el archivo hay que ordenar y para ordenar hay que calcular el resultado, asi que hay que ir linea por linea y sumar todos los valores de distancia y los agregaria como primer numero de la lista en cada fila, por ejemplo "10:1,5,4", despues de eso haria un sort eficiente pero sin usar el comando cat+sort del bash porque eso usaria demasiada memoria ram, en ves de eso tocaria usar alguna tecnica ya conocida de ordenamiento por datos en archivos y creo haber visto muchas en youtube, la tecnica es que debes hacer muchas iteraciones e ir guardando resultados muchas veces, no basta solo con abrir el archivo y contar todo una sola ves, hay que abrir un archivo de resultados junto al de rutas e ir traspasando el resultado de cada fila de un archivo a otro recalculando cada ves en que lugar va y para eso hay muchas formas y tecnicas:
He ordenado los videos desde el mas basico y facil de comprender hasta el mas complejo, para que te puedas dar una idea mejor de que es lo que estas buscando. Se trata un poco del principio del funcionamiento de las redes neuronales, hasta donde se aun no hay un consenso sobre una forma "definitiva" de hacer el ordenamiento ya que es algo complejo y tiene muchas variantes, cada algoritmo tiene sus ventajas y desventajas segun el tipo de dato, velocidad, etc.
Por ejemplo, si encuentras un algoritmo mas eficiente del que ya existe podrias acortar el tiempo de entrenamiento de las redes neuronales y hacer que las ia sean generadas con menor tiempo, hoy en dia las grandes empresas deben utilizar supercomputadores con mucha potencia para crear redes complejas que en si son estas busquedas de los caminos mas faciles para llegar de una neurona a otra multiplicado por millones de veces, algunos usan las gpu para eso, por eso es un tema complejo de resolver.
Saludos.
« Última modificación: 5 Septiembre 2024, 14:41 pm por WHK »
Autor
En línea
- 
