Algoritmo para encontrar la ruta más corta, con obstáculos

Question

Tengo una colección de Puntos que representa una cuadrícula, estoy buscando un algoritmo que me permita obtener la distancia más corta entre el punto A y B. La captura es cualquier punto (excluyendo A y B) pueden tener un obstáculo que obstruya el camino, y por lo tanto debe ser desviado. La ruta no puede moverse en diagonales.

Para una persona que quiere resolver este tipo de problema, me encontré con estas referencias a ser muy útiles:

http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first

Answer 1

Este es un excelente lugar para utilizar el A* search algorithm, una heurística algoritmo de búsqueda que encuentra rutas óptimas entre los puntos muy rápidamente, incluso cuando hay obstáculos presentes. La idea es convertir la cuadrícula en graph, donde cada celda de la cuadrícula es un nodo y en la que hay un borde entre dos celdas adyacentes que no están obstruidas entre sí. Una vez que tenga este gráfico, la respuesta que está buscando es la ruta más corta en el gráfico desde el nodo de inicio hasta el nodo de destino.

Para utilizar A *, necesitará una función heurística que "adivine" la distancia desde cualquier punto de la cuadrícula al cuadrado de destino. Una buena heurística para esto sería usar the Manhattan distance entre los dos puntos.

Si está buscando un algoritmo más fácil pero aún extremadamente eficiente para encontrar la ruta más corta, considere buscar en Dijkstra's algorithm, que se puede considerar como una versión más simple de A *. Es un poco más lento que A *, pero aún funciona muy rápido y garantiza una respuesta óptima.

Espero que esto ayude!

Answer 2

Se trata de un simple problema que puede ser resuelto mediante búsqueda en anchura

/** 
    * computing distance of each cell from the starting cell 
    * avoiding obstacles, 0 represents obstacle 1 represents non obstacle 
    * we can take only one step x-1;x+1;y-1;y+1 
*/ 

#include<iostream> 
#include<queue> 
#include<stdio.h> 
using namespace std; 

class XY 
{ 
public : 
int x; 
int y; 
}; 

int main() 
{ 
int grid[8][8] = { 
    {1,1,1,1,1,1,1,1}, 
    {1,0,0,0,1,1,1,1}, 
    {1,1,0,0,1,1,1,1}, 
    {1,1,0,0,1,1,1,1}, 
    {1,1,1,2,0,1,0,0}, 
    {1,1,1,1,1,1,1,1}, 
    {1,1,1,1,1,1,1,1}, 
    {1,1,1,1,1,1,1,1} 
}; 


int rows = 8; 
int cols = 8; 

int distance[rows][cols]; 

for(int m = 0;m<rows;m++) 
{ 
    for(int n =0;n<cols;n++) 
    { 
     distance[m][n] = -1; 
    } 
} 

queue<XY> iterator; 


XY xy; 
xy.x = 0; 
xy.y = 0; 
distance[0][0] = 0; 
iterator.push(xy); 

while(!iterator.empty()) 
{ 
    xy = iterator.front(); 
    iterator.pop(); 
    //printf("popped %d+%d\n",xy.x ,xy.y); 
    for(int p = -1;p<2;p++) 
    { 
     for(int q = -1;q<2;q++) 
     { 
      if(p == q)continue; 
      int i = xy.x + p; 
      int j = xy.y + q; 

      if(i<0)i=0; 
      if(j<0)j=0; 
      if(i>rows-1)i=rows-1; 
      if(j>cols-1)j=cols-1; 

      if(i== xy.x && j == xy.y)continue; 

    //    printf("i,j = %d,%d\n",i,j); 

      if(distance[i][j] == -1) 
      { 
    //     printf("******\n"); 
       if(grid[i][j] != 0) 
       { 
    //     printf("assigned distance %d to %d+%d\n",distance[xy.x][xy.y] + 1,i,i); 
       distance[i][j] = distance[xy.x][xy.y] + 1; 
       XY xyn; 
       xyn.x = i; 
       xyn.y = j; 
       iterator.push(xyn); 
     //     printf("pushed %d+%d\n",xyn.x,xyn.y); 
       } 
      } 

     } 
    } 
} 

for(int x = 0;x<rows;x++) 
{ 
    for(int y =0;y<cols;y++) 
    { 
     printf("%d ",distance[x][y]); 
    } 
    printf("\n"); 
} 
return 0; 
}