Teoretická informatika
Str.1
Grafy (G) Neorientované: (NG)
H – hrany, U-uzly, ρ-incidence (jestli k němu něco vede) Ξ neuspořádaná dvojice
ρ: H→UΞU ρ(h) = [u,v]
Izolovaný uzel – neinciduje s ním žádná hrana Rovnoběžné hrany – hrany se shodnou množinou krajních uzlů Prostý (G) – neobsahuje rovnoběžné hrany Multigraf – aspoň 1 dvojice rovnoběžných hran Obyčejný (G) – prostý (G) bez smyček (hrana mající stejný počáteční i koncový uzel)
⎛ n⎞ ⎝ 2⎠
Úplný graf – obyč. (G), mezi všemi uzly ex. jedna hrana. Značení Kn (graf o n uzlech). Počet hran = ⎜⎜ ⎟⎟ Diskrétní graf – pouze izolované uzly Podgraf: H´⊆ H && U´⊆ U && ρ´(h) = ρ(h) pro všechna h ∈ H´ Faktor (G) = hranový podgraf G´ - množina uzlů shodná s G (má všechny uzly a jen některé (všechny) hrany) Dva grafy, jejichž průnikem je prázdný (G) nazýváme disjunktními (G) Rozdíl G – G1 : G2 ⊆ G pro který platí G = G1 ∪ G2 (G2 neobsahuje žádné hrany z G1, a ani žádné „zbytečné“ uzly) Doplněk – vznikne odečtením grafu G od úplného grafu s množinou uzlů U Izomorfismus - ϕ: grafy jsou strukturálně stejné: G1 ≅ G2 Způsob pro odhalení: Píši si k tomu posloupnosti stupňů a grafy, jejichž posloupnosti se budou rovnat proberu podrobně Def: Nechť G1=
a G2= jsou dva grafy a ϕ bijekce množiny H1 ∪ U1 na množinu H2 ∪ U2 taková, že: • zúžené zobrazení ϕ⏐H1 je bijekce H1 na H2 (ϕ⏐H1: H1 ↔ H2) • zúžené zobrazení ϕ⏐U1 je bijekce U1 na U2 (ϕ⏐U1: U1 ↔ U2) • ϕ zachovává incidenci, tzn. pro libovolné h ∈ H platí ρ1(h) = [u,v] ⇒ ρ2(ϕ(h)) = [ϕ(u),ϕ(u)] Zobrazení ϕ se pak nazývá izomorfismus mezi grafy G1 a G2 a grafy G1, G2, pro které tento izomorfismus lze nalézt, se nazývá izomorfní grafy. Stupeň uzlu – počet hran s ním incidujících δG(u). Pro každou smyčku: δ(u) = 2 δ(G), Δ(G) – min. resp. max. stupeň uzlu v (G); Σδ(u) = 2 |H| V obec. grafu: δ(u) = poč. soused Věta: V lib. (G) je poč. uzlů lichého stupně číslo sudé. Sled (G) – posloupnost uzel, hrana, uzel …, hrana, uzel – délka sledu = počet hran – otevřený sled – různý počáteční a koncový uzel (i sled nulové délky) – uzavřený Tah – sled, ve kterém se neopakují hrany Cesta – tak, ve kterém se neopakují uzly (mimo uzavřené cesty) Kružnice – uzavřená cesta Z lib. sledu lze vybrat cestu, ale z uzavřeného sledu nemusí jít vybrat kružnice (to lze jen pro sled liché délky) Souvislý (G) – mezi lib. dvěma uzly ex. sled Na souvislé propojení potřebuji min. N-1 hran Komponenta grafu – každý jeho max. souvislý podgraf Strom – souvislý graf bez kružnic Kostra – faktor, který je stromem. Hrany náležející kostře jsou větve. Ty, které tam nepatří jsou tětivy. Přidáním 1 tětivy do kostry udělám právě 1 kružnici. Kostra má h – u + 1 tětiv T Počet různých koster grafu G = det(ArAr ), kde Ar je matice tvořená lib. |U|–1 LN řádky matice A
Orientované (OG):
u – počáteční uzel o(h) = (u,v) uΓv uzel u nazýváme předchůdcem uzlu v Úplný symetrický (OG) v němž je každá uspořádaná dvojice uzlů spojena orient. hranou Symetrická orientace: z udělám Opačně orientovaný (G) – otočíme orientaci (šipky) u všech hran Orientované spojení; Orientovaný tah; Orientovaná cesta; Cykl – orient. uzavřená cesta Silně souvislý – mezi lib. dvěma uzly ex. orient. spojení Silná komponenta – každý jeho max. silně souvislý podgraf (např. má 2 silné komponenty) Kondenzace grafu – prostý graf, jehož každý uzel odpovídá silné komponentě
Teoretická informatika
Str.2
Výstupní stp. uzelu δG (u), vstupní δG (u) – poč. hran, které mají uzel u za koncový Σδ+(u) = Σδ–(u) = |H| Kořen: δ–(u) = 0 List: δ+(u) = 0 Acyklický (G) – prostý (OG), který neobsahuje cyklus Nalezení: Odebírám listy a kořeny +
–
Vlastnosti grafů Pokrytí (G) – rozložíme množinu hran tak, že jsou hrany každé třídy Hi uspořádány do tahu. Pokrytí s nejmenším počtem tříd nazýváme minimální pokrytí Min pokrytí – projít všechny uzly. Hrany mohu pojít jen 1x Eulerův graf – každý uzel má sudý stupeň (skládá se z kružnic) Věta: (G) lze pokrýt jediným uzavřeným tahem iff, je souvislým Eulerovým (G) Věta: (G) který má 2n uzlů lichého stupně a je souvislý lze pokrýt minimálně n otevřenými tahy. Orient. Eulerův (G) – každý uzel má stejný vstupní a výstupní stupeň Nezávislá podmnožina uzlů – žádné dva z uzlů neincidují se stejnou hranou (nesousedící uzly); α(G) Klika grafu – max. úplný (každý s každým) podgraf Kn Klikovost grafu ω(G) – maximální klika (číslo n z Kn) α(G) = ω(–G) Dominující podmnožina – podmnožina uzlů, která svou množinou sousedů pokrývá všechny zbývající uzly (G) Dominance grafu β(G) = min|D| D ∈ dominující podmnožina Věta: Nezávislá podmnožina uzlů neorient (G) je max. iff je jeho dominující podmnožinou ⇒ β(G) ≤ α(G) Chromatické číslo χ(G) –α(G) ≥ |U| χ(G) ≤ δmax + 1 graf bez kružnic liché délky: χ(G) = 2 (např. strom) δmax – max. stupeň uzlu Bipartitní (bichromatický) (G): χ(G) = 2, uplný značím Km,n Vzdálenost d(u,v) – délka nejkratší cesty z u do v. d(u,v) ≥ 0; d(u,v) = 0 ⇔ u = v; d(u,v) = d(v,u) d(u,v) ≤ d(u,z) + d(z,v) Def: Vzdáleností uzlů u a v v neorientovaném souvislém grafu G = nazýváme délkou nejkratší cesty spojující tyto dva uzly. Průměr grafu T(G) = max d(u,v) pro všechna u, v. - max. vzdálenost v grafu Excentricita uzlu e(u,G) = max d(u,v) pro všechna v - jeho vzdálenost od jemu nejvzdálenějšímu vrcholu Poloměr r(G) = min e(u,G) u ∈ U Střed grafu – každý uzel s excentricitou rovnou poloměru Cyklomatické číslo: μ(G) = |H| – |U| + p, kde p – počet komponent udává počet tětiv grafu Hodnost grafu: h(G) =|U| – p Kořenový strom: kořen je propojitelný se všemi ostatními orientovanou cestou. Dálka této cesty se nazývá hloubka uzlu. Uspořádaný strom: rozlišujeme následníky na 1., 2., .… Pravidelný strom spt.2 s n listy obsahuje n–1 vnitřních uzlů (včetně kořene) a 2(n–1) hran Vnější délka: E(T) = Σvšech hloubek listů E = I (r – 1)+r*u E = I+2n Vnitřní délka: I(T) = Σhloubek vnitřních uzlů r – stp.stromu, u – počet vnitřních uzlů Binární strom: preorder – kořen, levý, pravý inorder – levý, kořen, pravý postorder – levý, pravý, kořen Separabilita a planarita Hranový řez – minimální množina hran, které když odeberu, tak se graf rozdělí na 2 komponenty (ne více). (⇒ nesmí sousedit s artikulací) Artikulace – takový uzel (jeden), kterým prochází všechny cesty mezi jistou dvojicí uzlů (⇒ podgraf bez toho uzlu má víc komponent). Má-li graf artikulaci je separabilní. Jinak je nesaparabilní. Planární graf: diagram lze nakreslit v E2. Eulerova formule: počet stěn grafu (včetně vnější) r = |H| – |U| + 2 Max. planární graf má hran: |H| ≤ 3 |U| – 6 Grafy K5 a K3,3 jsou nejmenší neplanární grafy Grafy jsou homeomorfní, jestliže jsou buď izomorfní, nebo je-li možné konečným počtem půlení hran v těchto grafech dosáhnout toho, že vzniklé grafy jsou izomorfní.
Teoretická informatika
Str.3
Topologické uspořádání Jde pouze pro acyklické grafy (žádný cyklus a smyčka). Uzly můžeme seřadit do horizontální úrovně a orientace všech hran pak musí směřovat jedním směrem. Získání: pomocí DFS prohledej a v okamžiku uzavření ulož každý uzel v na začátek seznamu uzlů, který po dokončení bude obsahovat uzly seřazené podle požadavků topologického uspořádání. Při zjišťování acykličnosti stačí vypouštět z grafu kořeny a listy (zůstane jen případný cyklus).
Algoritmy Matice incidence A – do řádků uzly, do sloupců hrany – napíši jedničku tam, kde je ta hrana spojena s uzlem ⇒ v každém sloupci 2 jedničky. Hodnost této matice o p komponent h(A) = |U| – p. U (OG) je 1 u počátečního uzlu, –1 u koncového Matice sousednosti V – v řádku i ve sloupci uzly – píši tam číslo, kolik hran ty uzly spojuje ⇒ matice je souměrná Vn udává, kolik sledů délky n je v grafu G. U (OG) prvek vik určuje hranu vedoucí z ui do uk.(matice není symetrická) Spojová reprezentace – pole uzlů (pozice označuje číslo uzlu) ve kterém jsou ukazatele na strukturu, která obsahuje číslo uzlu, se kterým tento sousedí a ukazatel NEXT. Věta: Dva (NG) jsou izomorfní iff, jsou jejich matice incidence stejné až na případnou permutaci řádků a sloupců. Pro matici sousednosti to platí také, ale uvažujeme jen stejné permutace množiny řádků a sloupců (možností je n!) d
Matice dosažitelnosti: R =
∑ V i , kde d = min(|H|, |U| – 1) i =0
BFS – prohledávání do šířky (nalezení stromu nejkratších cest a zjištění dosažitelnosti): INICIALIZACE: stav dej na FRESH, vzdálenost na ∞ a předchůdce na NULL. Otevři jeden uzel a ulož jej do fronty. Dokud není fronta prázdná vyber z ní první otevřený. Sousedy, kteří jsou FRESH otevři, urči jim vzdálenost, předchůdce a ulož jej do fronty. Odeber ten otevřený uzel s fronty a zavři jej. Čas složitost: O(H+U) DFS – prohledávání do hloubky (Depth–First search) DFS: Všechny uzly nastav jako FRESH a následníky na NULL. Pro každý FRESH uzel proveď DFS-Projdi(u) DFS-Projdi(u): Otevři ten uzel u a dej mu čas otevření. Pro všechny jeho FRESH následníky proveď DFS-Projdi(následník). Pak ten uzel uzavři a dej mu čas uzavření. Otevřené uzly ukládám do zásobníku otevřených uzlů (pro nerekurzivní řeš.). Čas složitost: O(H+U) Použití: Když neex. zpětné hrany (tímhle to poznám), jde o acyklický graf. Když se podívám na uzel a je FRESH ≡ stromová hrana, OPEN ≡ zpětná hrana, CLOSE ≡ dopředná nebo příčná (vede od uzlu k nějakému jeho potomkovi v DF-lese) DF-les se obecně skládá z několika DF-stromů. DF-strom se konstruuje pomocí předchůdců p[v] (jak se to procházelo pomocí DFS) Silné komponenty: • proveď DFS(G), který určí časovou značku uzavření f[u] každého uzlu u; • vytvoř opačně orientovaný graf G–; • proveď DFS(G–), přitom v hlavním cyklu DFS probírej uzly v pořadí klesající hodnoty f[u] (získané v prvním kroku) • rozklad množiny uzlů podle jednotlivých stromů DF-lesa získaného v předchozím kroku určuje rozklad na silné komponenty Pozn: V třetím bodu se uzavírá jedna silná komponenta po druhé. Je to nejspíš tak, že nejdřív to projdu v jednom směru a pak jdu od uzlů, které byly procházeny na konci a dívám se, kam se z nich mohu dostat (proto nejspíš G–). Generování všech koster grafu: Probírej hrany v lib. pořadí. Hranu, u které by se přidáním nevytvořila kružnice vlož do zásobníku a pokračuj v generování všech možných zbytků kostry s použitím zbývajících hran (rekurze). Pak se ještě generují všechny kostry neobsahující aktuální hranu. (2.rekurze). Kostra je celá, až má |U|–1 hran. Zjišťování kružnic-zjišťování komponent grafu KOMP(G): Vytvoříme množiny, kde bude jediný prvek (každý uzel) ⇒ bude taky svým reprezentantem. Pokud zjistím, že 2 uzly již patří do stejné komponenty (operace FIND-SET) → nemohu je propojit hranou (vznikla by kružnice). Pokud ne, ty dvě množiny sjednotím (operace UNION) a dám jim jednoho reprezentanta. Provedení: Kořenový strom, kde pro každý uzel se vytvoří samostatný podstrom (je tam sám)– otec je reprezentantem množiny (kořenem) – operace MAKE-SET. V operaci UNION mohu kořen menšího stromu zavěsit rovnou pod kořen většího (pak rychlé hledání). Ve FIND-SET mohu uzly, které jsem prošel při hledání kořene připojit rovnou na ten nalezený kořen, aby se to příště hledalo rychleji.
Minimální kostry: (hranám je přiřazena nezáporná reálná délka)
Teoretická informatika Str.4 Borůvkův-Kruskalův alg O(|H|.lg|H| ): upravený KOMP(G) – udělám MAKE-SET, uspořádám hrany do neklesající posloupnosti, ze které pak vybírám vhodné (FIND-SET) a popř. spojuji do jednoho stromu (UNION). Prostě vybírám hrany s min. ohodnocením (kdekoli z (G) ) a pokud bych přidáním nevytvořil kružnici, tak o nich prohlásím, že jsou v min. kostře. Jarníkův-Primův alg O(|H|.lg|U|): Přidávám k dosud nalezené kostře takové hrany, které sousedí s již nalezenou kostrou, mají nejmenší ohodnocení a nevytvoří kuržnici. Provedení: Do fronty ulož všechny uzly a urči jim nekonečnou vzdálenost od podstromu. Pouze kořen nemá předchůdce. Dokud není fronta prázdná, vyber nejbližší uzel u a u jeho sousedů, kteří jsou ještě ve frontě zkus, zda mají blíže k u. Pokud ano, zadej jim předchůdce u a menší vzdálenost. Hladové programován: ke globálně optimálnímu řešení lze dospět prostřednictvím lokálně optimálních výběrů (shora dolů) Dynamické programování: (zdola nahoru) - optimalizační problém rozkládám na podproblémy (na začátku nejsme schopni říct, jako rozložení je to správné). Alg typu „rozděl a panuj“ Huffmanovo kódování: Aby se pravděpodobnější případy hledali rychleji než ty méně pravděpodobné. Pro zadanou posloupnost vah se vytvoří list pro každou váhu wi a uloží se do prioritní fronty Q. (n–1)krát se opakuje sloučení uzlů s min. vahami. Vytvoří se jejich předchůdce, kterému se jako váha dá součet vah těch dvou předchůdců. Takto nově vzniklý uzel se vloží do Q, ze které se ti 2 zpracovaní vyjmou. Jde o prefixový kód – začátek žádného kódového slova není stejný jako jiného.
Nejkratší cesty z jednoho uzlu: Chceme i záporné ohodnocení hran. Pokud by cesta procházela záporně ohodnoceným cyklem (procházela by jím donekonečna) ⇒ min.spojení neexistuje. Označujeme dw(u,v) = –∞. dw(u,v) ≥ 0, dw(u,v) = 0 iff u = v; dw(u,v) ≤ dw(u,z) + dw(z,v) Nejkratší cesty do jediného cílového uzlu – stačí řešit standardní úlohu, ale v opačně orientovaném grafu Relaxace hrany alg. RELAX(u,v,w): Lze-li d[v] zmenšit (d[u]+w(u,v) < d[v]), pak to provedeme a také upravíme předchůdce (nově nalezená cesta je menší než ta dříve nalezená) Dijkstrův alg. O(|H|.lg|U|): ohodnocení hran musí mít nezáporné čísla; modifikované prohledáváním do hloubky Prioritní fronta Q seřazená podle d[u]. Vem nejmenší prvek z Q, uzavři jej a pro každého jeho následovníka proveď RELAXaci hrany (uprav jeho následovníkům vzdálenost (pro něž je to výhodné)). Pozn: Musím postihnout to, že měním vzdálenosti prvků, které jsou v prioritní frontě a prvek tam nesmí být 2x. Bellman-Fordův alg O(|H|.|U|): lze použít i pro záporně ohodnocené hrany Alg: Opakovaně relaxuj ( |U|–1 krát ) všechny hrany grafu. Pro všechny hrany zkus, jestli ještě neexistuje hrana, která zmenšuje d. Pokud ano – je zde záporný cyklus. Upravený: Ulož počáteční uzel do fronty. Pak v cyklu, dokud je něco ve frontě, tak to vyber a všechny vycházející hrany relaxuj: Jako původní relaxace, jen když se to povede, tak krom změny délky a předchůdce ten uzel vlož do fronty. U záporně ohodnoceného cyklu se fronta nikdy nevyprázdní. Pokud je graf acyklický, mohu vyhodit tu kontrolu na záporný cyklus a pak je složitost jen O(|H|+|U|).
Nejkratší cesty mezi všemi páry uzlů: Floydův-Warshallův alg: matice předchůdců a matice D, jejíž každý prvek dij vyjadřuje w-délku nejkratší cesty z ui do uj. 3 cykly v sobě k,i,j = 1 do n. dělej
(
)
d ij( k ) = min d ij( k −1) , d ik( k −1) + d kj( k −1) . Musím také iteračně upravovat matici
předchůdců. Odhalení nějakého záporného cyklu: na diagonále nějaké záporné číslo. Johnsonův alg O(|H|.|U|): pro řídké grafy Pomocí Bellmana-Forda zjistím, jestli tam jsou cykly záporné délky. Když ne, přehodnotím hrany, aby tam nebyly záporná
) ) w = w(u,v) + h(u) – h(v). Pak provedu n-krát Dijkstra a pro všechny uzly udělej d u ,v = d (u, v) + h(v) − h(u ) . Jak zvolit fci h: přidám do grafu uzel s orientovaně spojený se všemi ostatními hranou o w = 0. Pak h(u) = d(s,u). Ta fce čísla
vrací nuly, jestliže tam nejsou záporné cesty. Dynamické programování: např. vyhledání optimálního stromu (nějak, že se dělají ty horní diagonály z dolních …) Nejdelší společná podposloupnost: Do 1. řádku a sloupce obdélníkové matice (podle délek posloupností) dám nuly. Pak 2 cykly v sobě vnořené. Je li ai = bi, tak se to použije (do toho políčka se dá velikost předchozího (na diagonále vpravo)+1). Jinak se bere delší ze dvou uvažovaných možností.
Toky v sítích
Def: Sítí nazýváme čtveřici S = , kde G= je obyčejný (OG), s ∈U je zdroj sítě S, t ∈ U, t ≠ s je spotřebič sítě S a q: H → R+ je nezáporné ohodnocení hran, nazývané kapacita sítě S. Pro každou hranu h ∈ H nazýváme příslušnou hodnotu q(h) kapacitou hrany h.
Teoretická informatika Str.5 + Def: Tokem v síti S = nazýváme takové hodnocení hran f: H → R , které splňuje následující podmínky • pro každou hranu (u,v) ∈ H platí 0 ≤ f(u,v) ≤ q(u,v) … tok hranou nesmí překročit její kapacitu • pro každý uzel u sítě různý od s i od t platí: f (u , v ) = f ( w, u ) … tok se nehromadí v žádném vnitřním uzlu
∑
∑
( u ,v )∈H
( w ,u )∈H
Velikost toku f udává, kolik ve zdroji toku vzniká = kolik ho ve spotřebiči zaniká. Když je tam víc zdrojů/spotřebičů, udělám jeden a od něj vedu hrany s nekonečnou kapacitou ke skutečným zdrojům. Když má i uzel omezenou kapacitu, tak tento rozdělím na dva spojené hranou s touto kapacitou. Do jednu přivedu všechny hrany, které do původního vstupovali a do druhého všechny, které z něj vystupovali. Sítě s omezeným min. tokem: Síť doplníme umělým zdrojem Sa a spotřebičem ta a pro všechny hrany (u,v) mající ruv > 0 zavedeme dvojici hran (u,ta), (sa,v) s kapacitou ruv (a dolní mezí = 0) • Snížíme kapacitu quv – ruv a dolní mez toku hranou (u,v) stanovíme = 0 • Doplníme novou zpětnou hranu (t,s) s kapacitou qts = ∞ a dolní mezí = 0 Má-li takto vzniklá síť max. tok z (sa do ta) nasycující všechny případné hrany, pak lze v původní síti nalézt tok fts. Jinak přípustný tok neexistuje. Řez sítě: množina hran, po jejímž odebrání se budou zdroj a spotřebič nacházet v různých komponentách. Kapacita řezu = velikost max. toku v síti = součet jednotlivých kapacit hran, které do řezu patří. Párováním v grafu G nazýváme takovou podmnožinu P ⊆ H jeho hran, ve které žádné dvě hrany nemají společný uzel. Perfektní párování je, když P je faktorem grafu G. Maximální párování je takové, které obsahuje největší počet hran. Maximální tok v síti – Alg. Fordův-Fulkersonův: • Všechny uzly na FRESH; • pak jdu jako prohledávání do šířky, dokud nedojdu do spotřebiče; • Zapíši si zlepšující tok, změním propustnost (teď už tam něco teče → už se tam toho vleze méně) a opakuji od 1. bodu dokud to jde. Pokud v 2. bodu narazím na uzel, kterým už odtéká celá jeho kapacita a já bych tam tou svou cestou mohl dopravit taky něco, tak ten původní „zkusím poslat zpět“ a jdu tam já. S daty, co jsem poslal zpět (aspoň část) zkusím projít jinudy.
Algoritmy umělé inteligence (UI) Stavový prostor je množina všech stavů systému společně s operátory nebo akcemi, které způsobují přechody mezi těmito stavy. Možno chápat jako (OG) → automat. Informované hledání: hodnotící (heuristická) funkce směruje hledání určitým směrem. Gradientní algoritmus (gradientní alg): Pomocí prohledávání do hloubky. Při expanzi se následníci seřadí podle hodnotící funkce a do zásobníku otevřených uzlů se uloží tak, že na vrcholu bude nejperspektivnější z nich. Alg paprskového prohledávání (beam-search): Varianta prohledávání do šířky. V každé hladině uzlů stejně vzdálených od počátku se do fronty otevřených uzlů zařadí nejvýše k nejlepších kandidátů expanze. Alg uspořádaného prohledávání: Jako gradientní, ale otevřené uzly ukládá do prioritní fronty. K expanzi se pak vybírá uzel s nejmenší hodnotou f → Dijkstrův alg v němž se místo odhadované vzdálenosti od počátku používá hodnotící fce. (je-li výpočet f(u) závislý na hodnotě f pro předchůdce uzlu, je nutné upravit relaxaci a upravovat pro dříve generované uzly jejich ohodnocení a zařazovat je znovu do fronty otevřených uzlů. Výhodné je hodnotící fci mít: f(u) = g(u)+h(u), kde g(u) je vzdálenost od začátku a h(u) vzdálenost od konce. Alg s takto uspořádanou hodnotící funkcí se nazývá algoritmus A. Přípustný alg prohledávání – algoritmus, který zaručuje nalezení nejkratší cesty řešení
Heuristické hledání: ) Funkce h (u ) je odhad h(u) a nazývá se heuristická funkce (zcela závislá na existenci kvantifikovatelných heuristic. pravidel). alg A*: jako A, jen je tam ta hodnotící funkce aproximovaná.
)
alg A* je přípustný h (u ) ≤ h(u ) a ohodnocení každého operátoru je > 0.
)
)
alg A1* je lépe informovaný než A2*, když h1(u ) ≤ h 2(u ) pro každý stav u stavového prostoru. Aby to však A1 nalezl
)
)
dříve, musela by heuristická fce být konzistentní: h (u ) − h (v ) ≤ d (u , v ) , kde d(u,v) je přesná vzdálenost. SOH (symetrické obousměrné hledání), která je přípustná a kterou lze docílit nižšího počtu expandovaných uzlů než při prohledávání jednostranném. Mohu použít i heuristiku se směrováním – je to hodně složité. IDA* (iterative deepining A*): SKRIPTA: Iterativní prohlubování, při níž se na počátku nastaví prahová hodnota hodnotící funkce a uzly s vyšší hodnotou se neuchovávají. Pokud hledání neuspěje, nový práh se nastaví na nejblíže vyšší hodnotu dosaženou v minulém průchodu. PŘEDNÁŠKY: Jako alg. do hloubky s omezenou hloubkou. Určím hloubku, kam až to má jít. Když se to tam nenajde, zvětší se prohledávaná hloubka.
Teoretická informatika Str.6 SMA* - jako A*, ale fronta je omezena velikostí. Když se fronta naplní, některé uzly vyhodím. Alg najde optimální řešení, jestli vzdálenost toho uzlu je menší než počet míst ve frontě. Řád růstu funkce (ASI): n Když mám zjisti, která z fcí roste asymptoticky rychleji: a = b, b = exp(n ln a). Např. vyšetřit:
(
)
f ( n) = n
n
(
a g (n) =
)
( n)
n
exp n ln n ? ≥ ? exp n ln n = exp (n 12 ln n ) n ln n ? ≥ ? n 12 ln n
n ? ≥ ? 12 n
neplatí ⇒ g(n) roste řádově rychleji
