Algoritmia - Algoritmo para Recorrer ciudades en Bus

Tengo un proyecto en mente, el cual consiste en hacer un software que permita indicar en que parte de la ciudad estoy, a que parte debo ir; y que el sistema me ayude a hacer la combinacion correcta de buses para llegar a destino.

Lo importante es que hay que tener en cuenta:
-el horario en que pasa cada colectivo por cada parada.
-los diferentes dias de la semana tienen diferentes horarios
-mostrar diferentes opciones de recorrido.

Empece a hacerlo usando el algoritmo A*, pero para eso necesito hacer una matriz del tamaño de la ciudad y mantenerla en memoria. Sinceramente creo que es muy complicado hacerlo de esa manera. Otra idea que habia tenido es tomar el mapa y dividirlo en 4 pedazos o mas; y hacer diferentes cosas predefinidas cuando el destino esta en determinado cuadrante y el origen en otro.

Espero que haya sido claro lo que busco, en lo posible ideas o nombres de algoritmos que me puedan ayudar, asi como el A* me dio ciertas ideas; quizas hay otros que desconozco que me puedan servir de mucho.

Muchas Gracias!

Nicolás
Québec, Canadá.

Para abordar tu proyecto de optimización de rutas de transporte público, hay varias estrategias que podrías considerar. Aquí te presento algunas ideas y algoritmos que podrían ser útiles:

1. Algoritmo A* mejorado:
- Puedes seguir utilizando el algoritmo A*, pero con algunas mejoras para adaptarlo a tu situación específica. Por ejemplo, podrías considerar la inclusión de información sobre los horarios de los autobuses y la variabilidad de los horarios según los días de la semana.

2. Algoritmo de Dijkstra con tiempo variable:
- Modifica el algoritmo de Dijkstra para tener en cuenta el tiempo variable en las aristas del grafo, reflejando los horarios de los autobuses. Esto te permitirá encontrar la ruta más rápida según los horarios de transporte público.

3. División del mapa:
- La idea de dividir el mapa en secciones puede ser útil. Podrías implementar diferentes estrategias en cada sección según la densidad de paradas, la congestión del tráfico o la complejidad de las rutas.

4. Algoritmo de Floyd-Warshall para múltiples opciones:
- Considera el uso del algoritmo de Floyd-Warshall para encontrar todas las rutas posibles entre paradas. Esto te permitirá ofrecer diferentes opciones al usuario, teniendo en cuenta la variabilidad en los horarios y días de la semana.

5. Algoritmos de búsqueda en grafos ponderados:
- Además de A* y Dijkstra, puedes explorar otros algoritmos de búsqueda en grafos ponderados, como el algoritmo Bellman-Ford, que también pueden adaptarse a tu problema.

Recuerda que la elección del algoritmo dependerá de la complejidad y los requisitos específicos de tu proyecto. Es posible que debas realizar pruebas y ajustes para encontrar la solución más eficiente y adecuada a tus necesidades. ¡Buena suerte con tu proyecto desde el Estado de México, México, Nicolás!