Jak najít nejkratší cestu z bodu A do bodu B?

Algoritmy Bludiště Jak najít nejkratší cestu z bodu A do bodu B?

Velké množství strategických her (ať už tahových nebo realtime) se odehrává v terénu, který je tvořen dvojrozměrným polem políček, v podstatě čtvercovou sítí. Na té mapě na nějakém políčku A stojí náš hrdina/voják/děl­ník/tank/emzák apod. (nehodící se škrtněte). Nyní odscrolujeme na druhý konec mapy a tam klikneme na jiné políčko (B), kam chceme našeho výše uvedeného jedince poslat. A ten hrdina si teď musí rozmyslet, kudy přesně půjde, aby a) do cíle vůbec došel a b) mu to trvalo co nejkratší dobu.


Předpokládám, že souřadnice postaviček na mapě jsou celočíselné a chodí se vždycky z jednoho políčka na některé z osmi sousedních (rovně i šikmo, jako šachový král). Kdyby se chodilo jenom rovně, celý algoritmus by se hodně zjednodušil (zájemcům doporučuji článek o algoritmu vlny), ale my to teď zkusíme složitěji a obecněji.
Začněme od nejjednodušších případů.

Kdyby byl na celé mapě stejný terén a kdyby se na ní nevyskytovaly žádné překážky (prostě taková veliká rovná louka), stačilo by prostě vyrazit po přímce směrem z A do B. Na to stačí znát trochu geometrie (y=k*x+q) nebo rovnou použít Bresenhamův algoritmus. A nebo ještě primitivnější postup, který mnohdy docela dobře postačí:

while (X<>ciloveX)or(Y<>ciloveY) do
  begin
  if X>ciloveX then dec(X)
   else if X<ciloveX then inc(X);
  if Y>ciloveY then dec(Y)
   else if Y<ciloveY then inc(Y);
    ...nejak zpracuj a uloz souradnice X,Y...
  end;


Kdyby se na tu mapu dalo několik neprůchodných překážek (lesy, hory, rybníky...), mohli by vojáčci postupovat tak, že by nejdřív vyrazili přímo k cíli; když by narazili na překážku, zkusili by ji někudy obejít a kdyby se jim to nepovedlo, zastavili by se a čekali by na další rozkazy. Takhle nějak to fungovalo třeba ve Warcraftu 2.

Konečně se dostáváme k té nejobecnější variantě: terén na mapě není všude stejný. Někde se chodí lépe a rychleji, jinde to jde ztuha. Políčka mapy jsou podle náročnosti terénu číselně ohodnocena: čím obtížnější terén, tím vyšší číslo (například pohodlná dlážděná cesta bude mít toto číslo nízké, zatímco bažina nebo hustý les vysoké; pokud chceme neprůchodnou překážku, použijeme "nekonečně velkou" hodnotu - prakticky stačí např. maximální hodnota, která se vejde do použitého číselného typu). A tohle je případ, který nás zajímá.

Hráli jste někdy Heroes of Might and Magic (je jedno který díl)? V následujícím textu se pokusíme rekonstruovat, co se děje mezi okamžikem, kdy na mapě někam klikneme, a okamžikem, kdy se nám objeví šipkami vyznačená optimální cesta, kudy náš hrdina se svojí armádou půjde.


Krok nultý: nutné definice

Nejdřív si musíme ujasnit, jak vyhodnotíme obtížnost přechodu mezi dvěma políčky. Měla by se za směrodatnou považovat hodnota políčka, ze kterého vycházíme, nebo toho, na které se chystáme šlápnout, nebo nějaký průměr, nebo co vlastně? Odpověď je jednoduchá: to záleží na vás. Doporučuji (ale není to nutné) zvolit takový výraz, který vyjde stejný při cestě z prvního políčka na druhé i z druhého na první, takže se to potom neplete.

Je tu ale ještě jedna záludnost. Pokud se ve čtvercové síti posuneme o pět políček šikmo, urazíme ve skutečnosti větší vzdálenost, než kdybychom šli vodorovně nebo svisle. Přesněji řečeno odmocnina-ze-dvou-krát, tj. 1,4142136krát větší. Což znamená, že při šikmém směru bychom měli obtížnost přechodu ještě násobit odmocninou ze dvou. Protože se ale nechceme pachtit s desetinnými čísly, zkusíme si s nimi trochu pohrát. 1:1.4142136 zaokrouhlíme na 1:1.4, vynásobíme deseti, vyjde 10:14, a nakonec vydělíme dvěma, aby nevycházela tak velká čísla, a vyjde 5:7. Takže při vodorovném nebo svislém pohybu násobíme pěti, při šikmém sedmi. Je jasné, že nám teď vyjdou větší čísla, ale to je jedno. Prostě pak postavičkám interně přidělíme pětkrát víc akčních bodů na chůzi, nebo jak tomu chcete říkat - stejně se většinou zobrazují na různých stupnicích, kde hráč žádná čísla nevidí.

Pro svůj program jsem si nakonec zvolil vzorec:

ObtiznostPrechodu=((ObtiznostPrvnihoPolicka+ObtiznostDruhehoPolicka)*KorekceSmeru) shr 2

kde KorekceSměru je 5 nebo 7 a "shr 2" dá stejný výsledek jako "div 4", ale o pár taktů procesoru dříve, a dělám to proto, aby vycházela co nejmenší čísla a nebyly problémy s přetékáním na velkých mapách.


Krok první: ohodnocení mapy

Kdysi mi tento algoritmus na jednom fóru vysvětloval Lukáš Marek, za což mu tímto ještě jednou děkuji. Později jsem zjistil, že se to jmenuje Dijkstrův algoritmus pro nalezení optimální cesty v ohodnoceném grafu - to jenom kdybyste potřebovali jeho pravé jméno pro účinnější provozování googlovské magie :-).

Nyní si musíme nadefinovat, jak bude vypadat políčko mapy. Dejme tomu, že třeba takhle:

type policko = record
               ObtiznostTerenu:word;
               Stav:byte;
               Hodnota:word;
               {...
               a samozrejme dalsi, pro prakticke pouziti nezbytne
               polozky, jako treba informace o tom, jestli uz je
               policko odkryte, co je na nem za objekt a podobne
               ...}
               end;

ObtiznostTerenu je jasná.
Stav je třístavová proměnná. Může nabývat hodnot "zatím nic", "pracujem na něm" a "hotovo". Z praktických důvodů jsem zvolil typ Byte a hodnoty 0, 1 a 2.
Do položky Hodnota budeme ukládat počet akčních bodů potřebných pro cestu z výchozího políčka (A) sem.

<odbočka>
Když už jsme u definic, pojďme si rovnou definovat celou mapu. Mohli bychom použít obyčejné dvojrozměrné pole typu array[1..výška,1­..šířka] of policko, ale k tomu mám několik výhrad:

  1. Velikost mapy by byla pevně daná při kompilaci a nešla by za chodu programu změnit.
  2. Pokud programujete v reálném módu (např. v Turbo Pascalu), musela by se celá mapa vejít do 64 KB, což je maximální možná velikost proměnné, a nemohla by tedy být moc velká.
  3. Nebylo by to tak zajímavé :-).


Mapu si tedy můžeme definovat třeba jako dvojrozměrné dynamické pole:

{$R-} {vypnutí kontroly rozsahu, aby překladači nevadil rozsah pole 0..0}
type RadekMapy = array[0..0] of policko;
     UkNaRadekMapy = ^RadekMapy;
     SloupecMapy = array[0..0] of UkNaRadekMapy;
     UkNaSloupecMapy = ^SloupecMapy;

Pak deklarujeme proměnné:

var Mapa:UkNaSloupecMapy;
    VyskaMapy,SirkaMapy:word;

Jak se s takovou mapou pracuje? Nejdřív si nechte zadat šířku a výšku. Potom pomocí Getmem alokujte za proměnnou Mapa tak dlouhé pole ukazatelů, kolik chcete mít řádků:

Getmem(mapa,vyskamapy*sizeof(uknaradekmapy));

Potom za každým ukazatelem v tomto poli alokujte pole políček, které budou tvořit řádky mapy:

for i:=0 to vyskamapy-1 do getmem(mapa^[i],sirkamapy*sizeof(policko));

Samozřejmě taky průběžně testujte, jestli nedochází paměť (Maxavail).

K políčkům mapy se přistupuje takto (například):

mapa^[y]^[x].obtiznostterenu:=neco;

Rozdíl oproti obyčejnému poli (mapa[y,x].ob­tiznostterenu) je téměř zanedbatelný :-).
</odbočka>

Takže mapu máme vytvořenou, v ní máme nějaký zajímavý terén (tj. jsou nějak vhodně nastavené položky ObtiznostTerenu u všech políček) a můžeme se konečně pustit do hledání cesty, vlastně do prvního kroku - ohodnocení mapy.

Počáteční inicializace:

  • U všech políček na mapě nastavíme Stav na "zatím nic" a Hodnotu na "nekonečno" (zde použijeme číslo $FFFF, čili 65535).
  • Výchozímu políčku (A) přiřadíme stav "pracujem na něm" a hodnotu 0.


Cyklus, který necháme běžet tak dloho, dokud stav cílového políčka (B) není "hotovo" :

  • Z množiny všech políček ve stavu "pracujem na něm" vybereme to, které má nejmenší Hodnotu (dále Políčko).
  • Stav tohoto Políčka změníme na "hotovo".
  • Pro každého Souseda tohoto Políčka:
    • Pokud je ve stavu "zatím nic", tak mu stav změníme na "pracujem na něm". Pokud je ve stavu "hotovo", neděláme nic a jdeme prohledávat dalšího souseda, jinak pokračujeme:
    • Sečteme Hodnotu Políčka a obtížnost přechodu z Políčka na Souseda.
    • Výsledek porovnáme s Hodnotou Souseda. Pokud je jeho Hodnota větší, nahradíme ji tímto výsledkem.



Na mapě nyní máme více nebo méně šišatou souvislou oblast políček s hodnotou "hotovo", která má přibližný střed v bodě A, rozlézá se do všech stran a nějakým cípem zasahuje až k políčku B. Okraj této oblasti tvoří políčka s hodnotou "pracujem na něm" a zbytek mapy zůstal ve stavu "zatím nic". Pokud byla políčka A a B blízko u sebe, bude tato oblast malá a algoritmus proběhne rychle. Jestli ale od sebe byla hodně daleko a terén na mapě je hodně komplikovaný, oblast bude hodně velká a výpočet potrvá déle.

Hodnota každého políčka ve stavu "hotovo" je rovna nejmenšímu možnému počtu "akčních bodů" potřebných na cestu do něj z políčka A.

Konečnost algoritmu je zajištěna tím, že v každém cyklu jedno políčko přejde do stavu "hotovo". Protože políček na mapě je konečný počet a jedno z nich je cíl B, určitě se k němu jednou dostaneme.

U každého políčka ve stavu "pracujem na něm" se postupně zkouší, jak dlouhá by byla cesta na něj ze sousedících políček, a nechává se tam vždycky délka té nejkratší. Protože pak v cyklu vybíráme vždycky políčko s nejmenší hodnotou, nemůže se stát, že bychom omylem nějaké políčko prohlásili za hotové, i když by třeba do něj ještě existovala nějaká kratší cesta, kterou jsme dosud neprozkoumali.

Z programátorského hlediska tu máme několik samostatných úkolů.
Prvním je nalezení políčka ve stavu "pracujem na něm" s nejmenší Hodnotou. Dá se to udělat tak, že prohledáme celou mapu a u každého políčka zkontrolujeme, jestli se na něm pracuje a jakou má hodnotu. To je ovšem příšerně pomalé (hlavně u větších map). Lepší je udělat si nějaký pomocný seznam (nejlépe pole), do kterého budeme ukládat souřadnice políček ve chvíli, kdy jejich stav změníme ze "zatím nic" na "pracujem na něm". Projít takové pole a najít políčko s nejmenší hodnotou je rychlá záležitost, horší je to s jeho vyřazením. Já jsem to řešil přesunem části pole za mazaným políčkem tak, aby se vzniklá díra zakryla (je na to potřeba nějaká dostatečně rychlá varianta procedury Move). Nová políčka přidávám prostě na konec pole.

Druhým úkolem je ošetření sousedů. Na to je asi nejlepší napsat krátkou procedurku, které jako parametry předáme souřadnice souseda (relativní vzhledem k políčku, jehož je to soused) a korekci na směr (5 nebo 7). V této proceduře je hlavně potřeba ošetřit okraje mapy - nesmíme nic omylem zapsat mimo, protože to by způsobilo naši oblíbenou hláškou "Program provedl nepovolenou operaci a bude ukončen" (popř. v DOSu tvrdý zámrz).


Krok druhý: nalezení cesty v ohodnocené mapě

Tenhle krok bývá ve velkém množství článků, které můžete na síti najít, jaksi opomenut. A přitom bez něj je celá ohodnocená mapa k ničemu :-/.

Předpokládám, že si jednotlivé kroky cesty chceme někam uložit. Pro jednoduchost bude nejlepší předvést si to na spojovém seznamu:

type UkNaKrok=^krok;
Krok = record
       x,y:word;
       dalsi:uknakrok;
       end;

var PrvniKrok:uknakrok;

Z hlediska využití paměti by bylo lepší ukládat cestu do pole, ale takhle to bude názornější. Seznam bude jednosměrný, plnit ho budeme odzadu (tj. nové prvky budeme strkat před začátek). Ukazatel PrvniKrok ukazuje na začátek seznamu - první políčko cesty hned vedle A; poslední prvek seznamu obsahuje souřadnice políčka B.

Začneme v cíli (políčku B). Možná teď někoho napadne, že bychom mohli prostě jít po nejmenších číslech - prozkoumat všechny sousedy a přejít na políčko s nejmenší Hodnotou. Mě to napadlo taky, vyzkoušel jsem to v praxi a zjistil jsem, že tudy ne, přátelé. Špatně se vysvětluje proč, ale takhle se prostě nejkratší cesta nenajde. Fungující algoritmus vypadá následovně:

Inicializace:

  • Nastavíme se na políčko B a jeho souřadnice si uložíme.


Cyklus, který běží tak dlouho, dokud nejsme na políčku A:

  • Projdeme všechny sousední políčka.
  • U každého Souseda si spočítáme součet Hodnoty toho Souseda a obtížnost přechodu na aktuální políčko.
  • Přesuneme se na to sousední políčko, které mělo tento součet nejmenší.
  • Pokud to není A, uložíme si jeho souřadnice.




A jak by to všechno mohlo vypadat v praxi?

Třeba takhle:

procedure NajdiCestu(odkudX,odkudY,kamX,kamY:word);
const VelikostPole=1024; {velikost pomocneho pole pro ukladani policek ve stavu "pracujem na nem"}
type policko2 = record x,y:word; end; {tohle se do toho pole bude ukladat}
var i,j,tmpx,tmpy:integer;    {\ruzne pomocne promenne}
    tmphodnota,tmpindex:word; {/                      }
    p:uknakrok; {pro pridavani kroku cesty do spojoveho seznamu}
    pole:array[0..velikostpole] of policko2; {pomocne pole na ukladani policek}
    konec:word; {index za poslednim prvkem pole (misto, kam se do nej ma vlozit pristi policko)}
{}procedure prober(dx,dy:integer; korekce:word); {procedura pro osetrovani sousedu pri ohodnocovani mapy}
{}var soucet:longint;                            {dx,dy je relativni vzdalenost od policka tmpx,tmpy}
{}Begin
{}{osetreni okraju mapy:}
{}if (tmpx=0)and(dx<0) or
{}   (tmpx=sirkamapy-1)and(dx>0) or
{}   (tmpy=0)and(dy<0) or
{}   (tmpy=vyskamapy-1)and(dy>0) then exit;
{}{vyreseni policka:}
{}with mapa^[tmpy+dy]^[tmpx+dx] do
{}  begin
{}  soucet:=mapa^[tmpy]^[tmpx].hodnota+(korekce*(mapa^[tmpy]^[tmpx].obtiznostterenu+obtiznostterenu)) shr 2;
{}  if stav=0 then begin {policko je ve stavu "zatim nic"}
{}                 stav:=1; {prepis ho na "pracujem na nem"}
{}                 if konec<=velikostpole then {jestli se do pomocneho pole vejde...}
{}                   begin {...vlozime ho tam:}
{}                   with pole[konec] do begin x:=tmpx+dx; y:=tmpy+dy; end;
{}                   inc(konec);
{}                   end;
{}                 if soucet<$FFFF then hodnota:=soucet;
{}                 end
{}   else if (stav=1) {uz bylo ve stavu "pracujem na nem"}
{}           and(hodnota>soucet) then hodnota:=soucet;
{}  end;
{}End;{prober}
{}procedure hledej(dx,dy:integer; korekce:word); {procedura pro prochazeni sousedu aktualniho policka  }
{}var soucet:longint;                            {pri hledani cesty a nalezeni toho s nejmensim souctem}
{}Begin                                          {Hodnoty a obtiznosti prechodu na aktualni policko.   }
{}{okraje:}                                      {dx,dy jsou opet relativni k tmpx,tmpy.               }
{}if (tmpx=0)and(dx<0) or
{}   (tmpx=sirkamapy-1)and(dx>0) or
{}   (tmpy=0)and(dy<0) or
{}   (tmpy=vyskamapy-1)and(dy>0) then exit;
{}with mapa^[tmpy+dy]^[tmpx+dx] do
{}  begin
{}  soucet:=hodnota+(korekce*(mapa^[tmpy]^[tmpx].obtiznostterenu+obtiznostterenu)) shr 2;
{}  if soucet<tmphodnota then begin
{}                            i:=tmpy+dy;
{}                            j:=tmpx+dx;
{}                            tmphodnota:=soucet;
{}                            end;
{}  end;
{}{Stav policka uz v tehle fazi neni potreba kontrolovat, protoze nejmensi}
{}{hodnoty maji vzdycky ta policka, ktera uz jsou ve stavu "hotovo".}
{}End;{hledej}
Begin{najdicestu}
{je dobre nejdriv smazat minulou cestu:}
while prvnikrok<>nil do begin
                        p:=prvnikrok;
                        prvnikrok:=prvnikrok^.dalsi;
                        dispose(p);
                        end;
{ohodnoceni mapy - inicializace:}
for i:=0 to vyskamapy-1 do
 for j:=0 to sirkamapy-1 do with mapa^[i]^[j] do begin
                                                 stav:=0;        {"zatim nic"}
                                                 hodnota:=$FFFF; {"nekonecno"}
                                                 end;
{pocatecni policko:}
with mapa^[odkudy]^[odkudx] do begin
                               stav:=1;   {"pracujem na nem"}
                               hodnota:=0;
                               end;
{rovnou ho taky vlozime do pole:}
with pole[0] do begin x:=odkudx; y:=odkudy; end;
konec:=1;
{ohodnoceni mapy - cyklus:}
while (konec<>0) {pokud pomocne pole neni prazdne (coz by se mohlo stat, pokud by nestacila jeho
                  velikost, nektera policka by se do nej neulozila a pak by nam dosla driv nez
                  bychom se dostali do ciloveho policka)...}
      and(mapa^[kamy]^[kamx].stav<>2) do {...a dokud cil neni ve stavu "hotovo"}
  begin
  {vybereme policko se stavem "pracujem na nem" s nejmensi hodnotou:}
  tmphodnota:=$FFFF;
  for i:=0 to konec-1 do {pro kazde policko ulozene v pomocnem poli}
   with mapa^[pole[i].y]^[pole[i].x] do {najdeme odpovidajici policko na mape}
     if hodnota<tmphodnota then begin
                                tmpx:=pole[i].x;
                                tmpy:=pole[i].y;
                                tmphodnota:=hodnota;
                                tmpindex:=i;
                                end;
  {nyni mame jasno: hledane policko ma souradnice tmpx,tmpy,
   hodnotu tmphodnota a v pomocnem poli se nachazi na pozici tmpindex}
  {stav mu zmenime na "hotovo":}
  mapa^[tmpy]^[tmpx].stav:=2;
  {vyhodime ho z pomocneho pole (pouzijte tu nejrychlejsi variantu Move, jakou doma mate):}
  if tmpindex<konec-1 then move(pole[tmpindex+1],pole[tmpindex],(konec-tmpindex-1)*sizeof(policko2));
  dec(konec);
  {probereme vsechna okolni policka:}
  prober(-1, 0,5);
  prober( 1, 0,5);   {policka ve stavu "hotovo" ignorujeme,                     }
  prober( 0,-1,5);   {policka ve stavu "zatim nic" zmenime na "pracujem na nem",}
  prober( 0, 1,5);   {temto polickum dame takovou hodnotu, ktera je minimem     }
  prober(-1,-1,7);   {z jejich aktualni hodnoty a vypocitane delky cesty do     }
  prober(-1, 1,7);   {tohoto policka (viz drive)                                }
  prober( 1,-1,7);
  prober( 1, 1,7);
  end;
if mapa^[kamy]^[kamx].hodnota=$FFFF then exit; {vidime, ze cesta je prilis dlouha takze koncime
                   (algoritmus by sice dobehl i tak, ale proc to utrpeni zbytecne prodluzovat)}
{nyni je mapa ohodnocena, zbyva nalezt kudy kudy cesticka:}
tmpx:=kamx; tmpy:=kamy; {zacneme v cili}
new(prvnikrok); cil:=prvnikrok;    {cilove policko rovnou ulozime, je to taky soucast cesty}
with prvnikrok^ do begin
                   x:=tmpx;
                   y:=tmpy;
                   dalsi:=nil;
                   end;
j:=tmpx; i:=tmpy; {nutne pro pripad, kdy je cil = start}
 repeat
 tmphodnota:=$FFFF;
 hledej(-1, 0,5);
 hledej( 1, 0,5);    {Ze sousedu policka tmpx,tmpy vybirame takove, ktere  }
 hledej( 0,-1,5);    {ma nejmensi soucet sve hodnoty a hodnoty potrebne na }
 hledej( 0, 1,5);    {prechod z policka tmpx,tmpy.                         }
 hledej(-1,-1,7);
 hledej(-1, 1,7);
 hledej( 1,-1,7);
 hledej( 1, 1,7);
 {nyni je v souradnicich j,i ulozena poloha hledaneho policka}
 tmpx:=j; tmpy:=i; {presuneme se na to policko...}
 {...a toto policko ulozime:}
 if (tmpx<>odkudx)or(tmpy<>odkudy) {pocatecni policko uz ovsem ukladat nechceme, takze tohle jenom pro ty ostatni}
                                   then begin  {vlozime policko na zacatek seznamu}
                                        new(p);
                                        with p^ do begin
                                                   x:=tmpx;
                                                   y:=tmpy;
                                                   dalsi:=prvnikrok;
                                                   end;
                                        prvnikrok:=p;
                                        end;
 until ((tmpx=odkudx)and(tmpy=odkudy)) {opakujeme cyklus, dokud nedojdeme do startu...}
       or(tmphodnota=$FFFF); {...nebo dokud se nedostaneme na policko s hodnotou "nekonecno"
                (coz by se mohlo stat, kdyby cesta byla extremne dlouha. Ovsem pak by se take
                 hodilo vymazat ty dva kroky, ktere jsou touhle dobou ulozene v seznamu)}
End;{najdicestu}


V proceduře nejsou obsaženy kontroly dostupné paměti (Maxavail) při ukládání cesty do paměti, které si ale určitě každý doplní sám (jestli ne, mohl by program umřít na Heap overflow).

Když porovnáme ohodnocování mapy a hledání cesty z hlediska výpočetní náročnosti, zjistíme, že první část trvá mnohonásobně déle, protože se musí pošťourat v daleko větším počtu políček. Ovšem můžeme využít toho, že ohodnocení mapy je závislé pouze na poloze políčka A, ale ne už na poloze B (ta nám udává jenom okamžik, kdy už můžeme s ohodnocováním přestat, což ale nemusíme a můžeme si klidně ohodnotit celou mapu). Takže si teoreticky můžeme proceduru rozdělit, mapu ohodnotit jednou a potom si nechat rychle vyhledávat všechny možné cesty od místa, na kterém stojí náš hrdina, a nakonec ho jednou z nich poslat. A když navíc výpočty provádíme na pozadí (nebo spíš naopak, když výpočty běží v hlavním cyklu programu a veškerá interakce s uživatelem visí na přerušeních), můžeme hráče oblbnout natolik, že pak bude koukat, jak se ta cesta hledá rychle (přitom se hledá poměrně pomalu, ale v okamžiku, kdy o tom neví). Ale stejně by mě zajímalo, jak to machři z New World Computing u Heroes of M. & M. vypiplali, že nalezení cesty přes celou mapu trvalo i na 486/66 MHz zanedbatelné zlomky sekundy - moje procedura se s tím na stejném počítači (na mapě řádově 150x150 políček) dokáže piplat i 10 vteřin. Ale hlavně že funguje :-).


 

  Aktivity (1)

Článek pro vás napsal Mircosoft
Avatar
Autor je amatérský pascalista, assemblerista a bastlíř. Profesionálně psal nebo píše v HLASM, Rexxu, Cobolu, ST, LAD, FBD, PHP, SQL, JS, Basicu a pár dalších jazycích, které kupodivu stále existují a používají se :-).

Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!


 


Miniatura
Všechny články v sekci
Algoritmy pro bludiště
Miniatura
Následující článek
Průchod bludištěm - Theseus

 

 

Komentáře
Zobrazit starší komentáře (10)

Avatar
Lukáš Hruda (Luckin):

Řekl bych, že u kolekce hodně záleží na tom, co na ní má být rychlé. Pokud nepotřebuji měnit velikost nebo pouze občas či výjimečně, je nejlepší pole. Pokud potřebuji často měnit velikost, pak záleží, jestli potřebuji měnit velikost kompletně nebo pouze přidávat/odebírat jednotlivé prvky. Pak záleží na tom, jestli je potřebuji přidávat/odebírat pouze na konci nebo i veprostřed nebo na začátku. Pak záleží, jestli chci aby bylo rychlé spíše měnění velikosti nebo přístup k prvkům. Pak také záleží jestli mi záleží na spotřebě paměti. Prostě všechno záleží :D ...pro každou situaci je potřeba jiná optimalizace.

Tím ale netvrdím, že programátor udělá optimalizaci vždy lépe než kolekce.

Editováno 25.3.2013 15:32
 
Odpovědět 25.3.2013 15:29
Avatar
Kit
Redaktor
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Kit:

Po kolekcích je požadována hlavně robustnost a spolehlivost. Rychlost bývá až na dalších pozicích. Přesto bývají některé kolekce lépe vytuněné, než bych byl schopen nebo ochoten naprogramovat.

Když jsem potřeboval vynásobit 2 matice 5000×5000 prvků, knihovní funkce byla řádově rychlejší, než můj triviální program. Funkci sinus nebo logaritmus se také neobtěžuji programovat a raději použiji funkci z knihovny.

Některé kolekce mají přímo vestavěno binární vyhledávání, o kterém tady byla řeč. Proč je tedy nevyužít?

Odpovědět 25.3.2013 15:46
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek (Satik):

Pokud je tvůj kód pomalejší, než kód nějaké kolekce, pak to není tím, že by byla kolekce tak rychlá, ale tím, že tvůj kód je tak pomalý.

Napsat kód na míru algoritmu tak, aby byl rychlejší, než standardní kolekce moc práce většinou nedá.

Odpovědět 25.3.2013 15:51
:)
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

Právě kvůli robustnosti nemůžou být kolekce rychlejší, než vlastní kód.

Knihovní funkce mohou být rychlejší třeba proto, že využívají HW podpory - ty matice třeba MMX, sin nebo log jsou přímo asm instukce, takže je nesmysl je psát sám, hw to udělá vždy rychleji, než sw.

I když má kolekce binární vyhledávání, pořád je to jenom kolekce - má velkou režii kvůli obecnosti a robustnosti - např. můj vlastní C# string sortovač byl cca řádově rychlejší, než ten vestavěný...

Odpovědět 25.3.2013 15:58
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Záleží taky na jazyce, třeba v C++ je vektor skoro stejně rychlý jako pole, přitom umí i přidávat a odebírat prvky. Ovšem pouze na konec, změna velikosti v jiné části vektoru už je mnohem pomalejší. Tím se dostávám zpět k tomu, že záleží na situaci a na tom, co programátor zrovna potřebuje.

 
Odpovědět 25.3.2013 16:00
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

Jaký používáš algoritmus na násobení matic? Podotýkám, že matice mají rozměr 5000×5000. Mně by se s tím tedy programovat nechtělo.

Odpovědět 25.3.2013 16:00
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

Funkce sinus ani logaritmus nejsou v HW, píší se většinou ve Fortranu. V embedded zařízeních, kde záleží na rychlosti, se obvykle dělají tabulkami.

Odpovědět 25.3.2013 16:04
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

Netuším, takhle velké matice jsem zatím násobit nepotřeboval.

Když sinus ani logaritmus nejsou implementovány v hw, tak k čemu je podle tebe třeba asm instrukce fsin ? To by mě vážně zajímalo :D

Editováno 25.3.2013 16:31
Odpovědět 25.3.2013 16:30
:)
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

No dobrá, instrukce fsin se objevila poprvé v procesorech 387, přehlédl jsem to. Ve 386 ještě nebyla.

Klasickým algoritmem pro násobení matic by to trvalo dost dlouho, proto se to počítá rychlejšími algoritmy, které jsou ale podstatně delší a komplikovanější. Někdo je však přede mnou napsal a jsou fakt kvalitní.

Velké matice se násobí poměrně často zejména v různých simulacích fyzikálních dějů a při prezentaci grafiky. Některé grafické karty to mají vestavěno.

Odpovědět 25.3.2013 16:49
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Mircosoft
Redaktor
Avatar
Mircosoft:

Díky za podnětnou diskusi o kolekcích, maticích a hardwaru, ale už jsme poněkud off-topic.

Účelem článku bylo vysvětlit algoritmus hledání cesty na obecné úrovni, aby si ho každý mohl implementovat a optimalizovat po svém, ne poskytnout hotový, přímo použitelný kód. Jestli chcete napsat něco lepšího, směle do toho ;).

 
Odpovědět 26.3.2013 11:47
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 20. Zobrazit vše