C2142 Návrh algoritmů pro přírodovědce
7. Grafy.
Tomáš Raček
Jaro 2017
Vyhledávání v databázích I
Opakování. Umíme efektivně vyhledávat a řadit objekty podle
různých klíčů v případě, že je na těchto klíčích definováno
uspořádání (≤).
Vyhledávání molekul. Mějme molekulu a chtějme zjistit, zdali se již
vyskytuje v dané sadě sloučenin (= databázi).
• Záznamy o molekulách často obsahují jednoznačné
identifikátory (řetězce znaků) → umíme.
Problém. Tyto informace ale nemusí být dostupné. K dispozici
máme však minimálně:
• údaje o atomech (pozice, typy)
• vazby mezi atomy
Příklad molekuly – formát MOL
702
-OEChem-03301510303D
9 8 0 0 0 0 0 0 0999 V2000
-1.1712 0.2997 0.0000 O 0 0 0 0 0 0
-0.0463 -0.5665 0.0000 C 0 0 0 0 0 0
1.2175 0.2668 0.0000 C 0 0 0 0 0 0
-0.0958 -1.2120 0.8819 H 0 0 0 0 0 0
-0.0952 -1.1938 -0.8946 H 0 0 0 0 0 0
2.1050 -0.3720 -0.0177 H 0 0 0 0 0 0
1.2426 0.9307 -0.8704 H 0 0 0 0 0 0
1.2616 0.9052 0.8886 H 0 0 0 0 0 0
-1.1291 0.8364 0.8099 H 0 0 0 0 0 0
1 2 1 0 0 0 0
1 9 1 0 0 0 0
2 3 1 0 0 0 0
2 4 1 0 0 0 0
2 5 1 0 0 0 0
3 6 1 0 0 0 0
3 7 1 0 0 0 0
3 8 1 0 0 0 0
Vyhledávání v databázích II
Intuice. Porovnání na základě pozic jednotlivých atomů a vazeb
představuje výpočetně netriviální problém. Současné databáze
navíc obsahují stovky tisíc až miliony struktur.
Návrh řešení. Proveďme vyhledávání v několika fázích, které budou
postupně omezovat množinu přípustných struktur. Postupujme od
nejjednodušších metod po složitější.
1. jednoduché deskriptory (př. sumární vzorec)
2. využití znalosti topologie, podstruktur
3. porovnání pozic atomů v prostoru
Příklad. Porovnání molekul podle sumárních vzorců v rozumném
čase výrazně redukuje množinu kandidátů. Nicméně samo o sobě
nestačí.
Vyhledávání v databázích III
Omezení. Pomocí sumárního vzorce nelze rozlišit izomery.
Topologie. Je nutné přidat další informace o struktuře sloučenin –
propojení vazbami.
Problém. Potřebujeme nalézt vhodnou datovou strukturu pro
reprezentaci molekuly.
3. fáze. Ani toto rozlišení obecně nestačí (stereoizomery), ale
získané výsledky lze použít jako výchozí bod pro další algoritmy.
Graf
Definice. Graf G = (V, E), kde V je množina uzlů (vrcholů) a E je
množina hran.
Typy grafů
• orientovaný – hrany jsou uspořádané dvojice (u, v)
• neorientovaný – hrany jsou dvouprvkové podmnožiny {u, v}
Příklad orientovaného grafu
• G = (V, E)
• V = {A, B, C, D, E, F}
• E = {(A, B), (B, C), (C, E), (D, B), (E, D), (E, F)}
Reprezentace grafu
Minimální požadavky na datovou strukturu
• dotaz na existenci hrany v grafu
• sousedé daného vrcholu
Triviální řešení představuje obyčejný seznam (pole) hran. Nicméně
výše zmíněné operace pak nelze implementovat efektivně.
• G = (V, E)
• V = {A, B, C, D, E, F}
• E = {(A, B), (B, C), (C, E), (D, B), (E, D), (E, F)}
Matice sousednosti
Matice sousednosti. Vytvořme pro graf G = (V, E) matici A
o rozměrech |V| × |V| s vlastností:
Ai,j = 1 ↔ (i, j) ∈ E
Příklad
A =


0 1 1 0
0 0 0 0
0 1 0 1
0 0 1 0


Vlastnosti
• dotaz na přítomnost hrany je konstatní operace
• seznam následníků daného vrcholu v lineárním čase
• potřeba |V|2 paměti → vhodné pro husté grafy (|E| ≈ |V|2)
Seznam následníků
Seznam následníků. Uvažme pole ukazatelů na seznamy následníků
daných vrcholů.
Příklad
Vlastnosti
• dotaz na přítomnost hrany je lineární operace
• seznam následníků v lineárním čase
• pouze |V| + |E| paměti → vhodné pro řídké grafy (|E| ≈ |V|)
Procházení grafu
Cíl. Projít všechny vrcholy grafu dostupné ze zvoleného výchozího.
Naivní řešení. Projít postupně seznam vrcholů od začátku do konce
(podobně jako u obyčejného pole).
• zjevně lineární operace
• nerespektuje strukturu grafu
• graf nemusí být souvislý → projdeme i jeho nedosažitelné části
Ideální řešení
• zachová lineární složitost
• každý vrchol projde právě jednou
• odstraní výše uvedené nedostatky
Procházení do šířky
Breadth First Search (BFS) prochází graf po jednotlivých úrovních –
než projde vrcholy vzdálené (co do počtu hran) n od výchozího,
projde předtím všechny vrcholy vzdálené n − 1.
Vlastnosti
• procházíme nejdříve všechny přímé následníky vrcholů
• pro uložení pořadí, ve kterém vrcholy prohledáváme,
používáme frontu
• lineární složitost vzhledem k velikosti grafu – O(|V| + |E|)
Procházení do šířky – pseudokód
1: function BFS(G, u) is
2: Nechť Q je prázdná fronta
3: Enqueue(Q, u)
4: Označ u jako navštívený
5: while Q není prázdná do
6: v ← Dequeue(Q)
7: for all (v, w) ∈ E do
8: if w není navštívený then
9: Označ w jako navštívený
10: Enqueue(Q, w)
11: fi
12: done
13: done
14: end
Procházení do hloubky
Depth First Search (DFS) prochází graf „dokud to jde“, pak se vrací
do posledního místa, kde existuje neprozkoumaná cesta, kterou pak
pokračuje dále (= obvyklé prohledávání bludiště).
Vlastnosti
• lineární algoritmus – O(|V| + |E|)
• často v rekurzivní podobě, iterativní využívá zásobník
1: function DFS(G, u) is
2: Označ u jako navštívený
3: for all (u, v) ∈ E do
4: if v není navštívený then
5: DFS(G, v)
6: fi
7: done
8: end
Procházení do hloubky (iterativně) – pseudokód
1: function DFS(G, u) is
2: Nechť S je prázdný zásobník
3: Push(S, u)
4: Označ u jako navštívený
5: while S není prázdný do
6: v ← Pop(S)
7: for all (v, w) ∈ E do
8: if w není navštívený then
9: Označ w jako navštívený
10: Push(S, w)
11: fi
12: done
13: done
14: end
Otázka. Čím se liší pseudokód pro BFS a DFS?
Procházení binárního stromu
BFS → procházení po úrovních
Varianty DFS
• pre-order → 1. uzel, 2. levý podstrom, 3. pravý podstrom
• in-order → 1. levý podstrom, 2. uzel, 3. pravý podstrom
• post-order → 1. levý podstrom, 2. pravý podstrom, 3. uzel
Pořadí procházení vrcholů
• BFS: 2, 7, 5, 1, 6, 9, 5, 11, 4
• DFS pre-order: 2, 7, 1, 6, 5, 11, 5, 9, 4
• DFS in-order: 1, 7, 5, 6, 11, 2, 5, 4, 9
• DFS post-oder: 1, 5, 11, 6, 7, 4, 9, 5, 2
Otázka. Co kdybychom použili DFS in-order na BST?