Как ускорить алгоритм A* в больших пространственных масштабах?
Из http://ccl.northwestern.edu/netlogo/models/community/Astardemo1 я написал алгоритм A*, используя узлы в сети для определения путей с наименьшими затратами. Кажется, что код работает, но он слишком медленный, когда я использую его в больших пространственных масштабах. Мой ландшафт имеет протяженность 1000 патчей x 1000 патчей с 1 патчем = 1 пиксель. Даже если я уменьшу его до 400 патчей х 400 патчей с 1 патчем = 1 пиксель, это все равно слишком медленно (я не могу изменить свой ландшафт ниже 400 патчей х 400 патчей). Вот код:
to find-path [ source-node destination-node]
let search-done? false
let search-path []
let current-node 0
set list-open []
set list-closed []
let list-links-with-nodes-in-list-closed []
let list-links []
set list-open lput source-node list-open
while [ search-done? != true]
[
ifelse length list-open != 0
[
set list-open sort-by [[f] of ?1 < [f] of ?2] list-open
set current-node item 0 list-open
set list-open remove-item 0 list-open
set list-closed lput current-node list-closed
ask current-node
[
if parent-node != 0[
set list-links-with-nodes-in-list-closed lput link-with parent-node list-links-with-nodes-in-list-closed
]
ifelse any? (nodes-on neighbors4) with [ (xcor = [ xcor ] of destination-node) and (ycor = [ycor] of destination-node)]
[
set search-done? true
]
[
ask (nodes-on neighbors4) with [ (not member? self list-closed) and (self != parent-node) ]
[
if not member? self list-open and self != source-node and self != destination-node
[
set list-open lput self list-open
set parent-node current-node
set list-links sentence (list-links-with-nodes-in-list-closed) (link-with parent-node)
set g sum (map [ [link-cost] of ? ] list-links)
set h distance destination-node
set f (g + h)
]
]
]
]
]
[
user-message( "A path from the source to the destination does not exist." )
report []
]
]
set search-path lput current-node search-path
let temp first search-path
while [ temp != source-node ]
[
ask temp
[
set color red
]
set search-path lput [parent-node] of temp search-path
set temp [parent-node] of temp
]
set search-path fput destination-node search-path
set search-path reverse search-path
print search-path
end
К сожалению, я не знаю, как ускорить этот код. Есть ли решение для быстрого расчета маршрутов с наименьшей стоимостью в больших пространственных масштабах?
Большое спасибо за вашу помощь.
5 ответов
Было любопытно, поэтому я проверил мой A* и вот мой результат
Лабиринт 1280 х 800 х 32 бит пикселей
- как вы можете видеть, это заняло ~23 мс
- нет многопоточности (AMD 3,2 ГГц)
- 32-битное приложение C++ (BDS2006 Turbo C++ или Borland C++ Builder 2006, если хотите)
- самый медленный путь, который я нашел, был ~44 мс (заполнить почти всю карту)
Я думаю, что это достаточно быстро...
Вот источник для моего класса A*:
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
const DWORD A_star_space=0xFFFFFFFF;
const DWORD A_star_wall =0xFFFFFFFE;
//---------------------------------------------------------------------------
class A_star
{
public:
// variables
DWORD **map; // map[ys][xs]
int xs,ys; // map esolution xs*ys<0xFFFFFFFE !!!
int *px,*py,ps; // output points px[ps],py[ps] after compute()
// internals
A_star();
~A_star();
void _freemap(); // release map memory
void _freepnt(); // release px,py memory
// inteface
void resize(int _xs,int _ys); // realloc map to new resolution
void set(Graphics::TBitmap *bmp,DWORD col_wall); // copy bitmap to map
void get(Graphics::TBitmap *bmp); // draw map to bitmap for debuging
void compute(int x0,int y0,int x1,int y1); // compute path from x0,y0 to x1,y1 output to px,py
};
//---------------------------------------------------------------------------
A_star::A_star() { map=NULL; xs=0; ys=0; px=NULL; py=NULL; ps=0; }
A_star::~A_star() { _freemap(); _freepnt(); }
void A_star::_freemap() { if (map) delete[] map; map=NULL; xs=0; ys=0; }
void A_star::_freepnt() { if (px) delete[] px; px=NULL; if (py) delete[] py; py=NULL; ps=0; }
//---------------------------------------------------------------------------
void A_star::resize(int _xs,int _ys)
{
if ((xs==_xs)&&(ys==_ys)) return;
_freemap();
xs=_xs; ys=_ys;
map=new DWORD*[ys];
for (int y=0;y<ys;y++)
map[y]=new DWORD[xs];
}
//---------------------------------------------------------------------------
void A_star::set(Graphics::TBitmap *bmp,DWORD col_wall)
{
int x,y;
DWORD *p,c;
resize(bmp->Width,bmp->Height);
for (y=0;y<ys;y++)
for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
{
c=A_star_space;
if (p[x]==col_wall) c=A_star_wall;
map[y][x]=c;
}
}
//---------------------------------------------------------------------------
void A_star::get(Graphics::TBitmap *bmp)
{
int x,y;
DWORD *p,c;
bmp->SetSize(xs,ys);
for (y=0;y<ys;y++)
for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
{
c=map[y][x];
if (c==A_star_wall ) c=0x00000000;
else if (c==A_star_space) c=0x00FFFFFF;
else c=((c>>1)&0x7F)+0x00404040;
p[x]=c;
}
}
//---------------------------------------------------------------------------
void A_star::compute(int x0,int y0,int x1,int y1)
{
int x,y,xmin,xmax,ymin,ymax,xx,yy;
DWORD i,j,e;
// [clear previous paths]
for (y=0;y<ys;y++)
for (x=0;x<xs;x++)
if (map[y][x]!=A_star_wall)
map[y][x]=A_star_space;
/*
// [A* no-optimizatims]
xmin=x0; xmax=x0; ymin=y0; ymax=y0;
if (map[y0][x0]==A_star_space)
for (i=0,j=1,e=1,map[y0][x0]=i;(e)&&(map[y1][x1]==A_star_space);i++,j++)
for (e=0,y=ymin;y<=ymax;y++)
for ( x=xmin;x<=xmax;x++)
if (map[y][x]==i)
{
yy=y-1; xx=x; if ((yy>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymin>yy) ymin=yy; }
yy=y+1; xx=x; if ((yy<ys)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymax<yy) ymax=yy; }
yy=y; xx=x-1; if ((xx>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmin>xx) xmin=xx; }
yy=y; xx=x+1; if ((xx<xs)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmax<xx) xmax=xx; }
}
*/
// [A* changed points list]
// init space for 2 points list
_freepnt();
int i0=0,i1=xs*ys,n0=0,n1=0,ii;
px=new int[i1*2];
py=new int[i1*2];
// if start is not on space then stop
if (map[y0][x0]==A_star_space)
{
// init start position to first point list
px[i0+n0]=x0; py[i0+n0]=y0; n0++; map[y0][x0]=0;
// search until hit the destination (swap point lists after each iteration and clear the second one)
for (j=1,e=1;(e)&&(map[y1][x1]==A_star_space);j++,ii=i0,i0=i1,i1=ii,n0=n1,n1=0)
// test neibours of all points in first list and add valid new points to second one
for (e=0,ii=i0;ii<i0+n0;ii++)
{
x=px[ii]; y=py[ii];
yy=y-1; xx=x; if ((yy>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
yy=y+1; xx=x; if ((yy<ys)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
yy=y; xx=x-1; if ((xx>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
yy=y; xx=x+1; if ((xx<xs)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
}
}
// [reconstruct path]
_freepnt();
if (map[y1][x1]==A_star_space) return;
if (map[y1][x1]==A_star_wall) return;
ps=map[y1][x1]+1;
px=new int[ps];
py=new int[ps];
for (i=0;i<ps;i++) { px[i]=x0; py[i]=y0; }
for (x=x1,y=y1,i=ps-1,j=i-1;i>=0;i--,j--)
{
px[i]=x;
py[i]=y;
if ((y> 0)&&(map[y-1][x]==j)) { y--; continue; }
if ((y<ys-1)&&(map[y+1][x]==j)) { y++; continue; }
if ((x> 1)&&(map[y][x-1]==j)) { x--; continue; }
if ((x<xs-0)&&(map[y][x+1]==j)) { x++; continue; }
break;
}
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
Я знаю, что это слишком много кода, но он завершен. Важная вещь в функции члена compute так что ищите [A* changed points list], Неоптимизированный A* (Рем-ред) примерно в 100 раз медленнее.
Код использует растровое изображение из Borland VCL, поэтому, если у вас его нет, игнорируйте функции get,set и переписать их в ваш стиль ввода / вывода gfx. Они просто грузят map от bitmap и рисовать вычисляется map вернуться к bitmap
Использование:
// init
A_star map;
Graphics::TBitmap *maze=new Graphics::TBitmap;
maze->LoadFromFile("maze.bmp");
maze->HandleType=bmDIB;
maze->PixelFormat=pf32bit;
map.set(maze,0); // walls are 0x00000000 (black)
// this can be called repetitive without another init
map.compute(x0,y0,x1,y1); // map.px[map.ps],map.py[map.ps] holds the path
map.get(maze,0); // this is just for drawing the result map back to bitmap for viewing
TL;DR: Включите в свой список узлов (график) только те патчи (или агенты), которые важны!
Один из способов ускорить процесс - не искать в каждом пространстве сетки. A* - это поиск в графике, но кажется, что большинство кодеров просто сбрасывают каждую точку сетки на график. Это не обязательно. Использование разреженного графика поиска вместо поиска каждой точки на экране может ускорить процесс.
Даже в сложном лабиринте вы можете ускориться, включив в график только углы и перекрестки. Не добавляйте сетки для прихожей в открытый список - ищите следующий угол или перекресток. Это где предварительная обработка экрана / сетки / карты для построения графика поиска может сэкономить время позже.
Как вы можете видеть на этом изображении из моей (довольно неэффективной) модели A * на turtlezero.com, наивный подход создает множество дополнительных шагов. Любые открытые узлы, созданные в длинном прямом коридоре, теряются:
Исключив эти шаги из графика, решение может быть найдено в сотни раз быстрее.
Другой метод разреженных графов заключается в использовании графа, который становится все менее плотным по мере удаления от Уокера. То есть, сделайте свое пространство поиска более детализированным около ходунка и разреженным (меньше узлов, менее точным относительно препятствий) подальше от ходунка. Это особенно полезно, когда ходок перемещается по детализированной местности на карте, которая меняется, или к цели, которая движется, и маршрут должен быть пересчитан в любом случае.
Например, при моделировании движения, когда дороги могут стать заблокированными или происходят аварии. Аналогично, симуляция, когда один агент преследует другого агента в изменяющемся ландшафте. В этих случаях только следующие несколько шагов должны быть точно нанесены на график. Общий маршрут к месту назначения может быть приблизительным.
Один простой способ реализовать это - постепенно увеличивать размер шага ходунка по мере увеличения длины пути. Не обращайте внимания на препятствия или проведите быстрое пересечение линии или проверку касательной. Это дает путешественнику общее представление о том, куда идти.
Улучшенный путь может быть пересчитан с каждым шагом или периодически, или когда встречается препятствие.
Это может быть сохранено только в миллисекундах, но лучше использовать миллисекунды в конце пути, который скоро изменится, предоставляя мозги для большего количества ходячих, или лучшую графику, или больше времени с семьей.
Пример разреженного графика различной плотности см. В главе 8 "Расширенное программирование на Java" Дэвида Уоллеса Крофта из APress: http://www.apress.com/game-programming/java/9781590591239
Он использует круговой график увеличения разреженности в демонстрационной игре с алгоритмом *, который управляет вражескими танками.
Другой подход разреженного графа состоит в заполнении графа только путевыми точками интереса. Например, чтобы проложить маршрут по простому кампусу зданий, важны только входы, выходы и углы. Точки вдоль стороны здания или в открытом пространстве между ними не важны и могут быть опущены в графе поиска. Для более подробной карты может потребоваться больше точек пути - например, круг узлов вокруг фонтана или статуи или пересечение мощеных дорожек.
Вот диаграмма, показывающая пути между путевыми точками.
Это было сгенерировано мной на сайте turtlezero.com по модели графов зданий кампуса: http://www.turtlezero.com/models/view.php?model=campus-buildings-path-graph
Он использует простые запросы исправлений netlogo для поиска точек интереса, например, снаружи и внутри углов. Я уверен, что несколько более сложный набор запросов может иметь дело с такими вещами, как диагональные стены. Но даже без такой необычной дальнейшей оптимизации пространство поиска A * будет сокращено на порядки.
К сожалению, так как теперь Java 1.7 не допускает неподписанные апплеты, вы не можете запустить модель на веб-странице без изменения настроек безопасности Java. Извини за это. Но прочитайте описание.
A* - это две эвристики; Алгоритм Джикстры и жадный поиск. Алгоритм Джикстры ищет кратчайший путь. Жадный поиск ищет самый дешевый путь. Алгоритм Джикстры чрезвычайно медленный, потому что он не рискует. Умножьте эффект Жадного Поиска, чтобы пойти на больший риск.
Например, если A* = Djikstra + Greedyтогда быстрее A* = Djikstra + 1.1 * Greedy, Независимо от того, насколько вы оптимизируете свой доступ к памяти или свой код, это не исправит плохой подход к решению проблемы. Сделайте свой A* более жадным, и он будет сосредоточен на поиске решения, а не на идеальном решении.
НОТА:
Greedy Search = distance from end
Djikstra's Algorithm = distance from start
в стандарте A* он будет искать идеальные решения, пока не достигнет препятствия. Это видео показывает различные эвристики поиска в действии; обратите внимание, насколько быстрым может быть жадный поиск (переходите к 2:22 для A*, 4:40 для Greedy). У меня самого была похожая проблема, когда я впервые начал с A*, и измененный план A*, который я описал выше, улучшил мою производительность в геометрической прогрессии. Мораль истории; используйте правильный инструмент для работы.
Если вы планируете многократно использовать одну и ту же карту, некоторая форма предварительной обработки обычно оптимальна. По сути, вы определяете кратчайшие расстояния между некоторыми общими точками и добавляете их в графики в виде ребер, что обычно помогает быстрее найти решение. Хотя его сложнее реализовать.
Например, вы можете сделать это для всех автомагистралей на карте Великобритании, поэтому алгоритм поиска должен только найти маршрут до автомагистрали и от развязки автомагистралей до места назначения.
Я не могу сказать, какова может быть истинная причина наблюдаемой медлительности. Возможно, это просто из-за недостатков в эффективности, наложенных языком программирования под рукой. Как вы измерили свою производительность? Как мы можем воспроизвести это?
Кроме того, используемая эвристика (метрика расстояния) оказывает большое влияние на объем исследования, которое проводится для поиска оптимального пути, и, следовательно, также влияет на воспринимаемую эффективность алгоритма.
В теории вы должны использовать допустимую эвристику, то есть такую, которая никогда не переоценивает оставшееся расстояние. На практике, в зависимости от сложности лабиринта, консервативный выбор двухмерного лабиринта, такого как расстояние до Манхэттена, может значительно недооценить оставшееся расстояние. Поэтому много исследований делается в областях лабиринта, далеко от цели. Это приводит к степени исследования, которая больше напоминает исследование полного поиска (например, поиск по ширине), чем то, что можно ожидать от алгоритма информированного поиска.
Это может быть что-то, чтобы посмотреть.
Также взгляните на мой ответ здесь:
Там я сравнил различные эвристики, используемые с базовым алгоритмом A-Star, и визуализировал результаты. Вы можете найти это интересным.