je dán neorientovaný ohodnocený graf jako seznam hran s ohodnocením, každá hrana pouze v jednom směru. Dále je dán vrchol V grafu a hodnota Prah. Definujte predikát klastr/4: klastr(+Graf, +V, +Prah, -Klastr), který vrátí v proměnné Klastr seznam všech těch vrcholů Grafu, které jsou dosašitelné z vrcholu V cestou z hran s ohodnocením nejvýše Prah.
2. Prolog: Pseudosplay binárního stromu
Binární vyhledávací strom (BVS) obsahuje číselné hodnoty a reprezentujeme ho pomocí funktorů t/3 a void/0. Na stupu je dán binární vyhledávací strom a jeden jeho vrchol V. Napište prodecuru
transf/3: transf(+BVS,+V,-BVS0),
která pomocí rotací transformuje vstupní strom BVS tak, že vrchol V se dostane do kořene výstupního stromu BVS0, který je platný binární vyhledávací strom.
Příklad:
Kód: Vybrat vše
? transf(t(void,1,t(t(void,5,void),10,void)),5,V).
V = t(t(void,1,void),5,t(void,10,void))
Binární strom je reprezentován pomocí typu
Kód: Vybrat vše
data Bt a = Void
| Node (Bt a) a (Bt a)
Příklad: (indentace ve výstupu pro přehlednost)
Kód: Vybrat vše
> izo 1 Node (Node Void 1 (Node Void 2 (Node Void 0 Void)))
[Node (Node Void
2
(Node Void 0 Void))
1
Void,
Node Void
1
(Node (Node (Void 0 Void)
2
Void)]
N-ární strom je reprezentován datovým typem
Kód: Vybrat vše
data NTree a = Ntree a [Ntree a]
Kód: Vybrat vše
sort NT :: (h->k->Bool) -> Ntree (k, h) -> Ntree (k, h)
Máte k dispozici funkci sort :: (a->a->Bool) -> [a] -> [a]
Příklad
Kód: Vybrat vše
> sortNT (<) (Ntree (1, 'a') [Ntree (3, 'x') [], Ntree (0, 'z') []])
(Ntree (1, 'a') [Ntree (0, 'z') [], NTree (3, 'x') []])
Velký příklad: Problém n obchodních cestujících (přibližné znění)
Můžete si vybrat jeden z těchto jazyků: Prolog, Haskell
Na vstupu je zadán úplný graf G s ohodnocenými hranami, počáteční vrchol V grafu a číslo N. Úkolem je navrhnout heuristiku, která najde N různých cest (kružnic přes všechny vrcholy) tak, aby bylo pokud možno minimalizována maximální délka některé z cest. Cílem není napsat perfektní algoritmus, který najde řešení v nekonečném čase, ale nějaký rozumně rychlý algoritmus. V grafu platí trojúhelníková nerovnost.
V prvním příkladu byla nejasnost zadání, zda-li se vztahuje formulace "cestou z hran s ohodnocením nejvýše Prah" k jednotlivým hranám, nebo k celé cestě. Nakreslili nám na tabuli, že myslí k jednotlivým hranám. Než se tak stalo, ztratil jsem zhruba 10 minut času vymýšlením řešení alternativní verze.
Na vypracování bylo standardně 75 minut, poté následovala krátká pauza a druhá část, na kterou bylo 90 minut.