Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Хвильовий алгоритм (Алгоритм Лі) — алгоритм, що дозволяє знайти мінімальний шлях в графі з ребрами одиничної довжини. Заснований на алгоритмі пошуку в ширину. Застосовується для знаходження найкоротшого шляху в графі, в загальному випадку знаходить лише його довжину.
Суть алгоритму
На двовимірній карті (матриці), що складається з «прохідних» і «непрохідних» комірок, позначена комірка старту і комірка фінішу. Мета алгоритму - прокласти найкоротший шлях від комірки старту до комірки фінішу, якщо це, звичайно, можливо. Від старту у всі напрями поширюється хвиля, причому кожна пройдена хвилею комірка позначається як «пройдена». Хвиля, у свою чергу, не може проходити через комірки помічені як «пройдені» або «непрохідні». Хвиля рухається, поки не досягне точки фінішу або поки не залишиться непройдених комірок. Якщо хвиля пройшла всі доступні комірки, але так і не досягла точки фінішу, значить, шлях від старту до фінішу прокласти неможливо. Після досягнення хвилею фінішу, прокладається шлях в зворотному напрямі (від фінішу до старту) і зберігається в масиві.
Різновиди
Заповнення по матриці в 4 напрямках (околиця фон Неймана), він же алгоритм Лі — точніший, але менш швидкий метод.
i+1 i+1 i i+1 i+1
Заповнення по матриці в 8 напрямків (околиця Мура) — більш швидкий, але менш точний метод. Шлях по діагоналі приблизно в 1.4 рази довший, ніж по горизонталі й вертикалі, саме тому комірки, розташовані по діагоналі, мають коефіцієнт +3, а по горизонталі й вертикалі — коефіцієнт +2.
і+3 і+2 i+3 i+2 i i+2 і+3 i+2 і+3
Існує також алгоритм A* (A-star) — направлений хвильовий алгоритм.
Практичне застосування
Хвильовий алгоритм - один з основних при автоматизованому трасуванні (розводці) друкованих плат. Він має досить велику кількість різноманітних модифікацій, що дозволяють покращити знайдений розв'язок з точки зору затрат пам'яті та швидкодії. Також одне з характерних застосувань хвильового алгоритму — пошук найкоротшої відстані на карті в стратегічних комп'ютерних іграх.
Опис алгоритму
Алгоритм складається з кількох етапів, серед яких основними можна виділити наступні: підготовчий етап, етап поширення хвилі та етап побудови шляху.
На підготовчому етапі проводиться аналіз комірок, що присутні на карті, визначаються зайняті комірки. Решта комірок позначаються як вільні, їм присвоюється вага "0". В лічильник кроків К записується 1.
Етап поширення хвилі полягає у знаходженні точки фінішу шляхом перебору сусідніх комірок та присвоєння їм відповідної ваги. В першу чергу перевіряються всі комірки, суміжні з початковою. Якщо комірка має вагу "0", їй присвоюється значення з лічильника кроків. Комірки з іншою вагою (заповнені на попередніх кроках), а також комірки, відмічені як зайняті, залишаються без змін. Якщо одна з комірок є точкою фінішу, алгоритм переходить на наступний етап – побудову шляху. В іншому випадку лічильник кроків збільшується на одиницю і описаний для початкової точки алгоритм повторюється для всіх точок з вагою К-1. Якщо кінцева точка не знайдена, і для всіх точок з вагою К-1 в околі не лишилось вільних комірок, то вважається, що шлях не існує.
На етапі побудови шляху (згортання хвилі) починаємо рух з кінцевої точки. Для цієї точки обирається комірка з її околу (вага цієї комірки буде К). Тоді для цієї комірки знову шукається суміжна з вагою К-1. Таким чином продовжується доти, поки не знайдено комірку з вагою 1, в околі якої знаходиться початкова точка (вага початкової точки 0). Таким чином маємо побудований шлях, який також відносить до множини шляхів мінімальної довжини.
Приклад реалізації
Також однією з задач, з якими легко справляється хвильовий алгоритм є пошук виходу з лабіринту. Нижче наведено приклад реалізації алгоритму пошуку виходу з лабіринту на мові С++.[]
#include "conio.h" // Для функції getch() #include <string.h> struct screen_point{ unsigned char chr; unsigned char attr; // Це все що потрібно для виводу }; // на екран. typedef struct screen_point screen_line[80]; screen_line * scr; char movecost[10][10]={ {0,0,0,0,0,0,0,0,0,0}, {0,1,6,6,6,6,6,1,1,0}, {0,1,0,0,0,0,6,0,0,0}, {0,1,0,1,1,1,1,1,1,0}, {0,1,0,1,1,0,0,0,1,0}, // Це і є лабіринт {0,1,0,1,0,0,1,0,1,0}, // 0 - стіна {0,1,0,1,0,1,1,0,1,0}, // будь-яке інше число - {0,1,0,0,0,0,0,0,1,0}, // ступінь прохідності {0,1,8,1,1,1,1,1,1,0}, // 1 - найкраща прохідність {0,0,0,0,0,0,0,0,0,0} }; unsigned char fillmap[10][10]; // Розмір рівний розміру лабіринту!!! // якщо шлях може бути довшим за // 255 варто замінити byte->word struct{ signed char x,y; // Координати в лабіринті }buf[256]; // Чим більший лабіринт, тим більшим повинен // бути цей масив unsigned char bufp,bufe; // Індекси в buf int sx,sy,tx,ty; // Початкові та кінцеві координати шляху /* Ця частина займається виводом на екран і не має жодного відношення до алгоритму */ void clrscr(){ // Очистити екран int i; for(i=0;i<80*25;i++)((short*)scr)[i]=0x0720; } // Надрукувати рядок str в координатах (x,y) кольором attr void writestr(int x,int y,char str[],char attr){ int i; for(i=0;str[i]!=0;i++,x++){scr[y][x].chr=str[i];scr[y][x].attr=attr;} } // Малюємо початковий малюнок лабіринту void draw_maze(){ int i,j; for(j=0;j<10;j++)for(i=0;i<10;i++){ scr[j][i*2 ].attr=16*(7-movecost[j][i])+7+8*((i+j)&1); scr[j][i*2+1].attr=16*(7-movecost[j][i])+7+8*((i+j)&1); } scr[sy][sx*2].chr='[';scr[sy][sx*2+1].chr=']'; scr[ty][tx*2].chr='<';scr[ty][tx*2+1].chr='>'; scr[1][40].attr=16*(7-1);writestr(45,1,"Пусте місце",7); scr[3][40].attr=16*(7-0);writestr(45,3,"Стіна",7); scr[5][40].attr=16*(7-6);writestr(45,5,"Болото",7); writestr(40,7,"[] Початкова точка",7); writestr(40,9,"<> Ціль шляху",7); } /* Реалізація самого алгоритму */ /* Ця функція перевіряє чи є запропонований шлях в точку фінішу більш коротким, ніж знайдені раніше, і якщо так, то запам'ятовує точку в buf. */ void push(int x,int y,int n){ if(fillmap[y][x]<=n)return; // Якщо новий шлях не коротший, його відкидаємо fillmap[y][x]=n; // Запам'ятовуємо нову довжину шляху buf[bufe].x=x; buf[bufe].y=y; // Запам'ятовуємо точку bufe++; scr[y][x*2 ].chr=n/10+48; // Промальовка та очікування натиснення клавіші scr[y][x*2+1].chr=(n%10)+48; getch(); // } /* Тут береться чергова точка з buf і повертається 1, якщо buf пустий, повертається 0 */ int pop(int *x,int *y){ if(bufp==bufe)return 0; *x=buf[bufp].x; *y=buf[bufp].y; bufp++; return 1; } void fill(int sx,int sy,int tx,int ty){ int x,y,n,t; // Спочатку fillmap заповнюється max значенням _fmemset(fillmap,0xFF,sizeof(fillmap)); bufp=bufe=0; // Обнуляємо буфери push(sx,sy,0); while(pop(&x,&y)){ // Цикл виконується, доки є точки в буфері if((x==tx)&&(y==ty)){ writestr(0,20,"Знайдено шлях довжиною ",15); scr[20][19].chr=n/10+48; scr[20][20].chr=(n%10)+48; break; } // n рівне довжині шляху до будь-якої сусідньої комірки n=fillmap[y][x]+movecost[y][x]; // Перебір 4-х сусідніх комірок if(movecost[y+1][x ])push(x ,y+1,n); if(movecost[y-1][x ])push(x ,y-1,n); if(movecost[y ][x+1])push(x+1,y ,n); if(movecost[y ][x-1])push(x-1,y ,n); } // Якщо перебрано всю карту і не знайдено жодного шляху if(fillmap[ty][tx]==0xFF){ writestr(0,20,"Шляху не існує!!!",15); return; } else writestr(0,20,"Заливку завершено. Пройдемо по шляху!!!",15); x=tx;y=ty;n=0xFF; // Ми почали заливку з (sx,sy), отже // по шляху доведеться йти з (tx,ty), у зворотньому напрямі while((x!=sx)||(y!=sy)){ // Доки не прийшли в (sx,sy) scr[y][x*2].attr=2*16;scr[y][x*2+1].attr=2*16; // Малювання // Шукається сусідня комірка, if(fillmap[y+1][x ]<n){tx=x ;ty=y+1;t=fillmap[y+1][x ];} // що містить if(fillmap[y-1][x ]<n){tx=x ;ty=y-1;t=fillmap[y-1][x ];} // мінімальне значення if(fillmap[y ][x+1]<n){tx=x+1;ty=y ;t=fillmap[y ][x+1];} if(fillmap[y ][x-1]<n){tx=x-1;ty=y ;t=fillmap[y ][x-1];} x=tx;y=ty;n=t; // Переходимо на знайдену комірку getch(); // Очікуємо натиснення клавіші } } void main(){ int i; sx=1;sy=1; // Задання початкової точки tx=3;ty=3; // Задання цілі шляху scr=(screen_line*)0xB8000; clrscr(); draw_maze(); getch(); fill(sx,sy,tx,ty); // Виклик функції пошуку шляху } Див. також
Література
- Wai-Kai Chen. The circuits and filters handbook. — 2, 2003. — 2961 с. — .
- Frank Rubin. The Lee path connection algorithm. — IEEE Transactions on Computers, 1974.
Посилання
- Доведення коректності алгоритму [ 7 грудня 2010 у Wayback Machine.](рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Hvilovij algoritm Algoritm Li algoritm sho dozvolyaye znajti minimalnij shlyah v grafi z rebrami odinichnoyi dovzhini Zasnovanij na algoritmi poshuku v shirinu Zastosovuyetsya dlya znahodzhennya najkorotshogo shlyahu v grafi v zagalnomu vipadku znahodit lishe jogo dovzhinu Rezultat roboti algoritmu ortogonalnij shlyah Rezultat roboti algoritmu ortogonalno diagonalnij shlyah Sut algoritmuNa dvovimirnij karti matrici sho skladayetsya z prohidnih i neprohidnih komirok poznachena komirka startu i komirka finishu Meta algoritmu proklasti najkorotshij shlyah vid komirki startu do komirki finishu yaksho ce zvichajno mozhlivo Vid startu u vsi napryami poshiryuyetsya hvilya prichomu kozhna projdena hvileyu komirka poznachayetsya yak projdena Hvilya u svoyu chergu ne mozhe prohoditi cherez komirki pomicheni yak projdeni abo neprohidni Hvilya ruhayetsya poki ne dosyagne tochki finishu abo poki ne zalishitsya neprojdenih komirok Yaksho hvilya projshla vsi dostupni komirki ale tak i ne dosyagla tochki finishu znachit shlyah vid startu do finishu proklasti nemozhlivo Pislya dosyagnennya hvileyu finishu prokladayetsya shlyah v zvorotnomu napryami vid finishu do startu i zberigayetsya v masivi RiznovidiZapovnennya po matrici v 4 napryamkah okolicya fon Nejmana vin zhe algoritm Li tochnishij ale mensh shvidkij metod i 1 i 1 i i 1 i 1 Zapovnennya po matrici v 8 napryamkiv okolicya Mura bilsh shvidkij ale mensh tochnij metod Shlyah po diagonali priblizno v 1 4 razi dovshij nizh po gorizontali j vertikali same tomu komirki roztashovani po diagonali mayut koeficiyent 3 a po gorizontali j vertikali koeficiyent 2 i 3 i 2 i 3 i 2 i i 2 i 3 i 2 i 3 Isnuye takozh algoritm A A star napravlenij hvilovij algoritm Praktichne zastosuvannyaHvilovij algoritm odin z osnovnih pri avtomatizovanomu trasuvanni rozvodci drukovanih plat Vin maye dosit veliku kilkist riznomanitnih modifikacij sho dozvolyayut pokrashiti znajdenij rozv yazok z tochki zoru zatrat pam yati ta shvidkodiyi Takozh odne z harakternih zastosuvan hvilovogo algoritmu poshuk najkorotshoyi vidstani na karti v strategichnih komp yuternih igrah Opis algoritmuAlgoritm skladayetsya z kilkoh etapiv sered yakih osnovnimi mozhna vidiliti nastupni pidgotovchij etap etap poshirennya hvili ta etap pobudovi shlyahu Na pidgotovchomu etapi provoditsya analiz komirok sho prisutni na karti viznachayutsya zajnyati komirki Reshta komirok poznachayutsya yak vilni yim prisvoyuyetsya vaga 0 V lichilnik krokiv K zapisuyetsya 1 Etap poshirennya hvili polyagaye u znahodzhenni tochki finishu shlyahom pereboru susidnih komirok ta prisvoyennya yim vidpovidnoyi vagi V pershu chergu pereviryayutsya vsi komirki sumizhni z pochatkovoyu Yaksho komirka maye vagu 0 yij prisvoyuyetsya znachennya z lichilnika krokiv Komirki z inshoyu vagoyu zapovneni na poperednih krokah a takozh komirki vidmicheni yak zajnyati zalishayutsya bez zmin Yaksho odna z komirok ye tochkoyu finishu algoritm perehodit na nastupnij etap pobudovu shlyahu V inshomu vipadku lichilnik krokiv zbilshuyetsya na odinicyu i opisanij dlya pochatkovoyi tochki algoritm povtoryuyetsya dlya vsih tochok z vagoyu K 1 Yaksho kinceva tochka ne znajdena i dlya vsih tochok z vagoyu K 1 v okoli ne lishilos vilnih komirok to vvazhayetsya sho shlyah ne isnuye Na etapi pobudovi shlyahu zgortannya hvili pochinayemo ruh z kincevoyi tochki Dlya ciyeyi tochki obirayetsya komirka z yiyi okolu vaga ciyeyi komirki bude K Todi dlya ciyeyi komirki znovu shukayetsya sumizhna z vagoyu K 1 Takim chinom prodovzhuyetsya doti poki ne znajdeno komirku z vagoyu 1 v okoli yakoyi znahoditsya pochatkova tochka vaga pochatkovoyi tochki 0 Takim chinom mayemo pobudovanij shlyah yakij takozh vidnosit do mnozhini shlyahiv minimalnoyi dovzhini Priklad realizaciyiTakozh odniyeyu z zadach z yakimi legko spravlyayetsya hvilovij algoritm ye poshuk vihodu z labirintu Nizhche navedeno priklad realizaciyi algoritmu poshuku vihodu z labirintu na movi S dzherelo include conio h Dlya funkciyi getch include lt string h gt struct screen point unsigned char chr unsigned char attr Ce vse sho potribno dlya vivodu na ekran typedef struct screen point screen line 80 screen line scr char movecost 10 10 0 0 0 0 0 0 0 0 0 0 0 1 6 6 6 6 6 1 1 0 0 1 0 0 0 0 6 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 Ce i ye labirint 0 1 0 1 0 0 1 0 1 0 0 stina 0 1 0 1 0 1 1 0 1 0 bud yake inshe chislo 0 1 0 0 0 0 0 0 1 0 stupin prohidnosti 0 1 8 1 1 1 1 1 1 0 1 najkrasha prohidnist 0 0 0 0 0 0 0 0 0 0 unsigned char fillmap 10 10 Rozmir rivnij rozmiru labirintu yaksho shlyah mozhe buti dovshim za 255 varto zaminiti byte gt word struct signed char x y Koordinati v labirinti buf 256 Chim bilshij labirint tim bilshim povinen buti cej masiv unsigned char bufp bufe Indeksi v buf int sx sy tx ty Pochatkovi ta kincevi koordinati shlyahu Cya chastina zajmayetsya vivodom na ekran i ne maye zhodnogo vidnoshennya do algoritmu void clrscr Ochistiti ekran int i for i 0 i lt 80 25 i short scr i 0x0720 Nadrukuvati ryadok str v koordinatah x y kolorom attr void writestr int x int y char str char attr int i for i 0 str i 0 i x scr y x chr str i scr y x attr attr Malyuyemo pochatkovij malyunok labirintu void draw maze int i j for j 0 j lt 10 j for i 0 i lt 10 i scr j i 2 attr 16 7 movecost j i 7 8 i j amp 1 scr j i 2 1 attr 16 7 movecost j i 7 8 i j amp 1 scr sy sx 2 chr scr sy sx 2 1 chr scr ty tx 2 chr lt scr ty tx 2 1 chr gt scr 1 40 attr 16 7 1 writestr 45 1 Puste misce 7 scr 3 40 attr 16 7 0 writestr 45 3 Stina 7 scr 5 40 attr 16 7 6 writestr 45 5 Boloto 7 writestr 40 7 Pochatkova tochka 7 writestr 40 9 lt gt Cil shlyahu 7 Realizaciya samogo algoritmu Cya funkciya pereviryaye chi ye zaproponovanij shlyah v tochku finishu bilsh korotkim nizh znajdeni ranishe i yaksho tak to zapam yatovuye tochku v buf void push int x int y int n if fillmap y x lt n return Yaksho novij shlyah ne korotshij jogo vidkidayemo fillmap y x n Zapam yatovuyemo novu dovzhinu shlyahu buf bufe x x buf bufe y y Zapam yatovuyemo tochku bufe scr y x 2 chr n 10 48 Promalovka ta ochikuvannya natisnennya klavishi scr y x 2 1 chr n 10 48 getch Tut beretsya chergova tochka z buf i povertayetsya 1 yaksho buf pustij povertayetsya 0 int pop int x int y if bufp bufe return 0 x buf bufp x y buf bufp y bufp return 1 void fill int sx int sy int tx int ty int x y n t Spochatku fillmap zapovnyuyetsya max znachennyam fmemset fillmap 0xFF sizeof fillmap bufp bufe 0 Obnulyayemo buferi push sx sy 0 while pop amp x amp y Cikl vikonuyetsya doki ye tochki v buferi if x tx amp amp y ty writestr 0 20 Znajdeno shlyah dovzhinoyu 15 scr 20 19 chr n 10 48 scr 20 20 chr n 10 48 break n rivne dovzhini shlyahu do bud yakoyi susidnoyi komirki n fillmap y x movecost y x Perebir 4 h susidnih komirok if movecost y 1 x push x y 1 n if movecost y 1 x push x y 1 n if movecost y x 1 push x 1 y n if movecost y x 1 push x 1 y n Yaksho perebrano vsyu kartu i ne znajdeno zhodnogo shlyahu if fillmap ty tx 0xFF writestr 0 20 Shlyahu ne isnuye 15 return else writestr 0 20 Zalivku zaversheno Projdemo po shlyahu 15 x tx y ty n 0xFF Mi pochali zalivku z sx sy otzhe po shlyahu dovedetsya jti z tx ty u zvorotnomu napryami while x sx y sy Doki ne prijshli v sx sy scr y x 2 attr 2 16 scr y x 2 1 attr 2 16 Malyuvannya Shukayetsya susidnya komirka if fillmap y 1 x lt n tx x ty y 1 t fillmap y 1 x sho mistit if fillmap y 1 x lt n tx x ty y 1 t fillmap y 1 x minimalne znachennya if fillmap y x 1 lt n tx x 1 ty y t fillmap y x 1 if fillmap y x 1 lt n tx x 1 ty y t fillmap y x 1 x tx y ty n t Perehodimo na znajdenu komirku getch Ochikuyemo natisnennya klavishi void main int i sx 1 sy 1 Zadannya pochatkovoyi tochki tx 3 ty 3 Zadannya cili shlyahu scr screen line 0xB8000 clrscr draw maze getch fill sx sy tx ty Viklik funkciyi poshuku shlyahu Div takozhAlgoritm kanalnogo trasuvannyaLiteraturaWai Kai Chen The circuits and filters handbook 2 2003 2961 s ISBN 0849309123 Frank Rubin The Lee path connection algorithm IEEE Transactions on Computers 1974 PosilannyaDovedennya korektnosti algoritmu 7 grudnya 2010 u Wayback Machine ros