Алгоритъмът на Лий, обяснен с примери

Алгоритъмът на Лий е едно от възможните решения за проблеми с маршрута в лабиринта. Той винаги дава оптимално решение, ако такова съществува, но е бавно и изисква голяма памет за плътно оформление.

Разбиране как работи

Алгоритъмът е breadth-firstбазиран алгоритъм, който използва queuesза съхраняване на стъпките. Обикновено използва следните стъпки:

  1. Изберете начална точка и я добавете към опашката.
  2. Добавете валидните съседни клетки към опашката.
  3. Премахнете позицията, на която сте, от опашката и продължете към следващия елемент.
  4. Повторете стъпки 2 и 3, докато опашката не се изпразни.

Една от ключовите концепции за разбиране е, че breadth-firstтърсенията се разширяват, докато depth-firstтърсенията се задълбочават.

Използвайки примера на алгоритъм за решаване на лабиринт, depth-firstподходът ще изпробва всеки възможен път един по един, докато или стигне до задънена улица или до финала и върне резултата. Въпреки това пътят, който връща, може да не е най-ефективен, а просто първият пълен път до финала, който алгоритъмът е успял да намери.

А breadth-firstтърсене вместо това ще излязат на всеки отворено пространство в непосредствена близост до началната точка, а след това се търсят други възможни открити пространства. Той ще продължи да прави това, излизайки слой по слой и опитвайки всеки възможен път в тандем, докато намери крайната точка. Тъй като изпробвате всеки път едновременно, можете да сте сигурни, че първият пълен път от началото до края е и най-краткият.

Изпълнение

C ++ има опашката, вече внедрена в библиотеката, но ако използвате нещо друго, можете да внедрите своя собствена версия на опашката.

C ++ код:

int dl[] = {-1, 0, 1, 0}; // these arrays will help you travel in the 4 directions more easily int dc[] = {0, 1, 0, -1}; queue X, Y; // the queues used to get the positions in the matrix X.push(start_x); //initialize the queues with the start position Y.push(start_y); void lee() { int x, y, xx, yy; while(!X.empty()) // while there are still positions in the queue { x = X.front(); // set the current position y = Y.front(); for(int i = 0; i < 4; i++) { xx = x + dl[i]; // travel in an adiacent cell from the current position yy = y + dc[i]; if('position is valid') //here you should insert whatever conditions should apply for your position (xx, yy) { X.push(xx); // add the position to the queue Y.push(yy); mat[xx][yy] = -1; // you usually mark that you have been to this position in the matrix } } X.pop(); // eliminate the first position, as you have no more use for it Y.pop(); } }