Encontré un problema algorítmico y no sé cómo resolverlo. ¿Alguien me puede ayudar?

“¿Por qué reinventar la rueda?” Es una pregunta muy importante en la programación, y se aplica aquí también. Estoy seguro de que ya examinó los algoritmos existentes, pero no encontró nada adecuado. Esa es la belleza de los algoritmos: rara vez encajan perfectamente en su forma original, ¡pero puedes encontrar el mejor y comenzar desde allí ajustándolo! Si es lo suficientemente eficiente, tiene su solución. Si no es así, ¡acabas de encontrar una nueva razón para un nuevo algoritmo!

Entonces, ¿quieres encontrar el camino más corto entre A y B? ¿Has mirado algoritmos como Dijkstra? Ellos hacen exactamente eso. Por supuesto, no se ajustan a su caso específico (sin giros a la derecha), pero esa es la parte de aplicación de la que hablé anteriormente.

Comenzaría con un algoritmo como Dijkstra y simplemente no permitiré que gire a la derecha comprobando si el ángulo del nodo que está tratando de tomar es mayor que el ángulo del nodo más opuesto al nodo que vino. desde. Si es así, no permita que vaya de esa manera. Esto también se puede aplicar de otras maneras, si no tiene ángulos predefinidos, por ejemplo, a través de la ubicación.

¡La mejor de las suertes!

Así es como abordaría esto:

Imagine las calles y las intersecciones como una matriz N por M. Entonces, la intersección superior izquierda sería la posición (0,0), la intersección superior derecha sería la posición (0, m), la posición inferior izquierda (n, 0) y la intersección inferior derecha (n, m). Las calles serían olvidadas, pero de hecho representarían una transición de una intersección a otra.

Ahora, lo otro que debe considerar es la dirección en la que se dirige, que puede ser Norte, Este, Sur y Oeste. Si está en la posición (x, y) y va hacia el norte, su nueva posición sería (x-1, y).

En su problema, no puede girar a la derecha, lo que significa que:

Si te diriges al norte, no puedes ir solo a la derecha (x, y +1)

Si te diriges a la derecha, no puedes ir solo hacia el sur (x + 1, y)

Si te diriges hacia el sur, no puedes ir solo hacia el oeste (x, y-1)

Si te diriges al oeste, no puedes ir solo al norte (x + 1, y)

Si lleva un registro del último movimiento, sabe cuáles son las posibles nuevas posiciones.

Ahora hay muchos algoritmos de búsqueda de rutas, pero para un gráfico pequeño probablemente podría usar una búsqueda simple de amplitud (calculando las posibles posiciones como acabo de mostrar), y podría encontrar las rutas óptimas.

Si está familiarizado con (¿tal vez estudiando?) Uno de los algoritmos estándar, es probable que exista la posibilidad de modificarlo para descartar soluciones (rutas) candidatas que giren a la derecha. Primero debe ordenar la lista de bordes en cada intersección en el sentido de las agujas del reloj para que + 1 número de módulo de bordes represente el índice del borde a la derecha.

El modelo gráfico de calles solo determina la adyacencia de las calles. Lo que necesita es un gráfico dirigido que tenga un vértice para cada dirección que puede recorrer en cada carretera y un borde desde el vértice a hasta el vértice b si va directamente de a a b sin girar a la derecha. Por supuesto, cada ventaja será ponderada por su función de costo asociada.

una vez que tenga eso, cualquier algoritmo de búsqueda de ruta estándar funcionará.

Voy a tomar un enfoque ligeramente diferente y preguntar primero, por qué alguien usaría este algoritmo.

La pregunta nos llega de forma anónima, por lo que no conocemos su país,

Soy de Estados Unidos. Lo que he encontrado es en realidad una regla diferente. Se ha informado a las personas, especialmente a las personas mayores, que es estadísticamente más seguro no girar nunca a la izquierda . La razón es que un giro a la izquierda en los EE. UU., Donde las personas conducen por el lado derecho de una carretera de doble sentido, requiere cruzar el carril de circulación en la dirección opuesta. A medida que los tiempos de reacción disminuyen, los errores en la percepción de la velocidad con la que los automóviles están cerrando una pausa en el tráfico, combinados con la demora en despejar el intercambio presentan probabilidades significativas de verse involucrado en un choque frontal.

Por lo tanto, aquí, se aconseja que tres giros a la derecha pueden ser más seguros que un giro a la izquierda, suponiendo algo similar a un patrón de cuadrícula y controles de tráfico que alternan el derecho de paso. Una señal de alto donde un carril menor cruza una carretera principal duplica el desafío. Pero un semáforo sería más seguro. Girar a la derecha, en una carretera principal, aún requiere un juicio rápido de la habitación para detenerse, pero cualquier aceleración reducirá la velocidad a la que el próximo automóvil cierra la brecha.

Sería al revés en las naciones donde las personas conducen por el lado izquierdo de la carretera. Girar a la derecha introduce el mismo riesgo de cruzar el tráfico que viene en sentido contrario.

Si este era el objetivo, entonces la representación debería incluir los controles de tráfico: tipo y rutas con derecho de paso en momentos comunes. Esto debería resolver cómo mantener la intención cuando se trata de cinco y seis intersecciones de calles.

Intente modelar cada intersección como múltiples nodos, uno para cada dirección desde la que podría acercarse. Puede usar la conectividad de estos nodos en un gráfico dirigido para modelar sus restricciones.

En una situación ideal, las intersecciones estarían a la misma distancia entre sí (como un normal de 4 vías). Entonces, si divide el número de caminos por la mitad, ese número determinaría lo que está justo enfrente de usted (si está completo, es que hay muchos caminos más y si es un decimal, entonces no hay ningún camino enfrente de usted en Un entorno ideal). Entonces puede decir que no vaya en un rango de números de intersección. Si eso tiene sentido.

¿Cómo defino girar matemáticamente a derecha e izquierda si el número de direcciones en una intersección es mayor que 4?

Parece que todos los demás cubrieron todas las cosas de la teoría de gráficos, así que pasaré a la pregunta real.

Cuando trato con dos objetos, uso un punto y un producto cruzado para determinar eso.

Hablando en términos generales, el producto de puntos le dará frente o atrás y el producto cruzado le dará izquierda y derecha.

Primero, deberías definir qué tan a la derecha está un giro a la derecha. Una vez que haga eso, usaría el producto cruzado para encontrar la colección de giros a la derecha y el producto de puntos para verificar cuán “correctos” son. Compare eso con su corrección definida y agréguelos a la colección de giros a la izquierda si pasan.