Vysoká škola finanční a správní, o.p.s.
Programování Studijní text pro posluchače 1. ročníku oboru Aplikovaná informatika
Pavel Töpfer
Praha 2014
Obsah 1. Úvod ....................................................................................................................................... 3 2. Modulární programování........................................................................................................ 4 3. Modul CRT ............................................................................................................................ 8 4. Dynamicky alokované proměnné ......................................................................................... 10 5. Lineární spojové seznamy .................................................................................................... 14 6. Rekurze................................................................................................................................. 24 7. Prohledávání do hloubky a do šířky ..................................................................................... 30 8. Metoda „Rozděl a panuj“ ..................................................................................................... 45 9. Stromové struktury ............................................................................................................... 52 10. Aritmetické výrazy ............................................................................................................. 63 11. Metody ukládání a vyhledávání dat ................................................................................... 71 12. Grafové algoritmy .............................................................................................................. 78
2
1. Úvod Tento text bezprostředně navazuje na obdobný studijní text určený pro předmět Úvod do programování. Opět se nejedná o ucelenou systematickou učebnici, najdete zde rozšířené a doplněné prezentace k přednáškám z předmětu Programování a ukázkové programy s doprovodným vysvětlením, jakým způsobem jsou programy navrženy a jak fungují. Práce se studijním textem vám v žádném případě nemá a nemůže nahradit účast na přednáškách a vlastní aktivní práci na cvičeních, může vám však dobře pomoci při průběžném studiu a při přípravě ke zkoušce.
Začneme shrnutím, čím vším se budeme v předmětu Programování zabývat. Navážeme na výuku předmětu Úvod do programování a budeme předpokládat, že čtenář má již dostatečně dobře zvládnuto učivo tohoto předmětu. Nadále budeme při výkladu používat programovací jazyk Pascal, který již znáte z předmětu Úvod do programování a který se dobře hodí pro zápis algoritmů. Jelikož Pascal není náš cílový programovací jazyk, ale pouze prostředek pro ovládnutí základů algoritmizace a programování, nebudeme si již příliš rozšiřovat jeho znalosti. Z technických prostředků programovacího jazyka doplníme pouze prostředky pro realizaci modulárního programování a ukazatele a dynamicky alokované proměnné, s jejichž pomocí se naučíme pracovat s dynamickými datovými strukturami. Těžištěm výuky bude rozšíření a obohacení znalostí v oblasti algoritmů, datových struktur a programovacích technik užívaných při návrhu a vývoji programů. Naučíme se zejména následující: - lineární spojové seznamy a jejich využití - princip rekurze, hlavní druhy rekurzivních algoritmů - prohledávání do hloubky a do šířky, možnosti realizace - metody zvyšování efektivity backtrackingu – ořezávání, heuristiky - metoda „Rozděl a panuj“, quicksort - stromové struktury a jejich použití - reprezentace aritmetických výrazů, aritmetické notace, vyhodnocování výrazů - binární vyhledávací strom, vyvažování - hešování - přihrádkové třídění - algoritmy nalezení k-tého nejmenšího prvku - reprezentace grafu, implementace základních grafových algoritmů
3
2. Modulární programování U větších programových celků může být zdrojový text programu tvořen více soubory (moduly), z nichž právě jeden obsahuje hlavní program (tam začíná a končí výpočet). Ostatní moduly jsou „knihovny“ proměnných, konstant, typů, procedur a funkcí. Po připojení modulu k programu může program využívat prostředky deklarované v připojeném modulu. Rovněž modul může využívat prostředky deklarované v jiném modulu. Výhody a využití: - dekompozice rozsáhlého zdrojového textu do více modulů podle logického významu, některé moduly mohou obsahovat jednotlivé části řešení konkrétního problému, jiné obsahují obecné prostředky a nástroje (vede to k větší přehlednosti zdrojového kódu) - využití při dělbě práce v programátorském týmu - moduly jsou samostatně kompilovatelné - pro použití modulu v programu nepotřebujeme mít jeho zdrojový text, stačí nám přeložený modul (výhodné z obchodního hlediska) - moduly jsou opakovaně využitelné (ve více programech). Realizace v Turbo Pascalu: - v terminologii TP „program“ (hlavní program) + „unit“ (ostatní moduly) - česká terminologie: někdy „jednotka“, slangově „unita“ - každá unita v samostatném souboru, edituje se a překládá v běžném editačním okně IDE, ukládá se do souboru s příponou .PAS - překladem unity vznikne stejnojmenný soubor s příponou .TPU (Turbo Pascal Unit) = přeložený kód procedur a funkcí jako v .EXE + informace o exportovaných identifikátorech a jejich významu Použití unity v programu: klauzule uses hned za hlavičkou programu, před deklaracemi program Program_s_unitou; uses ALFA, ABC; var X: integer;
Standardní unity v Turbo Pascalu - jsou součástí instalace překladače: CRT – textová obrazovka, klávesnice, zvuk DOS – spolupráce programu s operačním systémem (např. GetTime, GetDate, práce se soubory, s přerušením) GRAPH – prostředky na kreslení na obrazovce v grafickém režimu SYSTEM – tzv. standardní procedury a funkce (např. read, write, assign, sin, abs, chr, val, odd, eof, exit) STRINGS – nulou ukončené řetězce (jako v C a ve Windows) WinCRT, WinDOS – pro aplikace ve Windows (v Borland Pascalu) a řada dalších. 4
Další unity s obecnými nástroji od jiných výrobců lze zakoupit nebo získat jako freeware (např. prostředky pro ovládání programu myší).
Syntaxe vlastní unity 1. hlavička unit Alfa; jméno unity se musí shodovat se jménem souboru (používat max. 8 znaků) 2. sekce rozhraní interface obsahuje deklarace exportovaných symbolů (identifikátory, které může používat program využívající unitu) - deklarace konstant, typů, proměnných, hlavičky procedur a funkcí (včetně parametrů, ale bez těl) 3. sekce implementace implementation obsahuje povinně těla všech procedur a funkcí ze sekce interface a případně deklarace dalších prostředků, které se neexportují (identifikátory nejsou uživatelům unity viditelné) begin … end. 4. tělo syntakticky složený příkaz – vykoná se 1x při spuštění programu, který unitu používá (inicializace proměnných, mnohdy prázdné)
Každá unita je vlastní prostor jmen – identifikátory deklarované v unitě jsou navzájem různé, ale v různých unitách se mohou opakovat stejná jména. Řešení kolizí stejných jmen při použití prostředků z unit: použije se kvalifikovaný identifikátor ve tvaru JménoUnity.JménoProstředku např.: Alfa.X := 15; CRT.ClrScr; Pokud kolize jmen nenastane, jméno unity s tečkou není třeba uvádět (stačí X:=15; ClrScr; ).
Příklad: zásobník celých čísel Soubor ZASOB.PAS unit Zasob;
{jméno unity = jméno souboru!}
interface procedure Uloz(Cislo: integer); function Vezmi: integer; function Prazdny: boolean; function Plny: boolean;
5
{Přístupové procedury, pomocí nichž uživatel využívá služby zásobníku. Vlastní datová reprezentace zásobníku je uživateli unity skryta v sekci implementation, nemá k ní přímý přístup.} implementation const MAX=100; {maximální velikost zásobníku} var Zas: array[1..MAX] of integer; {zásobník} Vrchol: integer; {vrchol} procedure Uloz(Cislo: integer); begin inc(Vrchol); Zas[Vrchol] := Cislo end; function Vezmi: integer; begin Vezmi := Zas[Vrchol]; dec(Vrchol) end; function Prazdny: boolean; begin Prazdny := Vrchol = 0 end; function Plny: boolean; begin Plny := Vrchol = MAX end; begin Vrchol := 0 end.
{prázdný zásobník}
Příklad: prostředky na práci se zlomky unit Zlomky; interface type Zlomek = rekord Cit, Jm: integer end; {zlomek zkrácen, Jm > 0} procedure Precti (var Z: Zlomek); {přečte ze vstupu} procedure Vypis (Z: Zlomek); {vypíše na obrazovku} procedure Secti (A, B: Zlomek; var C: Zlomek); {C:=A+B} procedure Odecti (A, B: Zlomek; var C: Zlomek); {C:=A-B}
6
procedure Vynasob (A, B: Zlomek; var C: Zlomek);{C:=A*B} procedure Vydel (A, B: Zlomek; var C: Zlomek); {C:=A/B} procedure ZmenZnamenko (var Z: Zlomek); function Nulovy (Z: Zlomek): boolean; function Vetsi (A, B: Zlomek): boolean;
{Z:=-Z} {Z = 0 ?} {A > B ?}
procedure IntNaZlomek (I: integer; var Z: Zlomek); function ZlomekNaInt (Z: Zlomek) : integer; implementation … begin {prázdné tělo} end. V unitě nejsou deklarovány žádné proměnné. Exportuje se z ní typ Zlomek a vhodný počet proměnných typu Zlomek se deklaruje až podle konkrétní potřeby v programu, který prostředky unity využívá.
Práce s unitami v IDE TP Překlad: Compile – překládá jen soubor z aktuálního okna při použití uses hledá přeložené .TPU soubory Build – překládá i všechny soubory s používanými unitami při použití uses hledá zdrojové .PAS soubory Make – porovná datum a čas souborů .PAS a .TPU, překládá co je třeba (změna od posledního překladu) Kde se hledají soubory s unitami: 1. TURBO.TPL (Turbo Pascal Library) - zavádí se do operační paměti počítače při spuštění IDE TP 2. pracovní adresář 3. adresáře určené v Options/Directories/Unit directories Použití uses v unitě - pokud unita využívá prostředky deklarované v jiné unitě - lze uvést buď těsně za interface, nebo těsně po implementation, nebo na obou místech - použití za interface: když se prostředky z unity používají již v části interface (konstanty nebo typy) - použití za implementation: nutné v případě cyklické závislosti dvou nebo více unit
7
3. Modul CRT = standardní knihovna prostředků pro lepší práci s textovou obrazovkou, klávesnicí a generátorem zvuků Dosud jsme s obrazovkou pracovali jako s „textovým souborem“, výstupní data jsme na ni zapisovali sekvenčně po řádcích. Při použití CRT získáme možnost adresovat pozice na obrazovce, volit barvy písma, atd. Použití v programu: uses CRT; bezprostředně za hlavičkou programu
Adresace na obrazovce: (X, Y) X je sloupec, číslování od 1 do 80 zleva doprava Y je řádek, číslování od 1 do 25/50 shora dolů Konstanty barev: Black = 0 Blue = 1 Green = 2 Cyan = 3 Red = 4 Magenta = 5 Brown = 6 LightGray = 7
DarkGray = 8 LightBlue = 9 LightGreen = 10 LightCyan = 11 LightRed = 12 LightMagenta = 13 Yellow = 14 White = 15
Blink = 128 Proměnné: CheckBreak: boolean - citlivost na Ctrl+Break (přerušení výpočtu), default hodnota true CheckEOF: boolean - citlivost na Ctrl+Z (příznak EOF input), default hodnota false (!!!) TextAttr: byte - aktuální atributy zobrazování textu - bity 76543210 7 = blikání, 654 = pozadí, 3210 = popředí (zobrazený znak)
Procedury a funkce: TextColor(Color: 0..15) - barva písma TextBackground(Color: 0..7) - barva pozadí nastavují hodnotu TextAttr, lze i přímo dosadit, např. TextAttr := Yellow + Blue*16 + Blink; GotoXY(X, Y) WhereX → WhereY →
- umístění kursoru na pozici (X, Y) - funkce vrací X-ovou souřadnici kursoru - funkce vrací Y-ovou souřadnici kursoru
8
ClrScr ClrEol DelLine InsLine
- smaže obrazovku (barvou pozadí), kursor umístí na pozici (1,1) - smaže od kursoru do konce řádku - vynechá řádek s kursorem - vloží prázdný řádek
TextMode(mode) TextMode(C80) TextMode(C80+Font8x8)
25 řádků 50 řádků
Window(X1, Y1, X2, Y2) - definice „okna“ = výřezu obrazovky, s nímž se bude dále pracovat - (X1, Y1) – levý horní roh, (X2, Y2) – pravý dolní roh - dále adresace relativně v okně – levý horní roh okna je (1,1) - default celá obrazovka (1, 1, 80, 25)
Klávesnice KeyPressed → boolean - byla stisknuta nějaká klávesa? - znak je ponechán v klávesnicovém bufferu pro následné čtení - nereaguje na samotné přeřaďovače (Shift, Alt, Ctrl, CapsLock, NumLock) ReadKey → char - čte jeden znak z klávesnice (nečeká na Enter, bez echa na obrazovku) - KeyPressed = true → čte okamžitě, false → čeká na znak - reaguje i na speciální klávesy (na rozdíl od procedury read) Speciální klávesy na PC (ne ASCII) → rozšířené kódy: ReadKey čte nejprve znak #0 a následně kód speciální klávesy
Generátor zvuků Sound(Hz: word) NoSound
- spuštění zvuku s frekvencí Hz - vypnutí generátoru zvuku
Měření času Delay(ms: word) - pozdržení výpočtu o ms milisekund (přibližně) - použití pro vytváření zvuků (pomocí sekvence volání procedur Sound – Delay – NoSound), pro chvilkové zobrazení informace na obrazovce, apod.
9
4. Dynamicky alokované proměnné Alokace paměti = způsob přidělování paměťového prostoru proměnným: statická – proměnné hlavního programu na zásobníku – proměnné procedur a funkcí dynamická na haldě – proměnné vytvářené na žádost programu 1. statická alokace - paměť přidělena pevně na celou dobu výpočtu - překladač zná umístění – efektivní kód při přístupu k proměnné - použití pro proměnné deklarované v hlavním programu - překročení kapacity prostoru pro statická data ohlásí překladač 2. alokace na zásobníku (stack) - pro proměnné deklarované v procedurách a funkcích - paměť je přidělována v aktivačních záznamech na zásobníku (je v nich také návratová adresa a další technické údaje) - paměť přidělena vždy při zavolání procedury, při ukončení je opět uvolněna (lokální proměnné zanikají, jejich hodnoty se ztrácejí) - výhoda: úspora paměti (proměnné nemající momentálně význam nezabírají místo), umožnění rekurzivních volání (více exemplářů) - překročení kapacity zásobníku → běhová chyba „Stack overflow“ 3. dynamická alokace na haldě (heap) - přidělování paměti na explicitní žádost programu během výpočtu - na přidělené úseky paměti program odkazuje pomocí speciálních proměnných typu ukazatel (obsahují paměťové adresy) - nepotřebnou paměť program opět sám explicitně uvolňuje - uvolňování úseků paměti nemusí být v opačném pořadí než jejich přidělování, jako je tomu u zásobníku → vznikají „díry“ (fragmentace paměti) - překročení kapacity haldy → běhová chyba „Heap overflow“
Dynamicky alokované proměnné Výhody dynamické alokace: - proměnné existují jen po dobu, kdy jsou skutečně potřeba - velikost podle skutečné potřeby (až po zjištění velikosti vstupních dat) - na haldě je k dispozici více paměti než ve statickém segmentu a na zásobníku (to je ovšem specifikum pouze Turbo Pascalu jakožto DOSovské aplikace) - práce s ukazateli, možnost vytvářet dynamické datové struktury Nevýhody dynamické alokace: - dynamicky alokované proměnné nemají svůj jednoznačný identifikátor, přistupuje se k nim prostřednictvím ukazatelů → pomalejší přístup k datům, větší nebezpečí chyby při psaní programu 10
Práce s dynamicky alokovanými proměnnými - program žádá o přidělení paměti určité velikosti (buď přímo uvede počet bytů, nebo v Pascalu častěji chce alokovat proměnnou určitého typu) - paměťovou adresu přidělené paměti program převezme do speciální proměnné typu ukazatel - pomocí ukazatele program k dynamicky alokované proměnné přistupuje a manipuluje s ní jako s každou jinou proměnnou příslušného typu - když už proměnná není potřeba, program ji uvolní (uvolněná paměť se může využít pro následné alokace) Halda (heap) - paměť určená pro realizaci dynamických alokací - správce haldy = program na evidenci přidělených a uvolněných úseků, sousední volné úseky spojuje (aby byly větší souvislé kusy) - obsazené úseky nelze v paměti přesouvat (vedou na ně odkazy z programu) → fragmentace paměti - nové žádosti o alokaci se realizují v uvolněných úsecích haldy, strategie přidělování paměti first-fit (první použitelný) a best-fit (nejmenší použitelný úsek) - automatické uvolňování a posouvání úseků = garbage collector – v Pascalu není - nelze-li uspokojit žádost o alokaci → běhová chyba Heap overflow Zjištění stavu paměti (v Turbo Pascalu) funkce MemAvail → velikost volné paměti na haldě v bytech funkce MaxAvail → velikost největšího souvislého volného úseku paměti na haldě v bytech
Typ ukazatel - pro uložení jedné paměťové adresy - v Pascalu může proměnná typu ukazatel ukazovat vždy jen na data určitého typu type T = … ; Uk = ^T; var P, Q: Uk;
{co chceme dynamicky alokovat} {typ „ukazatel na T“} {proměnné typu „ukazatel na T“}
Lze psát přímo var P, Q: ^T; například type T1 var P1: type T2 var P2:
= record X: real; Y: char end; ^T1; = array[1..10] of integer; ^T2;
Alokace paměti – procedura new(P) - velikost požadované paměti je určena datovým typem, pro který je deklarován ukazatel P (doplní překladač) - alokuje se zpravidla nejbližší násobek 8 bytů (věc implementace) - ve výstupním parametru P procedura vrací adresu přidělené paměti - pozor – původní hodnota proměnné P se ztratí
11
Uvolnění paměti – procedura dispose(P) - velikost uvolňované paměti je určena datovým typem, pro který je deklarován ukazatel P (doplní překladač) - ve vstupním parametru P se proceduře předává adresa uvolňované paměti - pozor – hodnota proměnné P se přitom nezmění (P dál ukazuje na uvolněnou paměť)
Operace s ukazateli - získání nové hodnoty (dosavadní hodnota ukazatele se ztratí) * voláním procedury new new(P) * dosazením Q:=P dosazovat lze jen mezi ukazateli téhož typu - konstanta nil = neukazuje nikam Q:=nil kompatibilní se všemi ukazatelovými typy význam: speciální hodnota těch ukazatelů, které momentálně nikam neukazují → prevence před možným chybným odkazem, „zakončení“ dynamických datových struktur (bude později) - porovnání ukazatelů – relační operátory =, <> if P = Q then … while P <> nil do … porovnávat lze jen ukazatele téhož typu - přístup k dynamicky alokované proměnné, na kterou ukazuje P: P^ P1^.X := 3.14; write(P1^.Y); for I:=1 to 10 do read(P2^[I]); - k jedné dynamicky alokované proměnné můžeme přistupovat zároveň (nebo postupně) pomocí více různých ukazatelů new(P); Q := P; Q^.A := 15; write(P^.A); {vypíše „15“} dispose(Q); {uvolní paměť alokovanou pomocí new(P)} Rozlišujte: Q := P;
dosazení hodnoty ukazatele P do ukazatele Q, tzn. Q začne ukazovat na tu proměnnou, na kterou právě ukazuje P (neprovádí se nová alokace)
Q^ := P^; dosazení hodnoty dynamicky alokované proměnné P^ do proměnné Q^ (ta musí být naalokována), hodnoty ukazatelů P, Q se tím nezmění if Q = P then … if Q^ = P^ then …
test, zda ukazatele P, Q ukazují na stejné místo v paměti test, zda hodnoty dynamicky alokovaných proměnných P^, Q^ jsou stejné (mohou to ale být různé proměnné)
12
Pozor na ztrátu přístupu k dynamicky alokované proměnné! Provedením new(P) nebo P:=Q se ztratí dosavadní hodnota proměnné P. Pokud na proměnnou P^ neukazuje ještě jiný ukazatel, stane se proměnná P^ nedostupnou – nelze nadále pracovat s její hodnotou, ale není ani možné uvolnit ji (→ „smetí“ v paměti). Pozor na chybné použití ukazatelové proměnné, která ukazuje na uvolněné místo v haldě! Dispose(P); P^.A:=10; Po provedení dispose(P) se hodnota P nezmění, P nyní ukazuje do haldy na místo evidované jako uvolněný úsek. Obsah této proměnné využívá správce haldy pro svoji organizaci seznamu uvolněných úseků → zápis do P^ může znamenat destrukci seznamu uvolněných úseků haldy.
Dynamické datové struktury Vytvářejí se během výpočtu z dynamicky alokovaných proměnných, průběžně mohou podle potřeby měnit svoji velikost. Realizace: - dynamicky se alokuje záznam, který má mezi svými položkami jednu nebo více položek typu ukazatel, ty ukazují na další dynamicky alokované záznamy, atd. - ukončení dynamické struktury pomocí hodnoty nil v ukazateli nebo ukazatelích V jedné dynamické struktuře mohou být provázány záznamy téhož typu nebo různých typů (méně časté). Příklady dynamických datových struktur: lineární spojový seznam, binární strom, obecný strom, graf.
13
5. Lineární spojové seznamy type Uk = ^Uzel; Uzel = record Info: integer; Dalsi: Uk end;
{uložená informace} {propojení seznamu}
var P, Q, R: Uk;
P
10
20
30
40 NIL
Průchod seznamem - v každém uzlu provést akci A s uloženou hodnotou procedure Pruchod(P: Uk); begin while P <> nil do begin A(P^.Info); {volání procedury A představuje libovolnou požadovanou akci} P:=P^.Dalsi {posun P na další uzel seznamu} end end; Parametr P je předáván hodnotou → vytvoří se lokální kopie ukazatele na začátek procházeného LSS, v proceduře můžeme P měnit, aniž by se v programu ztratil ukazatel na začátek seznamu.
Určení posledního prvku seznamu - průchod seznamem ukončit o jeden krok dříve function Posledni(P: Uk): Uk; {Pro prázdný seznam vrací funkce hodnotu nil, jinak vrací ukazatel na poslední prvek seznamu.} begin if P <> nil then {seznam je neprázdný} while P^.Dalsi <> nil do P:=P^.Dalsi; {posunutí P na další uzel} Posledni:=P end;
14
Příklady využití: - připojení nového uzlu na konec seznamu - spojení dvou seznamů za sebe (v prvním musíme dojít na konec)
Nalezení hodnoty v LSS - v seznamu hledáme uzel obsahující zadanou hodnotu X - průchod seznamem až do nalezení prvního uzlu s hodnotou X, příp. až na konec seznamu (pokud tam X vůbec není) function Hledej(P: Uk; X: integer): Uk; {Pokud X v seznamu není, vrací funkce hodnotu nil, jinak vrací ukazatel na první prvek s hodnotou X.} begin while (P <> nil) and (P^.Info <> X) do P:=P^.Dalsi; {posunutí P na další uzel} Hledej:=P end; Pozn.: Funkce využívá zkrácené vyhodnocování logických výrazů. V případě úplného vyhodnocování by nastala běhová chyba, kdyby hodnota X v seznamu nebyla.
Vytvoření LSS odzadu = přidávání uzlů na začátek seznamu seznam s N uzly, v nich rostoucí hodnoty od 1 do N P:=nil; {na začátku prázdný seznam} while N > 0 do begin new(Q); {nový uzel} Q^.Info:=N; Q^.Dalsi:=P; {zapojit na začátek seznamu} P:=Q; {nový začátek seznamu} N:=N-1 end; {P ukazuje na vytvořený seznam} Vytvoření LSS odpředu = přidávání uzlů na konec seznamu seznam s N uzly, v nich rostoucí hodnoty od 1 do N - první prvek seznamu vytvořit zvlášť mimo cyklus (ukazatel P) - udržovat pomocný ukazatel na dosud poslední prvek seznamu (Q) new(P); P^.Info:=1; Q:=P; for I:=2 to N do begin new(R);
{první uzel seznamu} {je zároveň zatím posledním}
{nový uzel} 15
R^.Info:=I; Q^.Dalsi:=R; Q:=R end; Q^.Dalsi:=nil;
{zapojit na konec seznamu} {bude zatím posledním prvkem} {seznam zakončit pomocí nil}
Zrušení spojového seznamu - nestačí P:=nil ani dispose(P), ruší se prvek po prvku při průchodu seznamem - opět potřebujeme pomocný ukazatel Q na „přidržení“ právě rušeného prvního prvku seznamu procedure Zrus(P: Uk); var Q: Uk; begin while P <> nil do begin Q:=P; P:=P^.Dalsi; dispose(Q) end end;
Vložení prvku do seznamu za daný uzel - ukazatel P ukazuje na uzel, za který chceme vložit nový uzel obsahující hodnotu X new(Q); Q^.Info:=X; Q^.Dalsi:=P^.Dalsi; P^.Dalsi:=Q;
{nový uzel} {obsahuje hodnotu X} {1} {2} pozor na pořadí operací 1-2 !
P
2
X Q
16
1
Vypuštění prvku z LSS 1. Máme ukazatel P na předchůdce rušeného prvku (rušíme tedy následníka uzlu P^) - snadné, potřebujeme ale pomocný ukazatel Q na „přidržení“ rušeného uzlu Q:=P^.Dalsi; P^.Dalsi:=Q^.Dalsi; dispose(Q);
{rušený uzel} {obnova propojení seznamu} {uvolnění paměti}
P
Q
2. Máme ukazatel P na rušený prvek (rušíme tedy uzel P^) Trik: - vypustíme ze seznamu následníka uzlu P^ (už umíme) a jeho hodnotu přesuneme do uzlu P^ - nelze použít pro poslední prvek seznamu (nemá následníka) - nelze použít, vedou-li do seznamu nějaké další odkazy Pomalejší řešení: - musíme znát ukazatel na začátek seznamu - projdeme seznam od začátku a najdeme předchůdce uzlu P^, jeho následníka pak vypustíme (to už umíme) - použitelné vždy, jenom první prvek seznamu je třeba vypouštět odlišně (nemá předchůdce) procedure Zrus(var Z: Uk; P: Uk); {Z – ukazatel na začátek seznamu, P – ukazatel na rušený prvek} var Q: Uk; {předchůdce rušeného uzlu} begin if P = Z then {ruší se první prvek seznamu} begin Z:=Z^.Dalsi; {nový začátek seznamu} dispose(P) end else begin Q:=Z; while Q^.Dalsi <> P do Q:=Q^.Dalsi; {předchůdce} Q^.Dalsi:=P^.Dalsi; dispose(P) end end; 17
3. Zrušit v seznamu první uzel s hodnotou X - máme ukazatel na začátek seznamu (parametr procedury) - zvlášť ošetřit případ, že X je v prvním prvku seznamu – v tom případě se změní začátek seznamu (parametr procedury je proto třeba předávat odkazem!) - průchod seznamem s vyhledáním uzlu, který obsahuje hodnotu X, zaznamenat si ukazatel na předchůdce tohoto uzlu - nezapomenout ošetřit případ, že X v seznamu vůbec není - pomocí známého předchůdce lze uzel s hodnotu X snadno vypustit procedure Vypust(var Z: Uk; X: integer); var P: Uk; {ukazatel na rušený prvek} Q: Uk; {předchůdce rušeného uzlu} begin if Z = nil then exit; {prázdný seznam} if Z^.Info = X then {X v prvním prvku seznamu} begin P:=Z; Z:=Z^.Dalsi; {nový začátek seznamu} dispose(P); {zrušit první prvek} exit end; Q:=Z; P:=Z^.Dalsi; while (P <> nil) and (P^.Info <> X) do begin Q:=P; P:=P^.Dalsi end; if P <> nil then {nalezena hodnota X} begin Q^.Dalsi:=P^.Dalsi; dispose(P) {zrušit prvek s X} end end;
Obrácení pořadí prvků v LSS - ze začátku původního LSS postupně odpojujeme uzly a zapojujeme je na začátek vytvářeného výsledného seznamu (výsledný seznam tedy stavíme odzadu → bude mít uzly v obráceném pořadí) - žádné uzly nerušíme ani nealokujeme, výsledný seznam stavíme z uzlů původního seznamu - lineární časová složitost – jeden průchod seznamem - procedura na obracení seznamu má jeden parametr předávaný odkazem – je vstupní (ukazatel na začátek původního seznamu) i výstupní (ukazatel na začátek obráceného seznamu) Využití: když potřebujeme procházet seznamem střídavě oběma směry (proti směru řazení uzlů to normálně nejde). Jiným možným řešením bude použití obousměrného lineárního spojového seznamu – paměťově náročnější (v každém uzlu budou dva ukazatele), ale nemusí se zase opakovaně obracet seznam.
18
procedure Obrat(var P: Uk); var Q, R: Uk; begin R:=nil; {výsledný seznam, zatím prázdný} while P <> nil do begin Q:=P; {přepojovaný uzel} P:=P^.Dalsi; {nový začátek původního seznamu} Q^.Dalsi:=R; {zapojit na začátek výsledného} R:=Q {nový začátek výsledného seznamu} end; P:=R end;
Druhy lineárních spojových seznamů 1. Obousměrný seznam type Uk = ^Uzel; Uzel = record Info: integer; Za, Pred: Uk end;
P
10
{uložená informace} {propojení seznamu}
20
30
40 NIL
NIL
Vlastnosti: - paměťově náročnější než jednosměrný seznam - umožňuje procházení seznamem střídavě oběma směry - některé operace obtížnější (přepojuje se více ukazatelů), jiné naopak snadnější
Příklad: vypuštění prvku z obousměrného LSS - máme ukazatel P na rušený prvek (P není okrajový prvek) P^.Pred^.Za:=P^.Za; {1} P^.Za^.Pred:=P^.Pred; {2} dispose(P);
19
P 1 5
3
12
2 2. Cyklický seznam - poslední prvek seznamu neukazuje na NIL, nýbrž na první prvek - lze i pro obousměrné seznamy, potom navíc první prvek seznamu ukazuje svým ukazatelem Pred na poslední prvek
P
3. Seznam s hlavou hlava = jeden prvek navíc umístěný vždy na začátku seznamu, neobsahuje uloženou hodnotou (příp. položku Info v hlavě lze využít pro jiné účely) Použití: prázdný seznam je tvořen samotnou hlavou (není to tedy jen NIL jako u obyčejných seznamů) → snáze se programují některé akce spočívající v přidávání resp. odebírání prvků ze seznamu (není třeba odlišovat stále zvláštní případy, že seznam je prázdný).
P
10
20
30 NIL
hlava
seznam má tři prvky
20
Možné kombinace - např. obousměrný cyklický lineární spojový seznam s hlavou (používá se někdy pro realizaci fronty)
Použití lineárních spojových seznamů Náhrada jednorozměrného pole – seznam údajů Paměť: - pole v Pascalu pouze konstantní velikosti, LSS vytvoříme potřebné délky podle počtu údajů - v prvcích pole jsou uloženy jen užitečné informace, v prvcích LSS uloženy navíc odkazy (ukazatel na další prvek) Čas: - některé operace jsou v LSS jednodušší (např. vypustit prvek se zachováním pořadí ostatních) - některé operace jsou v LSS složitější (např. zjistit hodnotu předcházejícího prvku) Použitelnost: - v LSS nelze indexovat prvky (např. nelze realizovat binární vyhledávání půlením intervalů)
Realizace zásobníku a fronty
Zásobník - realizován jednoduchým LSS, ukazatel na začátek seznamu ukazuje na vrchol zásobníku (dno zásobníku = NIL) - prázdný zásobník = prázdný LSS - přidávání i odebírání prvků se provádí na začátku LSS – snadné
procedure DoZasobniku(var Z: Uk; C: integer); {do zásobníku celých čísel Z přidá číslo C} var P: Uk; begin new(P); P^.Info := C; P^.Dalsi := Z; Z := P end;
21
function ZeZasobniku(var Z: Uk): integer; {vrací jedno číslo odebrané ze zásobníku; je-li zásobník prázdný, funkce by neměla být volána, vrací v takovém případě hodnotu maxint} var P: Uk; begin if Z = nil then ZeZasobniku := maxint else begin ZeZasobniku := Z^.Info; P := Z; Z := Z^.Dalsi; dispose(P) end end;
Fronta - realizována jednoduchým LSS a dvěma ukazateli: na začátek (tj. na první prvek LSS) a na konec (tj. na poslední prvek LSS) - na začátku LSS se dobře přidává i odebírá prvek, na konci LSS se dobře přidává, ale špatně odebírá → na začátku LSS bude odchod, na konci LSS bude příchod !! (tzn. každý ukazuje na toho, kdo přišel po něm, což je obráceně, než ve frontách v běžném životě) - prázdná fronta = prázdný LSS Jiná možná realizace: LSS s hlavou (snáze se pak programují operace s dočasně prázdnou frontou) type Fronta = rekord Prichod, Odchod: Uk end;
procedure DoFronty(var F: Fronta; C: integer); {do fronty celých čísel F přidá číslo C} var P: Uk; begin new(P); P^.Info := C; if F.Odchod = nil then {prázdná fronta} begin F.Prichod := P; F.Odchod := P end else begin F.Prichod^.Dalsi := P; F.Prichod := P end end;
22
function ZFronty(var F: Fronta): integer; {vrací jedno číslo odebrané z fronty; je-li fronta prázdná, funkce by neměla být volána, vrací v takovém případě hodnotu maxint} var P: Uk; begin if F.Odchod = nil then {prázdná fronta} ZFronty := maxint else begin ZFronty:= F.Odchod^.Info; P := F.Odchod; if F.Odchod = F.Prichod then F.Odchod := nil {fronta bude prázdná} else F.Odchod := F.Odchod^.Dalsi; dispose(P) end end;
Dlouhá čísla - uložena po cifrách nebo po skupinách cifer podobně jako v poli - nejsme omezeni maximálním možným počtem cifer v čísel - směr řazení LSS závisí na prováděných operacích (např. pro sčítání nebo násobení odzadu od cifer nejnižšího řádu, pro výpis ale potřebujeme cifry odpředu – bude nutno otáčet seznam) Polynomy - opět podobná reprezentace jako u polí – v každém prvku LSS uložen koeficient a exponent jednoho členu polynomu, členy s nulovým koeficientem se do LSS neukládají - pro provádění operací je výhodné mít LSS uspořádaný (vzestupně nebo sestupně) podle hodnot exponentu.
23
6. Rekurze V programování se rekurze objevuje ve dvou hladinách: - rekurzivní algoritmus (řešení úlohy je definováno pomocí řešení podúloh stejného charakteru) - rekurzivní volání procedury nebo funkce (volá sama sebe přímo nebo nepřímo prostřednictvím jiných procedur resp. funkcí) Většinou se rekurzivní algoritmy realizují pomocí rekurzivních volání, ale není to nezbytné: - rekurzivní algoritmus lze realizovat bez rekurzivních volání (pomocí vlastního zásobníku na uložení rozpracovaných nedokončených podúloh) → více práce pro programátora, program obvykle delší a méně přehledný, výpočet ale může být o něco efektivnější - rekurzivní volání lze teoreticky použít i při realizaci nerekurzivních iteračních algoritmů (dokonce každý cyklus lze nahradit rekurzivní procedurou) → většinou nevhodné, nečitelný a méně efektivní program. Rekurzivní volání - najednou je rozpočítáno více exemplářů téže procedury - všechny počítají podle téhož kódu - každý exemplář má na zásobníku svůj vlastní aktivační záznam s lokálními proměnnými, parametry a technickými údaji (kde je rozpočítán, návratová adresa) - procedura nemá přístup k lokálním proměnným jiného rekurzivního exempláře procedure Otoc; var U: char; begin read(U); if U <> ‘ ’ then Otoc; write(U) end; Vstup: ABC_ Výstup: _CBA
Příklady použití: Eukleidův algoritmus realizovaný funkcí s cyklem function NSD(X, Y: integer): integer; begin while X <> Y do if X > Y then X:=X - Y else Y:=Y - X; NSD:=X end; {function NSD}
24
Eukleidův algoritmus realizovaný rekurzivní funkcí - přesně kopíruje rekurzivní vztah pro NSD, na němž je Eukleidův algoritmus založen: když X < Y NSD(X,Y) = NSD(X,Y-X) když X > Y NSD(X,Y) = NSD(X-Y,Y) když X = Y NSD(X,Y) = X function NSD(X, Y: integer): integer; begin if X > Y then NSD:=NSD(X-Y, Y) else if Y > X then NSD:=NSD(X, Y-X) else {X = Y} NSD:=X end; {function NSD}
Faktoriál N! (součin čísel od 1 do N) rekurzivní definice: N! = 1 N! = N.(N-1)!
pro N = 0 pro N > 0
function Faktorial (N: integer): integer; var F, I: integer; begin F:=1; for I:=2 to N do F:=F*I; Faktorial:=F end; function Faktorial (N: integer): integer; begin if N=0 then Faktorial:=1 else Faktorial:=N*Faktorial(N-1) end; Časová složitost obou uvedených řešení je O(N). Fibonacciho čísla FN =
0 1 FN-1 + FN-2
pro N = 0 pro N = 1 pro N > 1
Rekurzivní definice posloupnosti čísel → realizace rekurzivní funkcí přesně podle definice: function Fib(N: integer): integer; begin if N=0 then Fib:=0 else if N=1 then Fib:=1 else Fib:=Fib(N-1)+Fib(N-2) end;
25
Funkce je teoreticky správná, ale její časová složitost je O(2N) → pro N větší než cca 40 je prakticky nepoužitelná Důvod: mnohokrát se opakovaně počítají stejné věci. Možnosti řešení: 1. rekurzivní algoritmus + pomocné pole pro uložení již spočítaných funkčních hodnot („chytrá rekurze“) – každé Fi se počítá jen jednou → časová složitost O(N) 2. počítat hodnoty iteračně odspodu – v pořadí F1, F2, … FN → časová složitost O(N) 3. z rekurzivní definice odvodit explicitní vzorec a počítat podle něj N N 1 − 5 5 1 + 5 − FN = 2 5 2
Použití rekurze Úlohy typu „zkoušení všech možností“ nebo „generování všech možností“ Příklad: vypsat všechna K-ciferná čísla v poziční soustavě o základu N Pokud K je předem pevně dáno: for i1:=0 to N-1 do for i2:=0 to N-1 do for i3:=0 to N-1 do … for iK:=0 to N-1 do writeln(i1, i2, i3, …, iK) Je-li K vstupním údajem, nemůžeme toto zapsat pomocí vnořených cyklů – nevíme předem, kolik jich máme v programu napsat. Řešení: rekurzivní procedura obsahující jeden takový cyklus, rekurzivní zanoření jde vždy do hloubky K. const MaxK = 20; var C: array[1..MaxK] of byte; N, K: byte;
{max. přípustné K} {uložení čísla}
begin write('Zadejte hodnoty K a N: '); readln(K, N); Cislo(1); end.
26
Dvě možné varianty implementace rekurzivní funkce Cislo: procedure Cislo(p:byte); {p - pořadí vybírané cifry čísla} {procedura používá globální proměnné C, K, N} var i,j:byte; begin for i:=0 to N-1 do begin C[p] := i; if p < K then Cislo(p+1) else begin for j:= 1 to K do write(C[j]); writeln end end end; procedure Cislo(p:byte); {p - pořadí vybírané cifry čísla} {procedura používá globální proměnné C, K, N} var i:byte; begin if p > K then {hotovo} begin for i:= 1 to K do write(C[i]); writeln end else {doplnit C[p]} for i:=0 to N-1 do begin C[p] := i; Cislo(p+1) end end;
Doplnění znamének Je dáno N celých čísel a požadovaný součet C. Před čísla doplňte znaménka + nebo – tak, aby byl součet čísel se znaménky roven danému C. Nalezněte všechna řešení úlohy. Řešení: před každé číslo zkusíme postupně dát + nebo –, po vytvoření celé N-tice znamének otestujeme součet → 2N možností, tedy časové složitost O(2N). program Soucet_Cisel_V_Poli; const MaxN = 100; var H: array[1..MaxN] of integer; 27
{max. počet čísel} {sčítaná čísla}
N: C: Z: I:
integer; integer; array[1..MaxN] of char; integer;
{počet čísel} {hledaný součet} {uložení znamének}
procedure X (K: integer; Soucet: integer); {K - kolikáté znaménko hledám, Soucet - průběžný součet čísel až do K-tého} {Procedura používá globální proměnné N, C, H, Z} var I: integer; begin if K = N+1 then {pole znamének zcela obsazeno} begin if Soucet = C then {našli jsme řešení} begin for I:=1 to N do write(Z[I], H[I]); writeln end end else {zkusíme hodnoty K-tého znaménka} begin Z[K] := '+'; X(K+1, Soucet+H[K]); Z[K] := '-'; X(K+1, Soucet-H[K]); end end; {procedure X} begin write('Počet sčítaných čísel: '); readln(N); writeln('Sčítaná čísla: '); for I:=1 to N do read(H[I]); write('Požadovaný součet: '); readln(C); X(1, 0); {začínáme od prvního znaménka, dosud součet 0} readln; end.
Rozklad čísla Zadané kladné celé číslo N rozložte všemi různými způsoby na součet kladných celých sčítanců. Rozklady lišící se pouze pořadím sčítanců nepovažujeme za různé. Příklad: 5 =4+1 =3+2 =3+1+1 =2+2+1 =2+1+1+1 =1+1+1+1+1
28
Řešení: Aby se neopakovaly stejné rozklady s různým pořadím sčítanců, budeme vytvářet pouze rozklady s nerostoucím pořadím sčítanců. Na každou pozici rozkladu vždy vyzkoušíme všechny přípustné hodnoty (maximálně kolik ještě zbývá a maxaximálně kolik je na předchozí pozici, minimálně 1). Toto provádíme, dokud je co rozkládat. program RozkladCisla; const Max = 100; var N: integer; A: array[0..Max] of integer;
{maximální přípustné N} {rozkládané číslo} {uložení rozkladu}
function Min(A, B: integer): integer; {pomocná funkce na výpočet minima z dvou celých čísel A, B} begin if A > B then Min := B else Min := A end; procedure Rozloz(Zbytek, P: integer); { Zbytek = kolik zbývá rozložit, P = kolikátý sčítanec vytváříme } var I: integer; begin if Zbytek = 0 then {rozklad je hotov} begin for I:=1 to P-1 do write(A[I]:3); writeln end else {přidat další člen rozkladu - v pořadí P-tý} begin for I:=Min(Zbytek, A[P-1]) downto 1 do begin A[P] := I; Rozloz(Zbytek-I, P+1) end; end; end; {procedure Rozloz} begin {hlavní program} write('Rozkládané číslo (1-',Max,'): '); readln(N); A[0] := Max+1; {technický trik} Rozloz(N, 1); {rozložit celé N, začínáme 1. sčítancem} end.
29
7. Prohledávání do hloubky a do šířky Backtracking = = =
prohledávání do hloubky prohledávání s návratem zpětné prohledávání
- postupně zkoušet všechny varianty pokračování, dokud nenajdeme řešení úlohy (hledáme-li jedno libovolné) nebo dokud neprojdeme všechny možnosti (máme-li nalézt všechna řešení úlohy) - je-li zvolená cesta neúspěšná, vrátíme se z ní zpět a zkoušíme jinou - to se opakuje v každém kroku, kde je výběr z více možných pokračování → průchod stromem všech možných cest výpočtu do hloubky, v každém rozhodovacím uzlu postupně zkoušíme všechny možnosti zleva doprava Příklady: Úlohy z minulé kapitoly - vypsat všechna K-ciferná čísla v poziční soustavě o základu N - doplnění znamének - rozklad čísla Řešení zkoušením všech možností je vlastně prohledáváním do hloubky. Hledání cesty v bludišti - dána výchozí pozice, máme nalézt východ z bludiště (nebo třeba poklad) - na každé křižovatce zkoušíme postupně všechny dosud nepoužité cesty - pro každou z nich hledáme řešení rekurzivním voláním téhož algoritmu
Osm dam na šachovnici - úkol: rozmístit na šachovnici 8 šachových dam tak, aby se žádné dvě navzájem neohrožovaly - v řádku zkoušíme postupně umístit dámu do všech sloupců, kam je to možné s ohledem na dámy umístěné v předchozích řádcích - pro každou takovou volbu hledáme rekurzivně řešení pro dámu na následujícím řádku
program OsmDam; {rozmístit 8 dam na šachovnici, aby se žádné dvě neohrožovaly} const N = 8; var A: array[1..N, 1..N] of boolean; i, j: integer; Pocet: longint; procedure Vypis; var i,j: integer;
30
begin for i:=1 to N do begin for j:=1 to N do if A[i,j] then write('* ') else write('. '); writeln end; writeln end; function Kolize(R, S: integer): boolean; var i, j: integer; begin Kolize:=false; for i:=1 to R-1 do if A[i,S] then begin Kolize:=true; exit end; i:=R-1; j:=S-1; while (i > 0) and (j > 0) do if A[i,j] then begin Kolize:=true; exit end else begin dec(i); dec(j) end; i:=R-1; j:=S+1; while (i > 0) and (j <= N) do if A[i,j] then begin Kolize:=true; exit end else begin dec(i); inc(j) end; end; procedure Damy(R: integer); var j: integer; begin for j:=1 to N do begin A[R,j]:=true; if not Kolize(R, j) then if R < N then Damy(R+1) else begin Vypis; inc(Pocet) end; A[R,j]:=false end end; begin for i:=1 to N do for j:=1 to N do A[i,j]:=false; Pocet:=0; Damy(1); writeln('Počet řešení: ', Pocet); writeln end.
31
Paměťová složitost - výška stromu představujícího všechny možné cesty výpočtu - vždy se pamatuje jedna cesta od kořene prohledávacího stromu k listu kořen = výchozí situace list stromu = buď řešení, nebo „slepá ulička“ Obvykle bývá rozumně velká, prohledávání do hloubky je paměťově zvládnutelné.
Časová složitost - počet uzlů ve stromu představujícím všechny možné cesty výpočtu (příp. v lepším případě jen jeho části, pokud neprocházíme celý, ale jen do nalezení prvního řešení). Obvykle exponenciální, prohledávání do hloubky je použitelné jen pro velmi malé úlohy. Snažíme se alespoň trochu zlepšit časovou složitost → ořezávání, heuristiky.
Ořezávání Během procházení stromu do hloubky vyhodnocujeme průběžně situaci v každém uzlu a je-li neperspektivní (tzn. nemůže vést k nalezení řešení), příslušný podstrom vůbec neprocházíme (odřízneme ho ze stromu). U některých úloh může ořezávání ušetřit velké množství práce.
Příklad: nalézt všechny magické čtverce velikosti N x N - každé z čísel od 1 do N 2 právě jednou - stejné součty ve všech řádcích a sloupcích (příp. i na obou diagonálách) pro N = 3 může vypadat třeba takto:
8 1 6 3 5 7 4 9 2
Hloupé řešení: zkoušet a testovat všechny permutace čísel od 1 do N 2 Ořezávání: - vždy hned po vyplnění jednoho řádku otestovat, zda je perspektivní (tzn. zda má správný součet) - když není, neztrácet zbytečně čas zkoušením všech permutací zbývajících čísel na zbývajících pozicích ve čtverci Určení součtu čísel v každé řadě magického čtverce řádku N: - součet všech čísel od 1 do N 2 je roven N 2.(N 2 + 1) / 2 - o tento součet musí rovným dílem podělit N řad, tedy každá z nich má součet N.(N 2 + 1) / 2 Např. pro N = 3 vyjde součet 15. 32
Heuristiky Použití heuristik je jiná programovací technikou na zrychlení výpočtu při prohledávání do hloubky. Odhadneme, kde je asi větší šance na nalezení řešení → použije se na určení pořadí, v němž se budou procházet varianty možných pokračování. Hledáme-li jedno libovolné řešení, zvyšujeme dobrou heuristikou pravděpodobnost, že ho najdeme brzy (neboť pořadí listů ve stromu se změní tak, že listy představující úspěšné řešení se nakupí více vlevo). V důsledku toho projdeme třeba jen velmi malou část stromu → velká časová úspora. Nepomůže nám to, pokud potřebujeme nalézt všechna řešení – potom stejně musíme projít celý prohledávací strom. Heuristika nic nezaručuje, proto se nemusí dokazovat její správnost, lze ji použít na základě intuitivního odhadu programátora. Není-li dobrá, výpočet nezrychlí, ale o možnost nalézt řešení jejím použitím nepřijdeme.
Příklad: Proskákání celé šachovnice koněm - je dána výchozí pozice šachového koně, máme s ním proskákat postupně všechna pole na šachovnici, žádné přitom nesmíme navštívit dvakrát - řešení prohledáváním do hloubky: v každé pozici zkoušíme postupně provést koněm tah na všechna dosud nenavštívená sousední pole - pro každý takový tah hledáme rekurzivně řešení v pozici vzniklé tímto tahem program PruchodSachovnice; const N = 8; {velikost strany čtvercové šachovnice} PocetKroku = 63; { = N*N - 1 } {počet tahů koně tvořících výslednou cestu} PocetTahu = 8; {počet různých tahů z jednoho pole} type
Index = 1..N;
{typ indexu na šachovnici}
var S: array[Index, Index] of integer; {šachovnice} Tah: array[1..PocetTahu] of record d1, d2: integer end; {možné tahy koně} Start1, Start2: Index; {souřadnice výchozí pozice koně} Nalezeno: Boolean; {příznak nalezení cesty koněm} i, j: Index; {pomocné indexy} procedure Cesta(i1, i2: Index; var Nalezeno: Boolean); {Procedura pro nalezení cesty koně z pozice (i1,i2) do konce. Začátek cesty je uložen v globálním poli S. Výstupní parametr Nalezeno udává, zda se cestu podařilo nalézt (po vyzkoušení všech možností)}
33
var Smer: 0..PocetTahu;{směr pohybu koně - index v poli Tah} j1, j2: integer; {nová pozice koně} Krok: integer; {pořadové číslo provedeného tahu} Nalez: Boolean; {příznak úspěšného nalezení cesty} begin Krok := S[i1,i2] + 1; Smer := 0; Nalez := false; {zatím cesta nenalezena} repeat {zkoušíme postupně všechny směry tahu koně} Smer := Smer+1; {nový zkoušený směr} j1 := i1 + Tah[Smer].d1; j2 := i2 + Tah[Smer].d2; {nové souřadnice koně} if (j1 >= 1) and (j1 <= N) and (j2 >= 1) and (j2 <= N) then {je uvnitř šachovnice} if S[j1,j2] = -1 then {pole dosud nenavštíveno} begin S[j1,j2] := Krok; if Krok = PocetKroku then Nalez := true {řešení úlohy nalezeno!} else begin {prodloužit cestu pomocí rekurze} Cesta(j1,j2,Nalez); if not Nalez then S[j1,j2] := -1 {neúspěšný pokus - nutný návrat} end end until Nalez or (Směr = PocetTahu); {konec hledání, pokud jsme cestu našli nebo když jsme vyzkoušeli všech 8 směrů bez úspěchu} Nalezeno := Nalez {vrací se výsledek hledání} end; {procedure Cesta} begin {program} {inicializace pole tahů koněm:} Tah[1].d1 := 1; Tah[1].d2 := 2; Tah[2].d1 := 2; Tah[2].d2 := 1; Tah[3].d1 := 2; Tah[3].d2 := -1; Tah[4].d1 := 1; Tah[4].d2 := -2; Tah[5].d1 := -1; Tah[5].d2 := -2; Tah[6].d1 := -2; Tah[6].d2 := -1; Tah[7].d1 := -2; Tah[7].d2 := 1; Tah[8].d1 := -1; Tah[8].d2 := 2; {inicializace šachovnice:} write('Počáteční pozice koně: '); readln(Start1, Start2); for i:=1 to N do for j:=1 to N do S[i,j] := -1; S[Start1,Start2] := 0;
34
Cesta(Start1, Start2, Nalezeno); {výsledek hledání cesty:} writeln; if Nalezeno then {výpis nalezené cesty koněm po šachovnici} for i:=1 to N do begin for j:=1 to N do write(S[i,j]:4); writeln end else writeln('Cesta neexistuje.'); writeln end.
Uvedené řešení je velmi pomalé. Existuje ale velmi účinná heuristika: v dané pozici provádět dříve vždy ty skoky, které vedou do pozic s menším počtem dalších pokračování. Tato heuristika vede ke zrychlení výpočtu o několik řádů. program Heuristika; {Pořadí zkoušených směrů pohybu koně je řízeno heuristikou: nejprve se jde na pole s menším počtem možností dalšího pokračování cesty.} const N = 8; {velikost strany čtvercové šachovnice} PocetKroku = 63; { = N*N - 1 } {počet tahů koně tvořících výslednou cestu} PocetTahu = 8; {počet různých tahů z jednoho pole} type
Index = 1..N; {typ indexu na šachovnici} SeznamSmeru = array[1..PocetTahu] of 1..PocetTahu; {seznam přípustných směrů pohybu koně}
var S: array[Index, Index] of integer; {šachovnice} Tah: array[1..PocetTahu] of record d1, d2: integer end; {možné tahy koně} Start1, Start2: Index; {souřadnice výchozí pozice koně} Nalezeno: Boolean; {příznak nalezení cesty koněm} i, j: Index; {pomocné indexy} function PocetVolnych(i1, i2: Index): integer; {Pomocná funkce pro určení počtu volných polí v okolí pole (i1,i2) - výsledek vrací jako funkční hodnotu.} var Smer: 1..PocetTahu;{směr pohybu koně - index v poli Tah} j1, j2: integer; {nová pozice koně} Pocet: integer; {počet volných polí v okolí (i1,i2)}
35
begin Pocet := 0; for Smer:=1 to PocetTahu do begin {zkoušíme postupně všechny směry tahu koně} j1 := i1 + Tah[Smer].d1; j2 := i2 + Tah[Smer].d2; {nové souřadnice koně} if (j1 >= 1) and (j1 <= N) and (j2 >= 1) and (j2 <= N) then {je uvnitř šachovnice} if S[j1,j2] = -1 then {pole dosud nenavštíveno} Pocet := Pocet+1; end; PocetVolnych := Pocet end; {function PocetVolnych} procedure UrciSmery(i1, i2: Index; var Sm: SeznamSmeru; var PocetSm: integer); {Pomocná procedura pro nalezení všech možných tahů koně z pozice (i1,i2). Směry tahů uloží do pole Sm, jejich počet do PocetSm. Tahy seřadí podle heuristiky.} var Smer: 1..PocetTahu;{směr pohybu koně - index v poli Tah} j1, j2: integer; {nová pozice koně} Volne: array[1..PocetTahu] of 0..PocetTahu; {počet volných polí v okolí pole určeného podle Sm} i, j, k, x: integer; {pro potřeby třídění} begin PocetSm := 0; for Smer:=1 to PocetTahu do begin {zkoušíme postupně všechny směry tahu koně} j1 := i1 + Tah[Smer].d1; j2 := i2 + Tah[Smer].d2; {nové souřadnice koně} if (j1 >= 1) and (j1 <= N) and (j2 >= 1) and (j2 <= N) then {je uvnitř šachovnice} if S[j1,j2] = -1 then {pole dosud nenavštíveno} begin PocetSm := PocetSm+1; Sm[PocetSm] := Smer; {uložit úspěšný směr pohybu} Volne[PocetSm] := PocetVolnych(j1,j2) end end; {pole Sm je naplněno přípustnými tahy, ještě musíme zvolit jejich pořadí - heuristika podle počtu volných sousedních polí:} for i:=1 to PocetSm-1 do begin k:=i; for j:=i+1 to PocetSm do if Volne[j] < Volne[k] then k:=j; if k > i then begin x:=Sm[k]; Sm[k]:=Sm[i]; Sm[i]:=x;
36
x:=Volne[k]; Volne[k]:=Volne[i]; Volne[i]:=x end end end; {procedure UrciSmery} procedure Cesta(i1, i2: Index; var Nalezeno: Boolean); {Procedura pro nalezení cesty koně z pozice (i1,i2) do konce. Začátek cesty je uložen v globálním poli S. Výstupní parametr Nalezeno udává, zda se cestu podařilo nalézt (po vyzkoušení všech možností)} var Smer: 1..PocetTahu;{směr pohybu koně - index v poli Sm} Sm: SeznamSmeru; {možné směry pohybu koně v pořadí daném heuristikou - indexy do pole Tah} PocetSm: integer; {počet možných tahů koně} j1, j2: integer; {nová pozice koně} Krok: integer; {pořadové číslo provedeného tahu} Nalez: Boolean; {příznak úspěšného nalezení cesty} begin Krok := S[i1,i2] + 1; UrciSmery(i1, i2, Sm, PocetSm); Smer := 1; Nalez := false; while (Smer <= PocetSm) and not Nalez do begin {zkoušíme postupně všechny směry tahu koně} j1 := i1 + Tah[Sm[Smer]].d1; j2 := i2 + Tah[Sm[Smer]].d2; {nové souřadnice koně} S[j1,j2] := Krok; if Krok = PocetKroku then Nalez := true {řešení úlohy nalezeno!} else begin {prodloužit cestu pomocí rekurze} Cesta(j1, j2, Nalez); if not Nalez then S[j1,j2] := -1 {neúspěšný pokus - nutný návrat} end; Smer := Smer+1; {nový zkoušený směr} end; Nalezeno := Nalez {vrací se výsledek hledání} end; {procedure Cesta} begin {program} {inicializace pole tahů koněm:} Tah[1].d1 := 1; Tah[1].d2 := 2; Tah[2].d1 := 2; Tah[2].d2 := 1; Tah[3].d1 := 2; Tah[3].d2 := -1; Tah[4].d1 := 1; Tah[4].d2 := -2; Tah[5].d1 := -1; Tah[5].d2 := -2; Tah[6].d1 := -2; Tah[6].d2 := -1;
37
Tah[7].d1 := -2; Tah[7].d2 := 1; Tah[8].d1 := -1; Tah[8].d2 := 2; {inicializace šachovnice:} write('Počáteční pozice koně: '); readln(Start1, Start2); for i:=1 to N do for j:=1 to N do S[i,j] := -1; S[Start1,Start2] := 0; Cesta(Start1, Start2, Nalezeno); {výsledek hledání cesty:} writeln; if Nalezeno then {výpis nalezené cesty koněm po šachovnici} for i:=1 to N do begin for j:=1 to N do write(S[i,j]:4); writeln end else writeln('Cesta neexistuje.'); writeln end.
Spojení ořezávání a heuristik při zvyšování rychlosti backtrackingu - pokud máme nalézt nejlepší řešení úlohy podle nějakého zadaného kritéria Vhodnou heuristikou se zajistí, aby se co nejdříve našlo nějaké hodně dobré řešení. Díky tomu se následně zvýší účinnost ořezávání (ořezávají se všechny pokusy, u nichž je zřejmé, že povedou k nalezení horšího řešení). Příklad: Nalézt nejkratší cestu mezi dvěma městy, neznáme-li předem mapu ani vzájemné vzdálenosti. - v každém městě si pamatujeme, jak nejlépe jsme tam přišli - přicházíme-li do města delší cestou, nemá smysl pokračovat - je-li průběžná délka větší než již nalezená cesta do cíle, nemá smysl pokračovat.
Prohledávání do šířky = algoritmus „vlny“ - souběžně zkoušet všechny možné varianty pokračování výpočtu, dokud nenajdeme řešení úlohy → průchod stromem všech možných cest výpočtu do šířky, po vrstvách (v každé vrstvě zkouší všechny možnosti zleva doprava) - je nutné pamatovat si všechny situace v jedné vrstvě stromu → při větší hloubce je to paměťově velmi náročné (exponenciálně), až nepoužitelné
38
- použijeme, máme-li nalézt jedno (nejkratší) řešení → vždy najde nejkratší možné řešení co do počtu kroků - výhodné, existují-li v rozsáhlém prohledávacím stromě nějaká řešení vzdálená od startu jen na málo kroků – prohledá se jen několik horních vrstev stromu (významná časová úspora oproti prohledávání do hloubky) - nevhodné při úloze nalézt všechna řešení – musí se projít celý strom, a to je při stejné časové složitosti výhodnější provádět do hloubky (paměťově mnohem méně náročné) - v některých úlohách je nutné prohledávat do hloubky (prohledávání do šířky by se paměťově nezvládlo), v některých je nutné prohledávat do šířky (prohledávání do hloubky by se časově nezvládlo), v některých je to jedno (obě varianty prohledávání jsou paměťově i časově stejně náročné)
Realizace prohledávání do hloubky a do šířky Prohledávání do hloubky se zpravidla realizuje rekurzivní procedurou, totéž lze naprogramovat pomocí zásobníku: vlož do zásobníku výchozí stav dokud (není zásobník prázdný) a (není nalezeno řešení) opakuj - vyjmi ze zásobníku vrchní stav a zpracuj ho - vlož do zásobníku jeho všechna možná pokračování Prohledávání do šířky se realizuje velmi podobně pomocí fronty: vlož do fronty výchozí stav dokud (není fronta prázdná) a (není nalezeno řešení) opakuj - vyjmi z fronty první stav a zpracuj ho - vlož do fronty jeho všechna možná pokračování Příklady: Proskákání celé šachovnice koněm (rozbor úlohy viz výše) - každé možné řešení úlohy má délku 63 kroků, použití prohledávání do šířky je paměťově nereálné Nejkratší cesta koněm na šachovnici - dána výchozí a cílová pozice, dojít šachovým koněm co nejmenším počtem tahů z výchozího na cílové pole - použití prohledávání do hloubky je velmi nevhodné – backtracking do hloubky až 63, zatímco vždy existuje řešení délky maximálně 6 - postupujeme do šířky: sousední pole k výchozímu označíme 1, jejich sousedy 2, jejich sousedy 3, atd., dokud nedojdeme na cílové pole (číslo = délka nejkratší cesty ze startu) – „algoritmus vlny“ - k nalezení vlastní cesty je nutný ještě „zpětný chod“ (cíl → sousední pole s hodnotou o 1 menší → … → start)
39
program NejkratsiCestaKonem1; {Nalezení nejkratší cesty koněm po šachovnici z daného výchozího na cílové pole. Šíření vlny je řízeno pouze hodnotami na šachovnici. Nalezení cesty zpětným průchodem podle hodnot pole S.} const N = 8; PocetTahu = 8;
{velikost strany čtvercové šachovnice} {počet různých tahů z jednoho pole}
type
{typ indexu na šachovnici}
Index = 1..N;
var S: array[Index, Index] of integer; {šachovnice} Tah: array[1..PocetTahu] of record d1, d2:integer end; {možné tahy koně} Start1, Start2: Index; {souřadnice výchozí pozice koně} Cil1, Cil2: Index; {souřadnice cílové pozice koně} Krok: integer; {pořadové číslo provedeného tahu} Smer: 0..PocetTahu; {směr pohybu koně - index v Tah} i1, i2: Index; {pozice koně} j1, j2: integer; {nová pozice koně z (i1,i2)} begin {program} {inicializace pole tahů koněm:} Tah[1].d1 := 1; Tah[1].d2 := 2; Tah[2].d1 := 2; Tah[2].d2 := 1; Tah[3].d1 := 2; Tah[3].d2 := -1; Tah[4].d1 := 1; Tah[4].d2 := -2; Tah[5].d1 := -1; Tah[5].d2 := -2; Tah[6].d1 := -2; Tah[6].d2 := -1; Tah[7].d1 := -2; Tah[7].d2 := 1; Tah[8].d1 := -1; Tah[8].d2 := 2; {inicializace šachovnice:} write('Počáteční pozice koně: '); readln(Start1, Start2); write('Cílová pozice koně: '); readln(Cil1, Cil2); for i1:=1 to N do for i2:=1 to N do S[i1,i2] := -1; S[Start1,Start2] := 0; {algoritmus vlny:} Krok := 1; while S[Cil1,Cil2] = -1 do {nemáme cestu na cílové pole} begin for i1:=1 to N do for i2:=1 to N do {zkusíme jít z pole (i1,i2)} if S[i1,i2] = Krok-1 then for Smer:= 1 to PocetTahu do {zkusíme pohyb všemi směry}
40
begin j1 := i1 + Tah[Smer].d1; j2 := i2 + Tah[Smer].d2; {nové souřadnice koně} if (j1 >= 1) and (j1 <= N) and (j2 >= 1) and (j2 <= N) then {je uvnitř šachovnice} if S[j1,j2] = -1 then {pole dosud nenavštíveno} S[j1,j2] := Krok {na (j1,j2) dorazila vlna} end; Krok := Krok+1 end; {nalezení cesty zpětným průchodem podle hodnot pole S:} writeln('Nejkratší cesta v obráceném pořadí:'); write('(', Cil1, ',', Cil2, ') '); i1 := Cil1; i2 := Cil2; while (i1 <> Start1) or (i2 <> Start2) do begin Smer := 1; repeat j1 := i1 + Tah[Smer].d1; j2 := i2 + Tah[Smer].d2; {nové souřadnice koně} if (j1 >= 1) and (j1 <= N) and (j2 >= 1) and (j2 <= N) then {je uvnitř šachovnice} if S[j1,j2] = S[i1,i2]-1 then {pole (i1,i2) je přímo dostupné z (j1,j2)} begin i1 := j1; i2 := j2; write('(', i1, ',', i2, ') '); Smer := 0 {už není třeba jít žádným směrem} end else Smer := Smer+1 {zkusíme jiný směr pohybu} else Smer := Smer+1 {zkusíme jiný směr pohybu} until Smer = 0 {už není třeba jít žádným směrem} end; writeln end.
Možnosti realizace: 1. Pole z předchozího kroku vlny (tzn. pole s číslem o 1 menším) nevyhledávat vždy procházením celé šachovnice, ale ukládat si jejich souřadnice navíc do fronty → je třeba paměť navíc, ale urychlí to výpočet při „vlně“ 2. U každého pole na šachovnici si pamatovat nejen minimální počet kroků, které na něj vedou, ale i souřadnice předchozího pole → snadné nalezení předchůdce při zpětném chodu (ale zase je to paměťově i časově náročnější při provádění „vlny“) 41
program NejkratsiCestaKonem2; {Nalezení nejkratší cesty koněm po šachovnici z daného výchozího na cílové pole. Šíření vlny je řízeno pomocí fronty souřadnic polí. Výpis cesty zpětným průchodem podle zaznamenaných hodnot souřadnic předchůdců.} const N = 8; {velikost strany čtvercové šachovnice} PocetPoli = 64; { = N*N } PocetTahu = 8; {počet různých tahů z jednoho pole} type
Index = 1..N; {typ indexu na šachovnici} Souradnice = record s1, s2: Index end; {souřadnice pole na šachovnici}
var S: array[Index, Index] of integer; {šachovnice} Tah: array[1..PocetTahu] of record d1, d2: integer end; {možné tahy koně} Pred: array[Index, Index] of Souradnice; {předchůdci} Fronta: array[1..PocetPoli] of Souradnice; {fronta pro řízení průchodu do šířky} ZacFr, KonFr: integer; {začátek a konec fronty} Start1, Start2: Index; {souřadnice výchozí pozice koně} Cil1, Cil2: Index; {souřadnice cílové pozice koně} Krok: integer; {pořadové číslo provedeného tahu} Smer: 0..PocetTahu; {směr pohybu koně - index v Tah} i1, i2: Index; {pozice koně} j1, j2: integer; {nová pozice koně z (i1,i2)} begin {program} {inicializace pole tahů koněm:} Tah[1].d1 := 1; Tah[1].d2 := 2; Tah[2].d1 := 2; Tah[2].d2 := 1; Tah[3].d1 := 2; Tah[3].d2 := -1; Tah[4].d1 := 1; Tah[4].d2 := -2; Tah[5].d1 := -1; Tah[5].d2 := -2; Tah[6].d1 := -2; Tah[6].d2 := -1; Tah[7].d1 := -2; Tah[7].d2 := 1; Tah[8].d1 := -1; Tah[8].d2 := 2; {inicializace šachovnice a fronty:} write('Počáteční pozice koně: '); readln(Start1, Start2); write('Cílová pozice koně: '); readln(Cil1, Cil2); for i1:=1 to N do for i2:=1 to N do S[i1,i2] := -1; S[Start1,Start2] := 0; ZacFr := 1; KonFr := 1;
42
{výchozí pozice}
Fronta[1].s1 := Start1; Fronta[1].s2 := Start2; {algoritmus vlny:} while S[Cil1,Cil2] = -1 do begin i1 := Fronta[ZacFr].s1; i2 := Fronta[ZacFr].s2; ZacFr := ZacFr+1; Krok := S[i1,i2]+1; for Smer:= 1 to PocetTahu do begin j1 := i1 + Tah[Smer].d1; j2 := i2 + Tah[Smer].d2; if (j1>=1) and (j1<=N) and (j2>=1) and (j2<=N) then if S[j1,j2] = -1 then begin S[j1,j2] := Krok; KonFr := KonFr+1; Fronta[KonFr].s1 := j1; Fronta[KonFr].s2 := j2; Pred[j1,j2].s1 := i1; Pred[j1,j2].s2 := i2 end end; Krok := Krok+1 end;
{nemáme cestu na cílové pole}
{zkusíme jít z pole (i1,i2)} {odebereme ho z fronty} {provedený krok šíření vlny} {zkusíme pohyb všemi směry}
{nové souřadnice koně} {je uvnitř šachovnice} {pole dosud nenavštíveno} {na (j1,j2) dorazila vlna} {vložíme ho do fronty}
{jeho předchůdcem je (i1,i2)}
{výpis cesty zpětným průchodem podle hodnot Pred:} writeln('Nejkratší cesta v obráceném pořadí:'); write('(', Cil1, ',', Cil2, ') '); i1 := Cil1; i2 := Cil2; while (i1 <> Start1) or (i2 <> Start2) do begin j1 := Pred[i1,i2].s1; j2 := Pred[i1,i2].s2; {souřadnice předchůdce} i1 := j1; i2 := j2; write('(', i1, ',', i2, ') '); end; writeln end.
43
Procházení grafu (např. pro určení souvislosti) - v obyčejném neorientovaném grafu projít ze zvoleného výchozího vrcholu všechny dostupné vrcholy - označujeme všechny již navštívené vrcholy, abychom někam nešli dvakrát (abychom nezačali v grafu chodit v cyklu) - můžeme rovnocenně použít průchod do hloubky nebo do šířky, liší se pořadím návštěvy jednotlivých vrcholů, ale oba najdou stejné řešení se stejnou (kvadratickou) časovou i paměťovou složitostí Možnosti realizace: 1. rekurzivní procedura realizující průchod do hloubky 2. zásobník nebo fronta pro řízení průchodu do hloubky resp. do šířky – představují seznam „dluhů“ = čísla těch vrcholů, do nichž jsme při prohledávání už přišli, ale z nichž jsme nezkoušeli jít dál 3. seznam „dluhů“ dokonce nemusí být realizován ani jako zásobník nebo fronta, můžeme z něj vybírat vrchol ke zpracování libovolně (pak průchod grafem neprobíhá do hloubky ani do šířky)
44
8. Metoda „Rozděl a panuj“ - metoda rekurzivního návrhu algoritmu (programu) Problém se rozdělí na dva (příp. více) podproblémy stejného typu, ale menší velikosti, z jejich řešení se pak snadno sestaví řešení původního problému. Každý podproblém je buď už triviální a vyřeší se přímo, nebo se k jeho řešení použije stejný rekurzivní postup. Realizace: rekurzivní procedurou Podmínka rozumné (tj. efektivní) použitelnosti metody: podproblémy vznikající rozkladem jsou na sobě nezávislé (nevyužívají stejné dílčí podúlohy a jejich řešení) Protipříklad: Fibonacciho čísla rekurzivně - řešení úlohy se sice skládalo z řešení podobných menších podúloh, ale ty nebyly na sobě nezávislé → opakované výpočty, velmi neefektivní řešení (exponenciální časová složitost)
Hanojské věže - 3 kolíky označíme A, B, C - na kolíku A je N disků různé velikosti, seřazené od největšího (dole) k nejmenšímu (nahoře) - kolíky B a C jsou prázdné - úkol: přenést všechny disky z kolíku A na kolík B, mohou se průběžně odkládat na kolík C - podmínka: nikdy nesmí ležet na kolíku větší disk na menším, nikdy nesmí zůstat disk mimo tyto tři kolíky
Řešení: definujeme akci PŘENESVĚŽ (N, A, B, C) → můžeme ji provést jedině takto: 1. PŘENESVĚŽ (N-1, A, C, B) 2. přenes disk z A na B 3. PŘENESVĚŽ (N-1, C, B, A)
= přenes N disků z A na B pomocí C
- rekurze - triviální akce - rekurze
Časová složitost: O(2N) – dána charakterem problému, k vyřešení úkolu je vždy nutné provést tolik přesunů.
program Hanoj; var N: integer;
{počet kotoučů}
procedure Prenes(N, A, B, C: integer); {přenese věž N kotoučů z kolíku A na kolík B, přitom využívá kolík C jako pomocný pro odkládání}
45
begin if N > 0 then begin Prenes(N-1, A, C, B); writeln('Přenes kotouč z ', A, ' na ', B); Prenes(N-1, C, B, A) end end; {procedure Prenes} begin write('Počet kotoučů: '); readln(N); Prenes(N, 1, 2, 3) end.
Vyhodnocení aritmetického výrazu metodou Rozděl a panuj Postup: 1. ve výrazu nalézt znaménko, které se při vyhodnocování provádí až jako poslední (zcela mimo závorky, nejnižší priority, z nich co nejvíce vpravo) 2. výraz rozdělit na dva podvýrazy vlevo a vpravo od zvoleného znaménka 3. oba podvýrazy vyhodnotit 4. s výsledky obou podvýrazů vykonat poslední operaci určenou znaménkem Realizace: 1. lineární průchod výrazem zleva doprava (pokud znaménko mimo závorky neexistuje, odstranit z výrazu vnější závorky a zopakovat) 2. triviální akce (konstantní složitosti) 3. buď je podvýraz triviální (konstanta), nebo se vyhodnotí rekurzivním voláním téhož algoritmu 4. triviální akce (konstantní složitosti) Časová složitost: N – délka výrazu (počet znamének) Časová složitost se odvodí podobně jako u quicksortu (viz dále) – záleží na struktuře výrazu - v nejhorším případě O(N 2) - v nejlepším a průměrném případě O(N.log N) program AritmetickyVyraz; {Výraz je zadán na vstupu, obsahuje celočíselné konstanty, binární operátory +,-,*,/ a kulaté závorky. Znak / představuje celočíselné dělení. Obvyklý postup vyhodnocení: podle závorek, podle priorit, operátory stejné priority zleva doprava. Předpoklad: zápis výrazu nemá celkem více než 255 znaků, může být tedy uložen v proměnné typu string.} var S: string;
{zpracovávaný výraz}
46
function Znamenko(var S: string): {Ve výrazu S určí index výskytu prováděného operátoru, přitom z nadbytečné závorky. Není-li v S funkce vrací nulu} var Plus, Krat: integer; Zavorky: integer; i: integer;
integer; znaménka naposledy S odstraní případné vnější už žádné znaménko,
{poloha posledního operátoru} {bilance závorek}
begin Plus := 0; Krat := 0; Zavorky := 0; for i:=1 to length(S) do case S[i] of '(': Zavorky := Zavorky + 1; ')': Zavorky := Zavorky - 1; '+', '-': if Zavorky = 0 then Plus := i; '*', '/': if Zavorky = 0 then Krat := i; end; if Plus > 0 then Znamenko := Plus else if Krat > 0 then Znamenko := Krat else if S[1] <> '(' then Znamenko := 0 else begin S := Copy(S, 2, length(S)-2); {odstranit vnější závorky} Znamenko := Znamenko(S) end end; {function Znamenko} function Hodnota(var S: string): integer; {Určí hodnotu výrazu uloženého v S} var Z: integer; S1, S2: string; H: integer; C: integer;
{poloha znaménka} {levý a pravý úsek od znaménka} {výsledná hodnota} {pomocné pro proceduru Val}
begin Z := Znamenko(S); if Z = 0 then Val(S, H, C) else begin S1 := Copy(S, 1, Z-1); S2 := Copy(S, Z+1, length(S)-Z);
47
case S[Z] of '+': H := Hodnota(S1) '-': H := Hodnota(S1) '*': H := Hodnota(S1) '/': H := Hodnota(S1) end end; Hodnota := H end; {function Hodnota}
+ Hodnota(S2); - Hodnota(S2); * Hodnota(S2); div Hodnota(S2);
begin write('Vyhodnocovaný výraz: '); readln(S); writeln('Hodnota výrazu: ', Hodnota(S)); readln; end.
Quicksort - v průměru nejrychlejší známý třídicí algoritmus - inicializace: tříděným úsekem je celé pole čísel - v tříděném úseku vybrat jednu hodnotu (označme X) - prvky přerovnat tak, aby vlevo byly prvky ≤ X a vpravo prvky ≥ X (lineární časová složitost vzhledem k délce tříděného úseku) - tím se pole rozdělí na dvě části - oba vzniklé úseky setřídit rekurzivním voláním téhož algoritmu (pokud nejsou triviální, tzn. délky 1, příp. 2) - po skončení všech rekurzivních volání je celé pole utříděno Realizace: rekurzivní procedura parametry = indexy v poli vymezující aktuální tříděný úsek volána s parametry (1, N ) program Quicksort_rekursivni; {Třídicí algoritmus Quicksort - rekurzivní verze} const MaxN = 100; {maximální počet tříděných čísel} type Pole = array[1..MaxN] of integer; var P: Pole; N: 1..MaxN; I: integer;
{tříděná čísla}
{uložení tříděných údajů} {počet prvků v poli P}
procedure Quicksort1(var P: Pole; Zac, Kon: integer); {setřídí v poli P úsek od indexu Zac do indexu Kon} var X: integer; {hodnota pro rozdělení na úseky} Q: integer; {pomocné pro výměnu prvků v poli}
48
I, J: integer; {posouvané pracovní indexy v poli} begin I:=Zac; J:=Kon; X:=P[(Zac+Kon) div 2]; {za hodnotu X vezmeme pro jednoduchost prostřední prvek ve zkoumaném úseku} repeat while P[I] < X do I:=I+1; while P[J] > X do J:=J-1; if I < J then {vyměnit prvky s indexy I a J} begin Q:=P[I]; P[I]:=P[J]; P[J]:=Q; I:=I+1; J:=J-1; {posun indexů na další prvky} end else if I = J then {indexy I a J se sešly, oba dva ukazují na hodnotu X} begin I:=I+1; J:=J-1 {posun indexů na další prvky - nutné kvůli ukončení cyklu} end until I > J; {úsek
je rozdělen na úseky a , které zpracujeme rekurzivním voláním procedury:} if Zac < J then Quicksort1(P, Zac, J); if I < Kon then Quicksort1(P, I, Kon); end; {procedure Quicksort1} begin {hlavní program} write('Počet tříděných čísel: '); readln(N); writeln('Zadání posloupnosti tříděných čísel:'); for I:=1 to N do read(P[I]); Quicksort1(P, 1, N); writeln('Setříděná čísla:'); for I:=1 to N do write(P[I]:5); writeln end.
Paměťová složitost: O(N ) třídění probíhá na místě v poli navíc je ale třeba paměť na realizaci rekurzivních volání (zásobník) Časová složitost: nejhorší případ - za X vždy vybereme nejmenší nebo největší prvek v úseku - postupně procházíme úseky délky N, N-1, N-2, …, celkem tedy práce N + (N-1) + (N-2) + … + 1 = N.(N+1)/2 … časová složitost O(N 2) 49
nejlepší případ - za X vždy vybereme prostřední hodnotu (medián) v úseku - procházíme 1 úsek délky N, 2 úseky délky N/2, 4 úseky délky N/4, …, celkem hloubka rekurze log N a na každé hladině rekurze se vykoná práce N (= součet délek K úseků, každý dlouhý N/K prvků) … časová složitost O(N.log N) průměrný případ - lze dokázat, že v průměrném případě má quicksort časovou složitost O(N.log N) jako v nejlepším případě
Realizace bez rekurzivní procedury - použití rekurzivní procedury lze nahradit vlastním zásobníkem - zásobník „dluhů“ = seznam úseků, které je ještě třeba dotřídit - místo rekurzivního volání → vložení úseku do zásobníku - v cyklu se postupně vybírají ze zásobníku jednotlivé dluhy a řeší se (čímž zase vznikají nové, menší dluhy) - pro programátora více práce při psaní programu - výsledný kód může být úspornější * na čas (úspora za režii rekurzivních volání) * na paměť (při dobré organizaci práce stačí zásobník logaritmické výšky) program Quicksort_nerekursivni; {Třídicí algoritmus Quicksort - nerekurzivní verze} const MaxN = 100; MaxNdiv2 = 50; type
{maximální počet tříděných čísel} {= MaxN div 2 (velikost zásobníku)}
Pole = array[1..MaxN] of integer;
{tříděná čísla}
var P: Pole; {uložení tříděných údajů} N: 1..MaxN; {počet prvků v poli P} Zasob: array[1..MaxNdiv2] of record Zac, Kon: integer end; {zásobník úseků čekajících na zpracování} Vrchol: 0..MaxN; {vrchol zásobníku} I: integer; procedure Quicksort2(var P:Pole; Zac, Kon:integer); {setřídí v poli P úsek od indexu Zac do indexu Kon} var X: integer; {hodnota pro rozdělení na úseky} Q: integer; {pomocné pro výměnu prvků v poli} Z, K: integer; {začátek a konec zkoumaného úseku} I, J: integer; {posouvané pracovní indexy v poli} Begin Zasob[1].Zac:=Zac; Zasob[1].Kon:=Kon; Vrchol:=1; {celý tříděný úsek vložen do zásobníku} 50
while Vrchol > 0 do {zásobník je neprázdný} begin Z:=Zasob[Vrchol].Zac; K:=Zasob[Vrchol].Kon; Vrchol:=Vrchol-1; {odebrán jeden úsek ze zásobníku} I:=Z; J:=K; X:=P[(I+J) div 2]; {za hodnotu X vezmeme pro jednoduchost prostřední prvek ve zkoumaném úseku} repeat while P[I] < X do I:=I+1; while P[J] > X do J:=J-1; if I < J then {vyměnit prvky s indexy I a J} begin Q:=P[I]; P[I]:=P[J]; P[J]:=Q; I:=I+1; J:=J-1; {posun indexů na další prvky} end else if I = J then {indexy I a J se sešly, oba dva ukazují na hodnotu X} begin I:=I+1; J:=J-1 {posun indexů na další prvky - nutné kvůli ukončení cyklu} end until I > J; {úsek je rozdělen na úseky a , které vložíme do zásobníku k dalšímu zpracování:} if Z < J then begin Vrchol:=Vrchol+1; Zasob[Vrchol].Zac:=Z; Zasob[Vrchol].Kon:=J end; if I < K then begin Vrchol:=Vrchol+1; Zasob[Vrchol].Zac:=I; Zasob[Vrchol].Kon:=K end end end; {procedure Quicksort2} begin {hlavní program} write('Počet tříděných čísel: '); readln(N); writeln('Zadání posloupnosti tříděných čísel:'); for I:=1 to N do read(P[I]); Quicksort2(P, 1, N); writeln('Setříděná čísla:'); for I:=1 to N do write(P[I]:5); writeln end.
51
9. Stromové struktury Binární strom type Uk = ^Uzel; Uzel = record Info: integer; L, R: Uk end;
{uložená informace} {levý a pravý syn}
kořen
list
NIL
Příklad použití: reprezentace aritmetického výrazu type Uk = ^Uzel; Uzel = record Znam: char; {znaménko + - * /} Hod: real; {hodnota uložená v listu} L, R: Uk {levý a pravý syn} end; - neukládají se závorky (uzávorkování je kódováno strukturou stromu) - je třeba odlišit listy (např. položka Znam = ‘@’)
52
(2 + 5) * (13 - 4)
* + 2
5
13
4
Vyhodnocení aritmetického výrazu reprezentovaného binárním stromem – rekurzívně (metodou Rozděl a panuj): function Vyhodnot(K: Uk): real; {K je ukazatel na kořen stromu} begin with K^ do case Znam of '@': Vyhodnot := Hod; '+': Vyhodnot := Vyhodnot(L) '-': Vyhodnot := Vyhodnot(L) '*': Vyhodnot := Vyhodnot(L) '/': Vyhodnot := Vyhodnot(L) end end;
+ * /
Vyhodnot(R); Vyhodnot(R); Vyhodnot(R); Vyhodnot(R)
Průchod binárním stromem – pomocí rekurze - v každém uzlu provést akci A (např. vypsat hodnotu položky Info) procedure Pruchod(P: Uk); {volat pro P<>nil !} begin ∇ if P^.L <> nil then Pruchod(P^.L); ∇ if P^.R <> nil then Pruchod(P^.R); ∇ end; ∇ = možné místo vyvolání akce A v uzlu P^ - po řadě průchod typu PREORDER INORDER POSTORDER 53
Průchod binárním stromem do hloubky bez rekurze – pomocí zásobníku DO_ZÁSOBNÍKU(Kořen) dokud ZÁSOBNÍK není prázdný P := ZE_ZÁSOBNÍKU AKCE(P) jestliže P^.R <> NIL tak DO_ZÁSOBNÍKU(P^.R) jestliže P^.L <> NIL tak DO_ZÁSOBNÍKU(P^.L) Průchod binárního stromu do šířky (po vrstvách) – pomocí fronty DO_FRONTY(Kořen) dokud FRONTA není prázdná P := Z_FRONTY AKCE(P) jestliže P^.L <> NIL tak DO_FRONTY(P^.L) jestliže P^.R <> NIL tak DO_FRONTY(P^.R)
Binární vyhledávací strom (binary search tree) - datová struktura pro ukládání a vyhledávání dat podle klíče - pro každý uzel platí: všechny záznamy uložené v levém podstromu mají menší klíč všechny záznamy uložené v pravém podstromu mají větší klíč - uvedené vztahy platí pro všechny záznamy v podstromu, nestačí jen pro přímé syny! → při vyhledávání není třeba procházet celý strom, stačí projít jednu cestu od kořene k listu → časová složitost vyhledávání je v nejhorším případě určena výškou stromu Výška H binárního stromu o N uzlech = délka nejdelší cesty z kořenu do listu minimum – vyvážený strom N = 20 + 21 + … + 2H = 2H+1 – 1 maximum – degenerovaný strom H ≈ N v průměrném případě výška O(log N)
→ H ≈ log2N
Hledání hodnoty v BVS function Hledej(P: Uk; H: integer): Uk; {v BVS s kořenem P hledá hodnotu H, vrací odkaz na nalezený uzel, resp. nil} var Sestup: boolean; begin Sestup := P <> nil; while Sestup do begin 54
if H else else if P end; Hledej end;
= P^.Hodnota then Sestup := false if H < P^.Hodnota then P := P^.L {H > P^.Hodnota} P := P^.R; = nil then Sestup := false := P;
Rekurzivní řešení téže funkce: function Hledej(P: Uk; H: integer): Uk; {v BVS s kořenem P hledá hodnotu H, vrací odkaz na nalezený uzel, resp. nil} begin if P = nil then Hledej := nil else if H = P^.Hodnota then Hledej := P else if H < P^.Hodnota then Hledej := Hledej(P^.L, H) else {H > P^.Hodnota} Hledej := Hledej(P^.R, H) end;
Přidání hodnoty do BVS - novou hodnotu musíme přidat tam, kde ji budeme hledat - přidává se vždy do nového listu - postupuje se stejně jako při hledání hodnoty v BVS, dokud se nenarazí na nilový ukazatel a do toho místa se přidá nový uzel - technická realizace: při průchodu stromem od kořene k listu udržovat pomocný ukazatel o jeden krok pozadu, pomocí něj pak připojit do stromu nový uzel - časová složitost je opět dána výškou stromu, v průměrném případě O(log N) Vypuštění hodnoty z BVS - nejprve průchodem od kořene směrem k listu najít uzel s vypouštěnou hodnotou (a jeho předchůdce ve stromě) - pokud je to list, zruší se (v předchůdci nastavit nil) - pokud má jen jednoho následníka, uzel se zruší a jeho následník se přepojí místo něj (předchůdce tedy bude místo na rušený uzel ukazovat na jeho jediného následníka) - pokud má dva následníky, uzel se nemůže fyzicky zrušit, smaže se jen jeho dosavadní hodnota a nahradí se jinou vhodnou hodnotou ze stromu. Tou je buď nejmenší hodnota z pravého podstromu nebo naopak největší hodnota z levého podstromu rušeného uzlu. Tato náhradní hodnota leží jistě v listu nebo v uzlu s jediným následníkem – její původní uzel tedy umíme snadno zrušit. - časová složitost je opět dána výškou stromu, v průměrném případě O(log N) – celkově se prošlo stromem pouze jednou od kořene k listu
55
Vyvážené stromy cíl: zajistit výšku stromu O(log N) → v případě BVS zajištěna časová složitost všech operací O(log N) Dokonale vyvážený binární strom pro každý uzel platí: počet uzlů v jeho levém a pravém podstromu se liší nejvýše o 1 - nejlepší možné vyvážení, výška stromu s N uzly je log N - lze snadno postavit z předem známé množiny hodnot - je obtížné udržovat strom dokonale vyvážený při přidávání a odebírání hodnot → proto se v praxi používají jiné (slabší) definice vyváženosti, strom nebude tak dokonale vyvážený, ale půjde snadněji udržovat AVL – strom (G. M. Adeľson-Velskij, E. M. Landis, 1962) pro každý uzel platí: výška jeho levého a pravého podstromu se liší nejvýše o 1 - slabší požadavek, ale stačí: AVL-strom je maximálně o 45% vyšší než dokonale vyvážený strom se stejným počtem uzlů - každý dokonale vyvážený strom je AVL-stromem - AVL-strom nemusí být dokonale vyvážený Příklad: AVL-strom, který není dokonale vyvážený
56
Postavení dokonale vyváženého binárního stromu s N uzly function DVBS(N: integer): Uk; var S: Uk; begin if N = 0 then DVBS:=nil else begin new(S); S^.L:=DVBS((N-1) div 2); S^.R:=DVBS(N-1 – (N-1) div 2); DVBS:=S end end; Funkce vrací ukazatel na kořen sestrojeného stromu. Info-hodnoty uzlů ve stromu zatím nejsou definovány.
Postavení dokonale vyváženého binárního vyhledávacího stromu s danými N hodnotami v uzlech 1. varianta řešení: - hodnoty nejprve setřídit v poli A[1..N] - postavit dokonale vyvážený binární strom s N uzly pomocí funkce DVBS (hodnoty uzlů zatím nejsou definovány) - projít sestrojený strom metodou inorder a přitom do uzlů stromu postupně zapisovat hodnoty z pole A v pořadí od nejmenší po největší 2. varianta řešení: - hodnoty nejprve setřídit v poli A[1..N] - při konstrukci stromu rovnou vkládat do Info-položek uzlů hodnoty - parametry funkce Strom určují rozsah indexů v poli A – udávají, které hodnoty z pole A patří do příslušného podstromu - funkce bude volána Strom(1, N), vrací ukazatel na kořen sestrojeného stromu function Strom(X, Y: integer): Uk; var S: Uk; begin if X > Y then Strom:=nil else begin new(S); S^.Info:=A[(X+Y) div 2]; S^.L:=Strom(X, (X+Y) div 2 –1); S^.R:=Strom((X+Y) div 2 +1, Y); Strom:=S end end;
57
Obecný strom - dynamická reprezentace 1. známe maximální stupeň větvení type Uk = ^Uzel; Uzel = record Info: integer; {uložená informace} Nasl: array[1..M] of Uk {pole ukazatelů na následníky} end; - v každém uzlu je připraveno M ukazatelů na následníky, z nich několik prvních je využito, ostatní mají hodnotu nil - použitelné, pokud M předem známe a je dostatečně malé
2. obecné řešení type Uk = ^Uzel; UkHrana = ^Hrana; Uzel = record Info: integer; Hr: UkHrana end; Hrana = rekord Nasl: Uk; Dalsi: UkHrana; end;
{uložená informace} {seznam ukazatelů na následníky}
{následník} {další hrana}
- namísto pole ukazatelů se v každém uzlu použije spojový seznam ukazatelů na následníky - heterogenní dynamická datová struktura, jsou v ní provázány uzly dvou typů (Uzel, Hrana) Průchod stromem základní schéma algoritmu: procedure Pruchod(P: Uk); proveď akci v uzlu P^; pro každého následníka uzlu P^ zavolej proceduru Průchod procedure Pruchod(P: Uk); var H: UkHrana; begin write(P^.Info); H:=P^.Hr; while H <> nil do begin Pruchod(H^.Nasl); H:=H^.Dalsi end end;
58
10
NIL 20
30
40
3. kanonická reprezentace - reprezentace obecného stromu binárním stromem type Uk = ^Uzel; Uzel = record Info: integer; Syn, Bratr: Uk end;
{uložená informace} {nejstarší syn, mladší bratr}
- každý uzel ukazuje jen na svého prvního syna (pomocí ukazatele Syn) - všichni synové téhož uzlu jsou navzájem propojeni do spojového seznamu (pomocí ukazatele Bratr) - uzel je list, právě když jeho ukazatel Syn má hodnotu nil
59
Příklad stromu:
1
3
2
5
4
6
7
Uložení v datové struktuře:
1 NIL
2
3
4 NIL
NIL
5
6
7 NIL
NIL
NIL
NIL NIL
60
Graf - dynamická reprezentace je možná, ale není typická - datově stejná jako obecná reprezentace stromů, odpovídá orientovanému grafu - neorientované hrana se reprezentuje dvojicí orientovaných hran vedoucích oběma směry - na rozdíl od stromu nemá graf jeden vstupní bod (kořen) a navíc nemusí být souvislý (resp. silně souvislý) – je třeba nějaká tabulka odkazů na všechny uzly (např. v podobě spojového seznamu, do něhož propojíme všechny uzly grafu) - pro realizaci algoritmu průchodu potřebujeme v každém uzlu navíc jednu položku typu boolean indikující, zda byl při průchodu uzel již navštíven (pro hlídání zacyklení) - v případě ohodnoceného grafu se do záznamu Hrana přidá položka reprezentující ohodnocení hrany Reprezentace grafu type Uk = ^Uzel; UkHrana = ^Hrana; Uzel = record Info: integer; {uložená informace} Hr: UkHrana; {seznam ukazatelů na následníky} Navstiven: boolean; {příznak pro algoritmus průchodu} SpojUzel: Uk; {seznam všech uzlů} end; Hrana = record Nasl: Uk; {následník} Dalsi: UkHrana; {další hrana} Delka: integer {ohodnocení hrany} end; Průchod grafem VSTUP: ukazatel na výchozí vrchol VÝSTUP: vypsat hodnoty všech dostupných vrcholů INICIALIZACE: ve všech uzlech grafu Navstiven = false ALGORITMUS: prohledávání grafu do hloubky procedure Pruchod(P: Uk); var H: UkHrana; begin if not P^.Navstiven then begin write(P^.Info); P^.Navstiven:=true; H:=P^.Hr; while H <> nil do begin Pruchod(H^.Nasl); H:=H^.Dalsi end end end;
61
Vícecestný vyhledávací strom - v každém uzlu je připraven prostor pro uložení K záznamů a K+1 odkazů na syny - může jich tam být uloženo méně, vždy ale klíče uložené v záznamech uzlu tvoří rostoucí posloupnost a synů je o 1 více než záznamů - sousední klíče v uzlu vymezují interval, jaké hodnoty klíčů jsou uloženy v záznamech příslušného podstromu (podle klíče se tedy určuje, ve kterém podstromu se má pokračovat v hledání) - existují techniky vyvažování zajišťující logaritmickou výšku stromu (B-stromy)
62
10. Aritmetické výrazy Notace aritmetického výrazu - průchod binárním stromem reprezentujícím aritmetický výraz (reprezentace aritmetického výrazu viz předchozí kapitola) - v navštívených uzlech vypisujeme uloženou hodnotu (2 + 5) * (13 - 4)
* + 2
5
13
4
průchod preorder → PREFIX průchod inorder → INFIX (bez závorek!) průchod postorder → POSTFIX
* + 2 5 - 13 4 2 + 5 * 13 - 4 2 5 + 13 4 - *
- vždy stejné pořadí operandů – listy stromu procházíme ve všech případech zleva doprava - v prefixovém zápisu operátor bezprostředně předchází své dva operandy, v postfixovém je následuje - v prefixovém a postfixovém zápisu výrazu nejsou závorky, pořadí vyhodnocování je plně určenou strukturou výrazu - inorder průchod stromem vytvořil chybný infixový zápis bez závorek, z něhož není zřejmé pořadí vyhodnocování výrazu Terminologická poznámka: prefix = polská notace (Polish notation) – Łukasiewicz postfix = reverzní polská notace (reverse Polish notataion)
Získání správného infixového zápisu výrazu: procedure Infix(P: Uk); begin if P^.Znam = '@' then write(P^.Hod) else
{list}
63
begin write('('); Infix(P^.L); write(P^.Znam); Infix(P^.R); write(')') end end;
Vyhodnocení výrazu v postfixové notaci - snadné, využití např. u kalkulaček, v překladačích - stačí jeden průchod zápisem výrazu zleva doprava - použijeme zásobník na ukládání číselných hodnot Postup zpracování postfixového zápisu: číslo → vložit do zásobníku znaménko → vyzvednout ze zásobníku horní dvě čísla provést s nimi operaci určenou znaménkem výsledek operace vložit do zásobníku konec → na zásobníku je jediné číslo = hodnota výrazu - pozor na pořadí operandů u nekomutativních operátorů (na vrcholu zásobníku je vždy pravý operand, pod ním levý) - časová i paměťová složitost O(N), kde N je délka výrazu program Postfix1; {Vyhodnoceni celočíselného aritmetického výrazu zapsaného v postfixové notaci. - celý výraz se vejde do jednoho stringu - ve výrazu jsou povoleny jen celočíselné konstanty a binární operátory +, -, *, / (ve významu "div") - zásobník je realizován v poli} const Max = 100; {maximální velikost zásobníku} var S: string; {uložení výrazu v postfixu} Zas: array [1..Max] of integer; {zásobník} V: integer; {vrchol zásobníku} A: integer; {hodnota číselné konstanty} i: integer; {index ve výrazu S} procedure Error(N: byte); begin case N of 1: writeln('Chybný výraz - příliš mnoho znamének'); 2: writeln('Chybný znak v zápisu výrazu'); 3: writeln('Chybný výraz - málo znamének ve výrazu'); end; halt end; 64
begin writeln ('Zadejte výraz v postfixové notaci: '); readln(S); V:=0; i:=1; while i <= length(S) do case S[i] of '0'..'9': begin A:=0; repeat A:=A*10+ord(S[i])-ord('0'); inc(i) until (S[i] < '0') or (S[i] > '9'); inc(V); Zas[V]:=A; end; '+': begin if V < 2 then Error(1); A:=Zas[V-1]+Zas[V]; dec(V); Zas[V]:=A; inc(i) end; '-': begin if V < 2 then Error(1); A:=Zas[V-1]-Zas[V]; dec(V); Zas[V]:=A; inc(i) end; '*': begin if V < 2 then Error(1); A:=Zas[V-1]*Zas[V]; dec(V); Zas[V]:=A; inc(i) end; '/': begin if V < 2 then Error(1); A:=Zas[V-1] div Zas[V]; dec(V); Zas[V]:=A; inc(i) end; ' ': inc(i); else Error(2) end; if V > 1 then Error(3); writeln('Hodnota výrazu: ', Zas[1]); end.
65
Jiný způsob řešení – stejný algoritmus, ale zásobník reprezentován lineárním spojovým seznamem: program Postfix2; {Vyhodnoceni celočíselného aritmetického výrazu zapsaného v postfixové notaci. - celý výraz se vejde do jednoho stringu - ve výrazu jsou povoleny jen celočíselné konstanty a binární operátory +, -, *, / (ve významu "div") - zásobník je realizován lineárním spojovým seznamem} type Uk = ^Uzel; Uzel = record Info: integer; Dalsi: Uk; end; var S: A: i: P:
string; integer; integer; Uk;
{uložení výrazu v postfixu} {hodnota číselné konstanty} {index ve výrazu S} {vrchol zásobníku}
procedure Error(N: byte); begin case N of 1: writeln('Chybný výraz - příliš mnoho znamének'); 2: writeln('Chybný znak v zápisu výrazu'); 3: writeln('Chybný výraz - málo znamének ve výrazu'); end; halt end; procedure Pridej(var P: Uk; X: integer); var Q: Uk; begin new(Q); Q^.Info:=X; Q^.Dalsi:=P; P:=Q; end; function Odeber(var P: Uk): integer; var Q: Uk; begin if P = nil then Error(1); Odeber:=P^.Info; Q:=P; P:=P^.Dalsi; dispose(Q) end;
66
begin writeln('Zadejte výraz v postfixové notaci: '); readln(S); P:=nil; i:=1; while i <= length(S) do case S[i] of '0'..'9': begin A:=0; repeat A:=A*10+ord(S[i])-ord('0'); inc(i) until (S[i] < '0') or (S[i] > '9'); Pridej(P, A); end; '+': begin Pridej(p, Odeber(p)+Odeber(p)); inc(i) end; '-': begin A:=Odeber(P); Pridej(P, Odeber(P)-A); inc(i); end; '*': begin Pridej(P, Odeber(P)*Odeber(P)); inc(i) end; '/': begin A:=Odeber(P); Pridej(P, Odeber(P) div A); inc(i) end; ' ': inc(i); else Error(2) end; writeln ('Hodnota výrazu: ', Odeber(P)); if P <> nil then Error(3); end.
67
Vyhodnocení výrazu v prefixové notaci 1. možnost: průchod výrazem odzadu, postup jako u postfixu 2. možnost: - jeden průchod zápisem výrazu zleva doprava - zásobník na ukládání znamének a číselných hodnot Postup zpracování prefixového zápisu odpředu: - znaménko nebo číslo → vložit do zásobníku - když se na vrcholu zásobníku sejdou dvě čísla → vyzvednout je ze zásobníku, dále vyzvednout znaménko uložené pod nimi, provést s čísly operaci určenou znaménkem a výsledek operace vložit do zásobníku (což může opětovně vyvolat tentýž proces vyhodnocení) - konec → na zásobníku je jediné číslo = hodnota výrazu - pozor na pořadí operandů u nekomutativních operátorů (na vrcholu zásobníku je vždy pravý operand, pod ním levý) - časová složitost O(N), kde N je délka výrazu
Převod z infixu do postfixu - jeden průchod zápisem výrazu zleva doprava, časová složitost O(N) - použijeme zásobník na ukládání znamének - v postfixovém zápisu jsou čísla ve stejném pořadí jako v infixovém, znaménka je třeba pozdržet na zásobníku Postup zpracování infixového zápisu: Číslo → zapsat přímo na výstup levá závorka → vložit do zásobníku pravá závorka → ze zásobníku postupně přenést na výstup všechna znaménka až k nejbližší uložené levé závorce, pak levou závorku ze zásobníku i pravou závorku ze vstupu zrušit znaménko → vložit do zásobníku předtím ale ze zásobníku postupně přenést na výstup všechna znaménka vyšší nebo stejné priority, nejvýše ale k první uložené levé závorce konec → ze zásobníku přenést na výstup všechna zbývající znaménka program In2Post; {Program převádí aritmetický výraz z infixové do postfixové notace. Předpokládá, že se výraz vejde do stringu (má maximálně 255 znaků). Program nekontroluje syntaktickou správnost, předpokládá správný výraz. Ve výrazu jsou povoleny celočíselné konstanty, binární Operátory +, -, *, / a závorky s libovolnou úrovní zanoření.} var S, Z: V: I:
T: string; array[1..128] of char; byte; byte;
{infix, postfix} {zásobník} {vrchol zásobníku Z} {pozice v infixu S}
68
begin write('Výraz v infixu: I:=1; T:=''; V:=0;
'); readln(S);
while I <= length(S) do case S[I] of '(': begin {do zásobníku} inc(V); Z[V]:=S[I]; inc(I) end; ')': begin {ze zásobníku na výstup všechno až k levé závorce} while Z[V] <> '(' do begin T:=T+Z[V]; dec(V) end; dec(V); {odstranit levou závorku ze zásobníku} inc(I) end; '+', '-': begin {nejprve ze zásobníku na výstup operátory stejné nebo vyšší priority, pak vložit} while (V > 0) and ((Z[V] = '+') or (Z[V] = '-') or (Z[V] = '*') or (Z[V] = '/')) do begin T:=T+Z[V]; dec(V) end; inc(V); Z[V]:=S[I]; inc(I) end; '*', '/': begin {nejprve ze zásobníku na výstup operátory stejné priority, pak vložit do zásobníku} while (V > 0) and ((Z[V] = '*') or (Z[V] = '/')) do begin T:=T+Z[V]; dec(V) end; inc(V); Z[V]:=S[I]; inc(I) end; else {číslo} begin {rovnou na výstup, po sobě jdoucí čísla oddělit mezerou} if (T <> '') and (T[length(T)] >= '0') and (T[length(T)] <= '9') then T:=T+' '; while (I <= length(S)) and (S[I] >= '0') and (S[I] <= '9') do begin T:=T+S[I]; inc(I) end; end end; {case} while V > 0 do {ještě je něco v zásobníku} begin T:=T+Z[V]; dec(V) end; {while V>0} writeln('Výraz v postfixu: ', T) end.
69
Vyhodnocení výrazu v infixové notaci - spojení obou předchozích algoritmů: * převod výrazu z infixu do postfixu v čase O(N) * vyhodnocení postfixové notace v čase O(N) → celková časová i paměťová složitost O(N) - obě fáze výpočtu se mohu provádět * buď postupně (s uložením vytvořené postfixové notace výrazu do znakového řetězce) * nebo souběžně (vznikající postfixová notace se neukládá, ale rovnou průběžně vyhodnocuje) → algoritmus používá dva zásobníky – jeden na znaménka a druhý na čísla
Postavení binárního stromu ze zápisu výrazu postfixová nebo prefixová notace → algoritmus podobný jako při vyhodnocování výrazu, do zásobníku se vždy ukládá ukazatel na nově alokovaný uzel a místo provádění operací se uzly s operandy zapojují pod uzel s operátorem jako jeho synové infixová notace → nejprve převedeme na postfixovou notaci
70
11. Metody ukládání a vyhledávání dat Shrnutí dříve probíraných metod uložení dat data = záznamy s klíčem, podle kterého vyhledáváme - pole: vyhledávání O(N), vkládání O(1) - uspořádané pole: binární vyhledávání O(log N), vkládání O(N) - lineární spojový seznam: vyhledávání O(N), vkládání O(1) stejná složitost jako v poli - uspořádaný LSS: vyhledávání O(N), vkládání O(N) průchod seznamem lze předčasně ukončit - binární vyhledávací strom: všechny operace v průměru O(log N), v nejhorším případě O(N) nebo je nutno strom vyvažovat - vícecestný vyhledávací strom
Přímé indexování pole klíčem - všechny operace mají složitost O(1), klíč musí být ordinální hodnota z předem známého malého rozsahu
Hešování - transformace klíče do předem známého menšího rozsahu ordinálních hodnot, jimiž lze indexovat pole klíč → hešovací funkce → index v poli (hešovací tabulka) rozsah možných klíčů bývá výrazně větší než rozsah přípustných indexů – např. klíč je rodné číslo člověka, pro uložení několik set lidí stačí pole indexované 0..999 ⇒ hešovací funkce nebývá prostá ⇒ vznikají kolize (více záznamům je přidělen stejný index v poli) 1. Minimalizace počtu kolizí: dobrá rovnoměrně rozptylující hešovací funkce, dostatečný rozsah indexů vzhledem k počtu ukládaných záznamů (zaplněnost hešovací tabulky do 90%) 2. Řešení kolizí: oblast přetečení nebo sekundární transformace klíče
Třídění čísel v poli = vnitřní třídění (řazení) Úkol: uspořádat prvky pole podle velikosti (od nejmenšího po největší). Přímé metody - jednoduchý zápis programu - časová složitost O(N 2) → vhodné jen pro malá data - třídí „na místě“ (tzn. nepotřebují další datovou strukturu velikosti N)
71
Efektivnější metody - rekurzivní quicksort a mergesort, třídění haldou (heapsort) - časová složitost O(N log N) Třídění haldou (heapsort) - postavit z čísel v poli haldu – čas O(N log N) postupným přidáváním prvků – nebo čas O(N) při stavbě odspodu - haldu rozebrat opakovaným odebíráním minima – čas O(N log N) → celková časová složitost O(N log N) ve všech případech - lze provádět na místě v jednom poli (kde byla původní data) → paměťová složitost O(N) Rekurzivní metody - složitější zápis programu, technika „Rozděl a panuj“ - v průměrném případě optimální časová složitost O(N.log N), Quicksort může mít v nejhorším případě složitost O(N 2) - Quicksort třídí „na místě“, Mergesort potřebuje další pole velikosti N, oba algoritmy navíc potřebují paměť na realizaci rekurze (tzn. systémový zásobník nebo vlastní zásobník v případě odstranění rekurzivních volání)
Dolní odhad složitosti problému třídění Vstupní data pro úlohu třídění - jistá posloupnost N čísel (klíčů), čísla mohou být navzájem různá - proto existuje až N! možných uspořádání vstupních dat velikosti N Obecný problém třídění o vstupních datech nic nevíme, není předem omezen rozsah hodnot, mohou to být čísla typu real (tzn. nelze jimi indexovat) → při třídění můžeme čísla jedině vzájemně porovnávat Strom všech možných průběhů výpočtu nějakého třídicího algoritmu pro vstupní data velikosti N: - kořen = počáteční stav - binární strom, větvení = porovnání nějakých dvou čísel (existují dva možné výsledky porovnání) - listy stromu = konec výpočtu (data setříděna) Pro každá vstupní data se musí průběh výpočtu někde odlišit od ostatních → strom má N! listů. Výška stromu výpočtů h = počet provedených porovnání čísel při nejdelším výpočtu = časová složitost algoritmu v nejhorším případě
72
Výška úplného binárního stromu se všemi K listy na poslední hladině je log2K. Jiný binární strom s K listy musí mít výšku větší. Uvažovaný strom všech možných výpočtů má tedy výšku h ≥ log2(N!). Časová složitost libovolného třídicího algoritmu nemůže být proto lepší než log2(N!), tedy než O(N.log N) – dokážeme třeba podle Stirlingovy formule. Známe konkrétní třídicí algoritmy s časovou složitostí O(N.log N), např. heapsort nebo mergesort, proto O(N.log N) je i složitost obecného problému vnitřního třídění v nejhorším případě.
Přihrádkové třídění Předpoklady: - třídíme hodnoty (resp. záznamy s klíči) z předem známého rozsahu D..H - rozsah D..H není příliš velký, takže lze v programu deklarovat pole indexované D..H Pak lze problém třídění řešit s lineární časovou složitostí přihrádkovým tříděním. Varianty: - třídění počítáním (Counting sort) - třídění rozdělováním (Bucket sort) - víceprůchodové třídění rozdělováním (Radix sort)
Counting sort - třídíme pouze celá čísla Realizace: 2 pole A – tříděné pole čísel [1..N] C – pomocné pole celých čísel [D..H] = čítače výskytů jednotlivých hodnot - projdeme pole A a do pole C spočítáme počty výskytů jednotlivých hodnot - projedeme pole C a z uložených hodnot vytvoříme nový obsah pole A
Bucket sort - třídíme celé záznamy podle zvoleného klíče Realizace: 3 pole A – původní pole záznamů [1..N] B – pole setříděných záznamů [1..N] C – pole celých čísel [D..H] * nejprve velikosti přihrádek pro prvky s daným klíčem * potom index v poli B, kde příslušná přihrádka končí * dále index posledního volného místa v přihrádce
73
type Pole = array[1..N] of record klic: integer; {cosi dalšího ...} end; procedure PrihradkoveTrideni(var A: Pole); var B: Pole; {setříděné záznamy} C: array[D..H] of integer; {hranice přihrádek} I, K: integer; Begin {Velikosti přihrádek:} for I := D to H do C[I] := 0; {všechny přihrádky prázdné} for I := 1 to N do begin K := A[I].klic; C[K] := C[K] + 1 {počty výskytů jednotlivých klíčů} end; {Konce přihrádek:} for I := D+1 to H do C[I] := C[I] + C[I-1]; {C[I] = index, kde budou končit v setříděném poli B záznamy s klíčem I} {Zařazení záznamů do přihrádek:} for I := N downto 1 do {záznamy bereme odzadu pro zajištění stability!} begin K := A[I].klic; B[C[K]] := A[I]; C[K] := C[K] –1 {index posledního volného místa v přihrádce} end; {Předání setříděného pole ven:} A := B end; {procedure PrihradkoveTrideni}
Paměťová složitost pole velikosti 1..N a pole velikosti D..H
→ O(N + (H-D))
Časová složitost dva for-cykly délky N a dva for-cykly délky H-D
→ O(N + (H-D))
Algoritmus má tedy časovou i paměťovou složitost lineární, ale nejen vzhledem k počtu záznamů N, nýbrž i k přípustnému rozsahu indexů H-D
74
Radix sort - přihrádkové třídění víceprůchodové - je-li rozsah hodnot D..H příliš velký na deklaraci pole, např. záznamů je sice jen několik stovek, ale klíčem je libovolné šesticiferné číslo → potřebovali bychom pole velké 1.000.000 Řešení: - klíč rozdělíme např. na dvě trojciferné (nebo na tři dvojciferné) části - provedeme nejprve přihrádkové třídění celého pole podle dolní (méně významné) trojice cifer - v další fázi setřídíme celé pole přihrádkovým tříděním podle horní (významnější) trojice cifer Díky stabilitě přihrádkového třídění (při jeho vhodné realizaci) se při závěrečné fázi zachová uspořádání záznamů získané v předchozích fázích výpočtu.
Nalezení K-tého nejmenšího prvku z daných N čísel (1 ≤ K ≤ N)
speciální případ: K = N / 2 … medián 1. Setřídit čísla v poli A výsledek: A[K]
O(N.log N)
2. Postavit z čísel v poli A haldu z ní K-krát odebrat minimum celkem časová složitost
O(N) O(K.log N) O(N + K.log N)
3. Modifikace Quicksortu - po rozdělení úseku pole pracujeme dál jen s tou částí, ve které je hledaný prvek, druhou část už není třeba dotřídit - volba správné části: ta, v níž leží index K (určí se podle toho, zda je velikost levé části větší než K) - výsledek výpočtu: prvek A[K] - při realizaci není třeba rekurze ani zásobník na její odstranění, jediné rekurzivní volání se snadno nahradí jednoduchým cyklem Časová složitost - v nejhorším případě: provede se plný quicksort (jeho nejhorší případ), tedy složitost O(N 2) - v nejlepším případě (půlení): procházejí se po řadě úseky délky N, N/2, N/4, …, 1, vykonaná práce = součet jejich délek se blíží k 2N, tedy časová složitost algoritmu O(N) - v průměrném případě rovněž O(N)
program K_ty_nejmensi; {Nalezení K-tého nejmenšího prvku metodou založenou na modifikaci třídicího algoritmus Quicksort} const MaxN = 100;
{maximální počet zpracovávaných čísel}
75
type Pole = array[1..MaxN] of integer; var P: Pole; N: 1..MaxN; I, K: integer;
{uložení čísel}
{uložení tříděných údajů} {počet prvků v poli P}
function NaleztKty(var P:Pole; Zac, Kon, K:integer): integer; {v poli celých čísel P v úseku od indexu Zac do indexu Kon vyhledá K-té nejmenší číslo a vrátí ho jako funkční hodnotu} var X: integer; {hodnota pro rozdělení na úseky} Q: integer; {pomocné pro výměnu prvků v poli} I, J: integer; {posouvané pracovní indexy v poli} begin while Zac < Kon do begin X:=P[K]; {jedna možná volba, lze i jinak} I:=Zac; J:=Kon; repeat while P[I] < X do I:=I+1; while P[J] > X do J:=J-1; if I < J then {vyměnit prvky s indexy I a J} begin Q:=P[I]; P[I]:=P[J]; P[J]:=Q; I:=I+1; J:=J-1; {posun indexu na další prvky} end else if I = J then {indexy I a J se sešly, oba dva ukazují na hodnotu X} begin I:=I+1; J:=J-1 {posun indexu na další prvky - nutné kvůli ukončení cyklu} end until I > J; {úsek je rozdělen na úseky a } if K < I then Kon:=J; {dál budeme hledat v levém úseku} if K > J then Zac:=I; {dál budeme hledat v pravém úseku} end; NaleztKty:=P[K] end; {function NaleztKty} begin {hlavní program} write('Počet zpracovávaných čísel: '); readln(N); writeln('Zadání posloupnosti zpracovávaných čísel:'); for I:=1 to N do read(P[I]); write('Kolikátý prvek nalézt?: '); readln(K); writeln('Nalezen ', K, '-tý nejmenší prvek: ', NaleztKty(P, 1, N, K)); writeln end.
76
4. Lineární algoritmus - obdobný postup jako v případě modifikovaného quicksortu, jenom hodnotu X, podle níž rozdělujeme prvky v poli, nevolíme náhodně, ale nějak chytře, aby byla natolik blízká mediánu, že nám zaručí lineární časovou složitost i v nejhorším případě (ale nebude to přesně medián).
77
12. Grafové algoritmy Grafy - vrcholy (N), hrany (M) - každá hrana spojuje právě dva vrcholy - nadále předpokládejme, že vrcholy jsou očíslovány od 1 do N - M je rovno nejvýše N.(N-1)/2 – úplný graf, bez multihran Rozlišujeme graf a nakreslení grafu – dvě různá nakreslení téhož grafu:
5 1
4
2
2 5
1
3
4
3
Vybrané základní pojmy graf
- neorientovaný - orientovaný - obecný (smíšený – může mít orientované i neorientované hrany)
graf
- neohodnocený - ohodnocený (hranově nebo vrcholově, my zde pracujeme s hranovým ohodnocením)
multihrana – více hran spojujících stejnou dvojici vrcholů (my zde nebudeme uvažovat) smyčka – hrana vedoucí z vrcholu do téhož vrcholu sled z vrcholu x do vrcholu y (libovolná opakování vrcholů i hran) tah z vrcholu x do vrcholu y (hrany se neopakují, vrcholy mohou) cesta z vrcholu x do vrcholu y (neopakují se ani vrcholy) vzdálenost vrcholů = délka nejkratší cesty mezi nimi - v neohodnoceném grafu minimalizujeme počet hran, které cestu tvoří - v ohodnoceném grafu minimalizujeme součet ohodnocení hran tvořících cestu uzavřený sled – uzavřený tah – kružnice (uzavřená cesta)
78
Souvislost grafu neorientovaný graf: souvislý graf – mezi každými dvěma vrcholy v něm existuje cesta komponenta souvislosti = maximální souvislá část grafu orientovaný graf: slabě souvislý – jeho symetrizací (tj. zrušením orientace hran) vznikne souvislý graf slabé komponenty silně souvislý – jeho každé dva vrcholy jsou oboustranně dosažitelné silné komponenty
Orientovaný graf je acyklický = neobsahuje cyklus, tj. orientovanou kružnici (smyčku nepokládáme za cyklus) tzn. všechny silné komponenty jsou jednobodové
Topologické uspořádání orientovaného grafu = očíslování vrcholů tak, že pro každou hranu i → j platí i ≤ j Orientovaný graf je acyklický, právě když má topologické uspořádání.
Strom = souvislý neorientovaný graf bez cyklů - mezi každými dvěma vrcholy existuje právě jedna cesta - strom s N vrcholy má vždy přesně N-1 hran
Poznámka: Jeden libovolný vrchol můžeme prohlásit za kořen a všem hranám přiřadit orientaci směrem od kořene → zakořeněný strom (těm jsme dosud říkali „stromy“).
79
Kostra grafu = souvislý podgraf obsahující všechny vrcholy grafu a co nejméně hran (tzn. N-1 hran) - kostra je stromem, který obsahuje všechny vrcholy původního grafu a některé hrany Hranově ohodnocený graf: minimální kostra = ta z koster, v níž je součet ohodnocení hran co nejmenší - nemusí být jednoznačná
6 4
4 4
9
3
3
5 7
Minimální kostra grafu na obrázku má součet ohodnocení hran 20, není jednoznačná (existují dvě různé takové minimální kostry).
Reprezentace grafu v programu 1. Matice sousednosti = čtvercová matice velikosti N x N A[ i, j ] = 0 / 1 právě když neexistuje / existuje hrana (i, j) neorientovaný graf – symetrická matice orientovaný graf – obecně není symetrická ohodnocený graf – A[ i, j ] = ohodnocení hrany (i, j) → matice vzdáleností (zvláštní pro ten účel vyčleněná hodnota potom kóduje, že příslušná hrana neexistuje) Určení všech sousedů daného vrcholu grafu v této reprezentaci: N operací (je třeba projít celý řádek matice) Vhodné použití: pro grafy s malým počtem vrcholů a přitom s relativně velkým počtem hran Kdy nevyhovuje: graf s velkým počtem vrcholů a relativně málo hranami (např. silniční síť nějakého regionu) - matice je rozsáhlá (paměťově náročná) a přitom v ní jsou uloženy skoro samé nuly - také při hledání sousedů daného vrcholu se musí přes všechny ty nuly procházet (pomalé) Řešení: použít jinou reprezentaci grafu
80
2. Seznamy následníků - u každého vrcholu je uložen seznam čísel vrcholů, do nichž odsud vede hrana - primárně určeno pro orientované grafy, neorientovaná hrana se nahradí dvojicí orientovaných (tam a zpět) - pro ohodnocený graf: s číslem cílového vrcholu se ukládá i ohodnocení hrany Realizace: a) matice N x N-1 (z každého vrcholu může vést až N-1 hran) + jednorozměrné pole délky N (udává počet hran vycházejících z jednotlivých vrcholů) → paměť se tím neušetří, čas na procházení všech následníků ano b) matice N x R – když víme, že z každého vrcholu vede maximálně R hran Např. N=1000 měst, z každého vede nejvýše R=10 silnic … stačí matice 1000 x 10 místo dosavadní 1000 x 1000 → výrazná paměťová úspora c) jednorozměrné pole N ukazatelů na lineární spojové seznamy, do nichž ukládáme čísla následníků jednotlivých vrcholů → alokace paměti přesně potřebné délky (ale nevýhody plynoucí z použití dynamicky alokované datové struktury) d) nemáme omezení R platné pro každý vrchol, ale celkově je v grafu nejvýše M hran - princip „vzájemné solidarity“ vrcholů – čísla následníků všech vrcholů se ukládají do jednoho společného pole E V: array [1..N+1] of word; E: array [1..M] of word;
{pro každý vrchol index do pole E, kde začínají jeho následníci} {čísla vrcholů}
Následníci vrcholu u jsou zapsáni v poli E na pozicích od indexu V[u] do indexu V[u+1]-1
3. Seznam hran - jednorozměrné pole délky M nebo lineární spojový seznam - každý záznam odpovídá jedné hraně grafu – uložena čísla koncových vrcholů a případně také ohodnocení hrany - lze použít pro orientované i neorientované grafy var Hrany: array [1..M] of record Odkud, Kam: word; { Hodnota: real } end; Vhodné použití: algoritmy založené na postupném zpracování všech hran grafu (např. hledání kostry grafu). Nevhodné: algoritmy vyžadující určení všech sousedů daného vrcholu – časová složitost O(M).
81
4. Matice incidence = matice velikosti M x N (hrany x vrcholy) neorientovaný graf – stačí matice typu boolean: A[ h, u ] = 0 právě když vrchol u neleží na hraně h A[ h, u ] = 1 právě když vrchol u leží na hraně h orientovaný graf – rozlišíme orientaci hran: A[ h, u ] = +1 právě když hrana h vede z vrcholu u A[ h, u ] = -1 právě když hrana h vede do vrcholu u hranově ohodnocený graf: A[ h, u ] přímo udává ohodnocení hrany Prakticky použitelné jen pro velmi řídké grafy (méně hran než vrcholů), jinak paměťově i časově neefektivní. Má význam spíše jen v teorii grafů (např. pro některé důkazy).
Základní grafové problémy a algoritmy 1. určení souvislosti neorientovaného grafu, resp. nalezení komponent souvislosti neorientovaného grafu - algoritmus založený na postupném prohledávání grafu (do hloubky nebo do šířky) a barvení komponent - algoritmus založený na postupném zpracování všech hran a vytváření faktorových množin (tj. komponent souvislosti) program Souvislost; {Určení komponent souvislosti v neorientovaném grafu} const MaxVrch = 100; MaxVrchPlus1 = 101; MaxHran = 1000; MaxHranPlus1 = 1001;
{max. přípustný počet vrcholů} {MaxVrch+1} {max. přípustný počet hran} {MaxHran+1}
var V: array[1..MaxVrchPlus1] of 1..MaxHranPlus1; E: array[1..MaxHran] of 1..MaxVrch; {uložení grafu ve tvaru seznamu následníků} Komponenta: array[1..MaxVrch] of integer; {pro každý vrchol číslo jeho komponenty} Zasobnik: array[1..MaxVrch] of 1..MaxVrch; {zásobník vrcholů pro další zpracování} Vrchol: 0..MaxVrch; {vrchol zásobníku} Navstiven: 0..MaxVrch; {počet navštívených vrcholů} N: 1..MaxVrch; {počet všech vrcholů grafu} Barva: integer; {barva vytvářené komponenty} Zacatek: 1..MaxVrch; {nejmenší vrchol komponenty} i, j: integer;
82
begin {Načtení vstupních dat} write('Počet vrcholů grafu: '); readln(N); writeln('Po řádcích následníci jednotlivých vrcholů', ' od 1 do ', N, ':'); V[1]:=1; j:=1; for i:=1 to N do begin while not eoln do {následníci vrcholu číslo i} begin read(E[j]); j:=j+1 end; readln; V[i+1]:=j end; {Inicializace} for i:=1 to N do Komponenta[i]:=0; Barva:=0; Zacatek:=1; Navstiven:=0;
{žádný vrchol ještě není zařazen}
{Hledání komponent} while Navstiven <> N do {existuje nenavštívený vrchol} begin Barva:=Barva+1; {další komponenta souvislosti} while Komponenta[Zacatek] <> 0 do Zacatek:=Zacatek+1; Vrchol:=1; Zasobnik[1]:=Zacatek; {začátek další komponenty} Komponenta[Zacatek]:=Barva; Navstiven:=Navstiven+1; while Vrchol > 0 do {zásobník není prázdný} begin j:=Zasobnik[Vrchol]; Vrchol:=Vrchol-1; {odebrat vrchol zásobníku} for i:=V[j] to V[j+1]-1 do if Komponenta[E[i]]=0 then {následník E[i] nenavštíven} begin Komponenta[E[i]]:=Barva; Vrchol:=Vrchol+1; Zasobnik[Vrchol]:=E[i]; Navstiven:=Navstiven+1 end end end;
83
{Výpis výsledku} writeln('Komponenty souvislosti daného grafu jsou tvořeny ', 'těmito vrcholy'); writeln(' (na každém řádku jedna komponenta):'); for j:=1 to Barva do begin for i:=1 to N do if Komponenta[i]=j then write(i:5); writeln end end.
2. existence kružnice v neorientovaném grafu - určíme komponenty souvislosti grafu, v každé komponentě souvislosti spočítáme hrany a zjistíme tak, zda je to strom - algoritmus založený na postupném zpracování všech hran a vytváření faktorových množin (tj. komponent souvislosti): když některá hrana spojuje vrcholy téže komponenty, v grafu existuje kružnice 3. nalezení kostry v neorientovaném grafu - algoritmus založený na postupném zpracování všech hran a vytváření faktorových množin (tj. komponent souvislosti): do kostry zařadíme každou hranu, která způsobí sjednocení dvou faktorových množin, tzn. její koncové vrcholy dosud ležely v různých komponentách souvislosti (přidáním této hrany do kostry tedy nevznikne kružnice) 4. nalezení minimální kostry v neorientovaném ohodnoceném grafu - stejný algoritmus jako v předchozím případě, jenom hrany nejprve seřadíme podle jejich ohodnocení a procházíme je od nejkratší po nejdelší (tzn. hladový algoritmus)
program MinimalniKostra; {Určení minimální kostry souvislého ohodnoceného neorientovaného grafu} const MaxVrch = 100; MaxHran = 1000;
{maximální počet vrcholů grafu} {maximální počet hran grafu}
type Hrana = record V1, V2: integer; Delka: integer end;
{spojené vrcholy} {ohodnocení hrany}
var Graf: array[1..MaxHran] of Hrana; {uložení grafu} Komponenta: array[1..MaxVrch] of integer; {komponenty} N: 1..MaxVrch; {skutečný počet vrcholů grafu} PomHrana: Hrana; K1, K2: integer; S, I, J, K: integer;
84
begin {Načtení vstupních dat} write('Počet vrcholů grafu: '); readln(N); writeln('Hrany grafu: ODKUD KAM DELKA'); S:=0; while not eof do begin S:=S+1; {počet všech hran grafu} with Graf[S] do read(V1, V2, Delka) end; {Setřídění hran podle velikosti od nejkratší k nejdelší - pro jednoduchost zde použijeme jednoduchý třídicí algoritmus třídění přímým výběrem:} for I:=1 to S-1 do begin K:=I; for J:=I+1 to S do if Graf[J].Delka < Graf[K].Delka then K:=J; if K <> I then begin PomHrana:=Graf[K]; Graf[K]:=Graf[I]; Graf[I]:=PomHrana end end; {Vlastní určení minimální kostry grafu - nalezená kostra se neukládá, přímo se vypisuje:} writeln; writeln('Hrany tvořící minimální kostru grafu:'); for I:=1 to N do Komponenta[I]:=I; {počáteční jednoprvkové komponenty souvislosti} I:=0; K:=0; {počet hran zařazených do kostry} while K < N-1 do begin I:=I+1; {zkoumaná hrana} K1:=Komponenta[Graf[I].V1]; K2:=Komponenta[Graf[I].V2]; if K1 <> K2 then {hranu I zařadíme do kostry} begin K:=K+1; writeln(Graf[I].V1:5, Graf[I].V2:5); for J:=1 to N do if Komponenta[J] = K2 then Komponenta[J]:=K1 end end end.
85
5. určení, zda je neorientovaný graf bipartijní = vrcholy je možné rozdělit do dvou skupin tak, aby každá hrana grafu spojovala vždy dvojici vrcholů patřících do různých skupin - algoritmus založený na postupném prohledávání grafu (do hloubky nebo do šířky) a barvení vrcholů střídavě dvěma barvami tak, aby sousední vrcholy měly vždy různou barvu
program BipartitniGraf; {Rozdělení měst do dvou skupin - bipartitní graf} const MaxN=100;
{maximální možný počet měst}
var A: array[1..MaxN, 1..MaxN] of boolean; {matice silnic} Barva: array[1..MaxN] of -1..1; {rozdělení měst} Zasob: array[1..MaxN] of 1..MaxN; {pracovní seznam měst} Vrchol: 0..MaxN; {index posledního prvku seznamu} N: 1..MaxN; {skutečný počet měst} Zarazena: integer; {počet měst zařazených do skupin} Konflikt: Boolean; {města nelze rozdělit} i, j: integer; begin {Inicializace proměnných a načtení vstupních dat} write('Počet měst: '); readln(N); for i:=1 to N do begin for j:=1 to N do A[i,j]:=false; Barva[i]:=0 end; write('Seznam všech silnic'); writeln(' - dvojice čísel měst ODKUD a KAM vede:'); while not eof do begin read(i,j); A[i,j]:=true; A[j,i]:=true {silnice jsou obousměrné} end; {Rozdělování měst} Zasob[1]:=1; {výchozí město} Vrchol:=1; {v seznamu zařazených je zatím samo} Barva[1]:=1; {zařazeno do skupiny 1} Zarazena:=1; {jedno město je zařazeno} Konflikt:=false; while (Vrchol > 0) and not Konflikt do begin j:=Zasob[Vrchol]; {odebrat číslo ze zásobníku} Vrchol:=Vrchol-1; for i:=1 to N do
86
if A[i,j] then {vede silnice z j do i} if Barva[i]=0 then begin {obarvit město i} Barva[i]:=-Barva[j]; Vrchol:=Vrchol+1; Zasob[Vrchol]:=i; Zarazena:=Zarazena+1 {další město zařazeno} end else if Barva[i] = Barva[j] then Konflikt:=true; {došlo ke kolizi - nelze rozdělit} if (Vrchol = 0) and (not Konflikt) and (Zarazena < N) then begin {Zásobník je prázdný, ale ještě nebyla obarvena všechna města ani nedošlo ke konfliktu. Libovolné dosud nezařazené město můžeme zařadit do kterékoliv skupiny -> první dosud nezařazené dáme do skupiny 1} j:=1; while Barva[j] <> 0 do j:=j+1; Zasob[1]:=j; {nově zařazené město} Vrchol:=1; {v seznamu zařazených je samo} Barva[j]:=1; {zařazeno do skupiny 1} Zarazena:=Zarazena+1; {další město je zařazeno} end end; {Vyhodnocení procesu rozdělování měst} if Konflikt then writeln('Rozdělení měst do dvou skupin neexistuje.') else begin writeln('Rozdělení měst do dvou skupin je možné.'); writeln('Jedno takové přípustné rozdělení vypadá takto:'); write('1.skupina:'); for i:=1 to N do if Barva[i] = 1 then write(i:3); writeln; write('2.skupina:'); for i:=1 to N do if Barva[i] = -1 then write(i:3); writeln end end.
6. topologické uspořádání orientovaného grafu = očíslování vrcholů tak, že pro každou hranu i → j platí i < j - algoritmus založený na postupném odebírání těch vrcholů, do nichž nevede žádná hrana – topologické třídění (podrobněji viz dále)
87
7. zjištění, zda je orientovaný graf acyklický = neobsahuje cyklus (tj. orientovanou kružnici) - orientovaný graf je acyklický právě tehdy, když se dá topologicky uspořádat - stejný algoritmus jako v předchozím případě, pokusíme se graf topologicky uspořádat 8. nalezení nejkratší cesty v neohodnoceném grafu nejkratší cesta z vrcholu u do vrcholu v = cesta z u do v tvořená co nejmenším počtem hran - algoritmus založený na postupném prohledávání grafu do šířky (vycházíme z vrcholu u) a zjišťování, na kolik kroků je dosažitelný který vrchol - po ohodnocení cílového vrcholu v musí ještě následovat zpětný chod, při kterém určíme vlastní cestu (porovnáváme ohodnocení jednotlivých vrcholů nebo máme zaznamenány předchůdce jednotlivých vrcholů) Podobný postup známe už z dřívějška – nejkratší cesta koněm na šachovnici. Algoritmus funguje stejně pro neorientované i pro orientované grafy (u těch postupujeme při prohledávání do šířky jen ve směru šipek a naopak při zpětném chodu proti směru šipek). program MinCesta1; {Nalezení nejkratší cesty v neohodnoceném grafu - průchod grafem do šířky} const MaxVrch = 100; MaxVrchPlus1 = 101; MaxHran = 1000; MaxHranPlus1 = 1001;
{max. přípustný počet vrcholů} {MaxVrch+1} {max. přípustný počet hran} {MaxHran+1}
var V: array[1..MaxVrchPlus1] of 1..MaxHranPlus1; E: array[1..MaxHran] of 1..MaxVrch; {uložení grafu ve tvaru seznamu následníků} Fronta: array[1..MaxVrch] of 1..MaxVrch; {fronta vrcholů pro realizaci průchodu} ZacFr, KonFr: 1..MaxVrch; {začátek a konec fronty} D: array[1..MaxVrch] of integer; {vzdálenosti vrcholů} P: array[1..MaxVrch] of 1..MaxVrch; {předchůdci vrcholů} N: 1..MaxVrch; {počet všech vrcholů grafu} Start, Cil: 1..MaxVrch; {výchozí a cílový vrchol} EI: 1..MaxVrch; {pomocné pro uložení E[i]} i, j: integer; begin {Načtení vstupních dat} write('Počet vrcholů grafu: '); readln(N); write('Číslo výchozího a cílového vrcholu: '); readln(Start, Cil); writeln('Po řádcích následníci jednotlivých vrcholů', ' od 1 do ', N, ':'); V[1]:=1; j:=1; 88
for i:=1 to N do begin while not eoln do {následníci vrcholu číslo i} begin read(E[j]); j:=j+1 end; readln; V[i+1]:=j end; {Inicializace} for i:=1 to N do D[i]:=-1; {žádný vrchol ještě není navštíven} D[Start]:=0; Fronta[1]:=Start; {ve frontě je jen výchozí vrchol} ZacFr:=1; KonFr:=1; {Průchod grafem do šířky} while (D[Cil] = -1) and (ZacFr <= KonFr) do begin j:=Fronta[ZacFr]; {jdeme z vrcholu j} ZacFr:=ZacFr+1; for i:=V[j] to V[j+1]-1 do begin EI := E[i]; {následníci vrcholu j jsou E[i]} if D[EI] = -1 then begin D[EI]:=D[j]+1; P[EI]:=j; KonFr:=KonFr+1; Fronta[KonFr]:=EI end end end; {Vypsání nejkratší cesty} if D[Cil] = -1 then writeln('Cílový vrchol cesty není dostupný', ' ze zadaného výchozího vrcholu!') else begin writeln('Délka nejkratší cesty z vrcholu ', Start, ' do vrcholu ', Cil,': ', D[Cil]); writeln('Nejkratší cesta v obráceném pořadí vrcholů'); writeln('(od cílového vrcholu k výchozímu):'); i:=Cil; while i <> Start do begin write(i:5); i:=P[i] end; writeln(Start:5) end end.
89
9. nalezení nejkratší cesty v ohodnoceném grafu nejkratší cesta z vrcholu u do vrcholu v = taková cesta z u do v, na níž je součet ohodnocení všech hran co nejmenší - podobný postup jako prohledávání do šířky v předchozím případě, vlna se ale nešíří z výchozího vrcholu u rovnoměrně do všech stran, nýbrž je vhodně „deformována“ pomocí ohodnocení - Dijkstrův algoritmus (viz dále) - nutná podmínka: ohodnocení všech hran nezáporná - Dijkstrův algoritmus určí pouze délky nejkratších cest do jednotlivých vrcholů, následovat musí opět zpětný chod, při kterém určíme vlastní cestu
Topologické třídění Algoritmus sloužící k nalezení topologického uspořádání orientovaného grafu, tzn. takového očíslování všech vrcholů grafu čísly od 1 do N, aby pro každou hranu i→j platilo, že i < j. Pozorování: - topologické uspořádání nemusí existovat (cyklus v grafu) - topologické uspořádání nemusí být jednoznačné Naším úkolem tedy je nalézt jedno libovolné topologické upořádání daného orientovaného grafu nebo ohlásit, že žádné topologické uspořádání neexistuje. Příklady: - dány návaznosti výrobních operací (orientované hrany), sestavit výrobní proces (zvolit správné pořadí jednotlivých operací) - nepřímá rekurze – pořadí deklarací procedur bez použití forvard Tvrzení: Orientovaný graf lze topologicky uspořádat, právě když je acyklický. Důkaz: → triviální: kdyby graf obsahoval cyklus (např. i → j → k → i), přímo z definice plyne, že nemůže existovat jeho topologické upořádání (muselo by platit i < j < k < i, což je spor) ← konstrukčně: ukážeme algoritmus topologického třídění, který libovolný acyklický graf topologicky uspořádá. Pozorování: V orientovaném acyklickém grafu existuje vrchol bez předchůdců (tzn. vrchol, do kterého nevede žádná hrana). Dokážeme sporem – nechť tvrzení neplatí a v orientovaném acyklickém grafu do každého vrcholu nějaká hrana vede. Zvolíme libovolný vrchol V1, do něj vede hrana z nějakého vrcholu V2, do něj vede hrana z vrcholu V3, atd. V grafu je jen konečně mnoho vrcholů, takže nejvýše po N krocích se takto dostaneme do vrcholu grafu, ve kterém jsem už byli → graf obsahuje cyklus, což je spor s předpokladem.
90
Algoritmus: - zvolíme libovolný vrchol bez předchůdců (v acyklickém grafu musí existovat, jinak konec = je tam cyklus) - zvolenému vrcholu přiřadíme nejbližší volné pořadové číslo v topologickém uspořádání a z grafu tento vrchol vypustíme včetně hran z něj vedoucích - tím dostaneme graf (opět orientovaný a acyklický, když původní graf byl orientovaný a acyklický!), který má o jeden vrchol méně, a na něj aplikujeme stejný postup - úspěšný konec, pokud takto postupně očíslujeme a vypustíme všechny vrcholy grafu Realizace: - graf uložen pomocí seznamů následníků (případně matice sousednosti) - pomocné pole P indexované čísly vrcholů od 1 do N, kde je pro každý vrchol uložen počet jeho předchůdců Vrchol bez předchůdců tam tedy má 0, vypuštěnému vrcholu uložíme do pole P pro odlišení nějakou zvláštní hodnotu, např. -1. Časová složitost: O(N 2) následující postup se opakuje nejvýše N-krát: vybrat vrchol bez předchůdce – průchod polem P O(N) vrchol vyřadit – vložení „-1“ do pole P O(1) vyřadit hrany z něj vedoucí – projít seznam následníků a snížit jim o 1 údaj v poli P O(N)
program TopologickeTrideni; {Topologické uspořádání vrcholů orientovaného grafu} const MaxVrch = 100; MaxVrchPlus1 = 101; MaxHran = 1000; MaxHranPlus1 = 1001;
{max. přípustný počet vrcholů} {MaxVrch+1} {max. přípustný počet hran} {MaxHran+1}
var V: array[1..MaxVrchPlus1] of 1..MaxHranPlus1; E: array[1..MaxHran] of 1..MaxVrch; {uložení grafu ve tvaru seznamu následníků} P: array[1..MaxVrch] of integer; {pro každý vrchol počet jeho předchůdců} Q: array[1..MaxVrch] of integer; {seznam čísel vrcholů nemajících předchůdce} PocetQ: 0..MaxVrch; {aktuální počet záznamů v seznamu Q} U: array[1..MaxVrch] of integer; {výsledné topologické uspořádání vrcholů grafu} N: 1..MaxVrch; {počet všech vrcholů grafu} Cyklus: boolean; {nalezen cyklus v grafu} i, j, k: integer; begin {Načtení vstupních dat} write('Počet vrcholů grafu: '); readln(N); 91
writeln('Po řádcích následníci jednotlivých vrcholů', ' od 1 do ', N, ':'); V[1]:=1; j:=1; for i:=1 to N do begin while not eoln do {následníci vrcholu číslo i} begin read(E[j]); j:=j+1 end; readln; V[i+1]:=j end; {Inicializace - počáteční obsazení poli P, Q} for i:=1 to N do P[i]:=0; {zatím vynulovat počet předchůdců} for i:=1 to V[N+1]-1 do {prvek E[V[N+1]-1] představuje posledního následníka v E} begin j:=E[i]; {číslo koncového vrcholu nějaké hrany} P[j]:=P[j]+1 {vrchol číslo j má tedy dalšího předchůdce} end; PocetQ := 0; {ještě neznáme vrcholy bez předchůdců} for i:=1 to N do if P[i] = 0 then begin PocetQ := PocetQ + 1; Q[PocetQ] := i {další vrchol bez předchůdců} end; {Vlastní topologické třídění} Cyklus := false; {zatím nebyl nalezen cyklus} i := 1; {hledáme vrchol V[i]} while not Cyklus and (i <= N) do if PocetQ = 0 then Cyklus := true {graf není acyklický} else begin U[i] := Q[PocetQ]; {další vrchol do uspořádání} PocetQ := PocetQ - 1; for j:=V[U[i]] to V[U[i]+1]-1 do begin {vrcholy E[j] jsou všichni následníci vrcholu U[i]} k := E[j]; P[k] := P[k] - 1; {snížíme jim počet předchůdců} if P[k] = 0 then {nemá předchůdce - zařadit do Q} {vrcholy již vyřazené z grafu budou mít P[k] < 0} begin PocetQ := PocetQ + 1;
92
Q[PocetQ] := k end end; i:=i+1 end; {Výpis výsledku} if Cyklus then begin writeln('Zadaný graf není acyklický'); writeln('Nelze ho proto topologicky uspořádat') end else begin writeln('Topologické uspořádání vrcholů grafu:'); for i:=1 to N do write(U[i]:4); writeln end end.
Dijkstrův algoritmus - nalezení nejkratší cesty v ohodnoceném grafu Nejkratší cesta z vrcholu u do vrcholu v = taková cesta z u do v, na níž je součet ohodnocení všech hran co nejmenší. Trochu podobný postup jako prohledávání do šířky v případě neohodnoceného grafu, vlna se ale nešíří z výchozího vrcholu u rovnoměrně do všech stran, nýbrž je vhodně „deformována“ pomocí ohodnocení. Nutná podmínka použitelnosti: ohodnocení všech hran je nezáporné. Stejný postup lze použít pro neorientované i pro orientované grafy. Dijkstrův algoritmus lze použít buď pro nalezení nejkratší vzdálenosti z výchozího vrcholu u do cílového vrcholu v, nebo pro určení nejkratších vzdáleností z výchozího vrcholu u do všech dostupných vrcholů grafu (při stejné, tj. kvadratické asymptotické časové složitosti). Dijkstrův algoritmus určí pouze délku nejkratší cesty z výchozího do cílového vrcholu, následovat musí zpětný chod (podobně jako při prohledávání do šířky), při kterém určíme vlastní cestu. Pokud existuje více různých cest téže minimální délky, algoritmus určí jednu libovolnou z nich. Reprezentace grafu: seznamy následníků nebo matice vzdáleností di,j - potřebujeme umět rychle určit, kam vedou z daného vrcholu hrany
93
Další uložené údaje: u každého vrcholu si potřebujeme evidovat přiřazenou hodnotu hi = délka nejkratší cesty z výchozího vrcholu u do vrcholu i, jakou jsme zatím našli realizace H: array [1..N] of TypOhodnoceni o této hodnotě si dále pamatujeme, zda je dočasná (tzn. možná ještě půjde zlepšit, tj. snížit) nebo trvalá (je to už definitivní hodnota) realizace Docas: array [1..N] of Boolean (pole příznaků) nebo Docas: set of 1..N (množina vrcholů) Inicializace dat hu = 0 (výchozí vrchol) hi = „+∞ ∞“ pro všechna i ≠ u hodnoty všech vrcholů jsou dočasné Algoritmus dokud má cílový vrchol dočasnou hodnotu 1. nechť j je vrchol s nejmenší dočasnou hodnotou 2. hodnotu vrcholu j prohlásíme za trvalou 3. všem následníkům vrcholu j, které mají ještě dočasnou hodnotu, přepočítáme jejich hodnotu podle vztahu hi = min ( hi, hj + dj,i ) (tzn. snížíme dočasné hodnoty všech vrcholů grafu, které je možné snížit díky cestě vedoucí přes vrchol j) Pokud chceme znát vzdálenosti z vrcholu u do všech dostupných vrcholů, změníme podmínku ukončení cyklu takto: dokud existuje dostupný vrchol s dočasnou hodnotou Správnost I. konečnost: při každé obrátce cyklu se jeden vrchol stane trvalým → nejvýše po N krocích výpočet skončí II. korektnost výsledku – proč můžeme minimální dočasnou hodnotu vrcholu prohlásit za trvalou: - dočasná hodnota představuje vždy délku nejkratší cesty vedoucí přes všechny trvalé vrcholy (plyne z přepočítávání hodnot v bodě 3.) - minimální dočasná hodnota už nepůjde lepšit, neboť ostatní dočasné vrcholy mají hodnotu větší a hrany grafu jsou ohodnoceny nezáporně Efektivita cyklus se opakuje nejvýše N-krát, v něm je složitost vložených kroků: 1. nalezení vrcholu s minimální dočasnou hodnotu O(N) 2. označení této hodnoty za trvalou O(1) 3. obejdeme nejvýše N následníků, každý přepočítáme O(N) → celková časová složitost algoritmu O(N 2)
94
Určení cesty u každého vrcholu i si budeme pamatovat číslo vrcholu pi, který je jeho předchůdcem na minimální cestě z výchozího vrcholu realizace P: array [1..N] of 0..N Inicializace: pu = 0 (výchozí vrchol nemá předchůdce) Stanovení hodnot předchůdců: vždy při snížení hodnoty hi na hodnotu hj + dj,i definujeme rovněž novou hodnotu pi = j Po skončení Dijkstrova algoritmu následuje zpětný chod pomocí hodnot p stejně jako v případě neohodnocených grafů. Složitost algoritmu to nijak neovlivní, zůstává O(N 2).
program MinCesta2; {Nalezení nejkratší cesty v ohodnoceném grafu - Dijkstrův algoritmus} const MaxVrch = 100;
{max. přípustný počet vrcholů}
var Vzdal: array[1..MaxVrch, 1..MaxVrch] of integer; {uložení grafu ve tvaru matice vzdáleností} H: array[1..MaxVrch] of integer; {hodnoty vrcholů} Docas: array[1..MaxVrch] of boolean; {dočasná hodnota} P: array[1..MaxVrch] of 1..MaxVrch; {předchůdci vrcholů} N: 1..MaxVrch; {počet všech vrcholů grafu} Start, Cil: 1..MaxVrch; {výchozí a cílový vrchol} Pruchod: boolean; {pokračovat v průchodu} i, j: integer; begin {Načtení vstupních dat a inicializace} write('Počet vrcholů grafu: '); readln(N); write('Číslo výchozího a cílového vrcholu: '); readln(Start, Cil); for i:=1 to N do begin H[i]:=maxint; Docas[i]:=true; for j:=1 to N do Vzdal[i,j]:=maxint end; writeln('Hrany grafu ve tvaru "odkud, kam, délka":'); while not eof do begin read(i, j); read(Vzdal[i,j]) end; H[Start]:=0; Pruchod:=true;
95
{Průchod grafem} while Docas[Cil] and Pruchod do begin j:=Cil; {hledáme vrchol s minimální dočasnou hodnotou} for i:=1 to N do if Docas[i] and (H[i] < H[j]) then j:=i; {vybrán vrchol j} if H[j] = maxint then Pruchod:=false {cílový vrchol je nedostupný} else begin Docas[j]:=false; {vrchol j má trvalou hodnotu} for i:=1 to N do if Vzdal[j,i] < maxint then if H[j] + Vzdal[j,i] < H[i] then begin H[i]:=H[j] + Vzdal[j,i]; {kratší cesta do vrcholu i} P[i]:=j {novým předchůdcem i je j} end end end; {Vypsání nejkratší cesty} if Docas[Cil] then writeln('Cílový vrchol cesty není dostupný', ' ze zadaného výchozího vrcholu!') else begin writeln('Délka nejkratší cesty z vrcholu ', Start, ' do vrcholu ', Cil,': ', H[Cil]); writeln('Nejkratší cesta v obráceném pořadí vrcholů'); writeln('(od cílového vrcholu k výchozímu):'); i:=Cil; while i <> Start do begin write(i:5); i:=P[i] end; writeln(Start:5) end end.
96
