Алгоритм поиска кратчайшего пути с препятствиями
У меня есть коллекция Точек, которая представляет сетку, я ищу алгоритм, который дает мне кратчайшее расстояние между точками А и В. Уловом, являющимся любой точкой (исключая А и В), может быть препятствие, мешающее пути, и таким образом, должен быть в обход. Путь не может двигаться по диагонали.
Для тех, кто хочет решить проблему такого типа, я нашел эти ссылки очень полезными:
http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html
2 ответа
Это отличное место для использования алгоритма поиска A *, эвристического алгоритма поиска, который очень быстро находит оптимальные пути между точками даже при наличии препятствий. Идея состоит в том, чтобы преобразовать сетку в график, где каждая ячейка в сетке является узлом и в котором есть граница между любыми двумя соседними ячейками, которые не закрыты друг от друга. Если у вас есть этот график, ответ, который вы ищете, - это кратчайший путь на графике от начального узла до узла назначения.
Чтобы использовать A*, вам понадобится эвристическая функция, которая "угадывает" расстояние от любой точки сетки до квадрата назначения. Хорошей эвристикой для этого было бы использование манхэттенского расстояния между двумя точками.
Если вы ищете более простой, но все же чрезвычайно эффективный алгоритм поиска кратчайшего пути, рассмотрите алгоритм Дейкстры, который можно рассматривать как более простую версию A *. Это немного медленнее, чем A*, но все еще работает очень быстро и гарантирует оптимальный ответ.
Надеюсь это поможет!
Это простая проблема, которую можно решить с помощью поиска в ширину.
/**
* 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;
}
Я считаю, что данная проблема может быть решена с помощью Breadth First Search(BFS), как упоминалось ранее. Установление постановки проблемы важно. Итак, давайте опишем проблему, а затем перейдем к ее решению.
Описание проблемы:
Вы отвечаете за подготовку недавно купленного участка для нового здания. Участок покрыт траншеями и имеет единственное препятствие, которое необходимо устранить, прежде чем можно будет подготовить фундамент для здания. Робот сноса должен устранить препятствие, прежде чем можно будет продвинуться по зданию. Напишите алгоритм, чтобы определить минимальное расстояние, необходимое роботу-разрушителю для устранения препятствия.
Предположения:
- Лот плоский, за исключением траншей, и может быть представлен в виде двумерной сетки.
- Робот для сноса должен начинаться с верхнего левого угла участка, который всегда плоский и может перемещаться на один блок вверх, вниз, вправо или влево за раз.
- Робот сноса не может войти в траншеи и не может покинуть участок.
- Плоские области представлены как 1, области с траншеями как 0 и препятствием - 9.
Выход:
Вернуть целое число, представляющее минимальное пройденное расстояние для устранения препятствия, иначе вернем -1.
Решение
from collections import defaultdict
from collections import deque
def is_valid(i, j, m, n, matrix, visited):
if i >= 0 and j >= 0 \
and i < m and j < n \
and visited[i][j] is False \
and matrix[i][j] in (1, 9):
return True
return False
def remove_obstacle(matrix, m, n):
queue = deque()
i = 0
j = 0
queue.append((i, j, 0))
visited = [[False for _ in range(n)] for _ in range(m)]
distance_matrix = [[100 for _ in range(n)] for _ in range(m)]
visited[i][j] = True
while queue:
i, j, distance = queue.popleft()
distance_matrix[i][j] = distance
visited[i][j] = True
if matrix[i][j] == 9:
return distance
new_distance = distance + 1
if is_valid(i + 1, j, m, n, matrix, visited):
queue.append((i + 1, j, new_distance))
if is_valid(i - 1, j, m, n, matrix, visited):
queue.append((i - 1, j, new_distance))
if is_valid(i, j + 1, m, n, matrix, visited):
queue.append((i, j + 1, new_distance))
if is_valid(i, j - 1, m, n, matrix, visited):
queue.append((i, j - 1, new_distance))
return -1
if __name__ == '__main__':
m = 5
n = 4
l = [
[1, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 0, 1],
[1, 1, 9, 1],
[0, 0, 1, 1]
]
bfs = remove_obstacle(l, m, n)
assert bfs == 5
m = 3
n = 3
l = [
[1, 0, 0],
[1, 0, 0],
[1, 9, 1]
]
bfs = remove_obstacle(l, m, n)
assert bfs == 3