algorithm - primero - metodo dijkstra

Algoritmo de búsqueda de ruta eficiente evitando el zigzag

Question

Esta pregunta ya tiene una respuesta aquí:

• Pathfinding - A * con menos turnos 2 respuestas

Estoy desarrollando un software que conecta objetos con cables. Este cableado tiene la regla de que estos cables no pueden pasar a otros objetos y no se acepta movimiento diagonal.

Todos los algoritmos de ruta más cortos que conozco (A *, dijkstra, etc.) encuentran este tipo de rutas:

No quiero los zigzags innecesarios en la segunda captura de pantalla. ¿Cómo logro este objetivo?

Nota: Cualquier persona que quiera probar los algoritmos puede usar this aplicación.

Otra nota: Esta es la situación exacta que no quiero. Encuentra la ruta en zigzag en lugar de la "vaya a la derecha hasta que alcance la posición x del objetivo, vaya hacia arriba hasta que alcance la posición y del objetivo", que tiene el mismo costo que la zigzag.

Answer 1

En este momento, su algoritmo responde a la pregunta "¿por qué cuadrados recorre el camino óptimo?" Su gráfica tiene un nodo para cada cuadrado y un borde para cada par de cuadrados adyacentes.

Cámbielo a "¿Dónde cruza el camino óptimo los bordes entre cuadrados?"

Tu gráfica cambiará:

• Gráficos de nodos: medio de cada borde entre cuadrados adyacentes + inicio + acabado.
• Gráficos de bordes: en cada cuadrado se conectan todos los pares de bordes cuadrados.

Y ahora puede establecer un precio diferente para las conexiones de los bordes cuadrados opuestos y las conexiones de los bordes cuadrados adyacentes. Dar mayor peso a la segunda reducirá el número de zig-zags.

Answer 2

Internamente, el algoritmo evalúa muchos caminos posibles y elige el más corto.

Si ajusta el algoritmo ligeramente, por lo que calcula una penalización adicional para cada cambio en la dirección, entonces elegirá la ruta más corta con el menor número de cambios en la dirección.

Answer 3

Intuitivamente, puede hacer esto dando a su agente un "impulso".

Específicamente, aumente el tamaño de su espacio estatal en un factor de cuatro; realiza un seguimiento de si el agente se movió por última vez hacia arriba, a la derecha, a la izquierda o hacia abajo. Aumente los costos en su red por algún factor importante y asigne una pequeña penalización a los movimientos que cambien de dirección.

Answer 4

No estoy familiarizado con los algoritmos de búsqueda específicamente, pero este sería el mejor enfoque programático, que se explica a continuación.

Objetos que utilizamos:

vertex { //generic x,y coordinate
    int x;
    int y;
}
vertices[3]; //3 vertices: 0, 1, 2 (0 is start, 1 is mid, 2 is end);

Y nuestro algoritmo, que depende de la ruta más eficiente ya encontrada, no tiene rarezas como ¯ | _ | ¯

boolean hasObstacles = false;

int increment = 0;
//there''s some other ways to set this up, but this should make the most sense to explaining which way we need to go
if(vertices[0].x < vertices[2].x)
    increment = 1;
else
    increment = -1;

for(int i = vertices[0].x; i != vertices[2].x; i = i + increment) {
    //check for collision at coordinate (i, vertices[0].y), set hasObstacles to true if collision
}

if(vertices[0].y < vertices[2].y)
    increment = 1;
else
    increment = -1;

for(int i = vertices[0].y; i != vertices[2].y; i = i + increment) {
    //check for collision at coordinate (vertices[2].x, i), set hasObstacles to true if collision
}

if(!hasObstacles) {
    //we can remove these 3 vertices and add this point to our list of vertices.
    vertex corner = new vertex(vertices[2].x, vertices[0].y) // relocation of point
}

La exploración debe avanzar un vértice a la vez. Si los 3 vértices se reemplazan con un solo vértice, la siguiente exploración debe usar ese nuevo vértice como 0.

Answer 5

Su problema no es trivial porque, por ejemplo, si avanza con avidez tanto como pueda hacia arriba o hacia la derecha, podría encontrar un laberinto de objetos apretados que requiere una zig-zag loca para terminar, mientras que si se detuvo antes de laberinto apretado usted podría ser capaz de cambiar de dirección menos veces esencialmente rodeando el laberinto. Y podría encontrar este dilema en cualquier lugar a lo largo de su camino, no solo al principio. Una forma de resolver este problema es usar Dijkstra y definir una cuadrícula de ubicaciones a las que puede viajar, y luego definir un movimiento que tenga 2 pasos de largo en lugar de 1 paso. Defina que la distancia entre dos puntos de la cuadrícula conectada sea muy pequeña si el movimiento es puramente horizontal o vertical pura en una dirección orientada, y muy grande si el movimiento cambia de dirección en el medio. Luego, asumiendo que la longitud del camino de principio a fin sea uniforme, el camino más corto desde el inicio hasta el final en este marco de doble movimiento será el camino que minimice la cantidad de zig-zag. Si la longitud de la ruta de inicio a final es impar, entonces use los puntos de la cuadrícula a un espacio de distancia horizontal y verticalmente para comenzar y luego la longitud de la ruta de inicio a final será uniforme (aunque tendrá que ejecutar la búsqueda de ruta para ambas Posibles posiciones de inicio modificadas).

Answer 6

Todo lo que necesita es modificar un poco la heurística de su algoritmo A *. Uno en lo más alto de mi cabeza: si no te gustan estos giros, puedes penalizar cada turno.

Por lo tanto, su heurística dependerá de la cantidad de vueltas y de la distancia de Manhattan al objetivo. Una cosa importante es no olvidar que no debe sobreestimar la distancia a la meta. Lea más sobre cómo seleccionar heurística aquí .

Answer 7

Use un par de valores (dobles, enteros, lo que sea) para su cálculo de la distancia.

El primero es la distancia, el segundo el número de vueltas.

Ordenar léxicamente, por lo que el primero importa más que el segundo.

Esto es más limpio que "usar una pequeña penalización por turnos" tanto matemática como programáticamente.

Cada nodo está duplicado. El nodo "ingresó verticalmente" y "ingresó horizontalmente", ya que hacen una diferencia en el número de giros.

La heurística es la distancia de Manhattan, con un giro si no está exactamente horizontal o verticalmente alineado con el objetivo.

Como inconveniente, esta técnica se interpone en el camino de la optimización del punto de salto, ya que hay muchas menos rutas simétricas a una ubicación (ya que algunas rutas tienen más giros que otras).

Answer 8

Su algoritmo actual encuentra una ruta más corta, Pmin , pero el algoritmo mejorado debe encontrar una ruta más corta que tome el número mínimo de giros (Pmin, Tmin) . La solución general requiere que trabaje con un par de números en lugar de un solo número. Si el Pnew recién encontrado es más pequeño que el Pmin actual O si es igual, pero Tnew es más pequeño que (Pnew, Tnew) tome (Pnew, Tnew) como nueva ruta mínima.

Si el tablero es lo suficientemente pequeño, aún podría usar un solo número como lo usa actualmente, pero este número debe ser un número compuesto C = P * N + T , donde N es suficientemente grande y un número constante lo suficientemente pequeño. Debe ser más grande que la T más grande posible para ese tablero, que es casi el número total de fichas en el tablero. También debe ser lo suficientemente pequeño como para que no haya un desbordamiento de enteros cuando el algoritmo maneja la ruta más grande en el tablero, que también es el número total de mosaicos en el tablero. Entonces, N debe cumplir estos dos términos (B es el número total de fichas en el tablero):

N > B
B * N < INT_MAX

Si B es más grande que SQRT(INT_MAX) , este sistema no tiene solución y debería ir con un par de valores. N debe ser SQRT(INT_MAX) , que para 2 ³² es 2 ¹⁶ .

El principal problema ahora es cómo contar todos los giros, pero eso depende del algoritmo que tengas. No debería ser demasiado difícil agregar esa parte.