# ADS B - Housenka.

Obrázek: https://ibb.co/jgQywvn

Nejprve budu předpokládat, že ze stromu odstraním všechny původní listy. S výjimkou toho, že housenka musí někde začít, totiž listy neovlivní to, jak bude vypadat "tělo" housenky (momentálně neřeším, zdali tato housenka bude nejdelší).

Vrcholy, které jsou novými listy, označím za koncové, naopak ty vrcholy se 3 a více sousedy, označím za uzly. Vrcholy s 2 sousedy pak budou průběžné vrcholy.

Při řešení aplikuji DFS postup průchodu grafem. V obrázku začnu v koncovém vrcholu $A$ a otvírám vždy takového souseda, který není otevřený, takže u průběžných vrcholů je jen 1 možnost.

Tímto se dostanu do uzlu $B$ a v obrázku pro zjednodušení jednotlivé větve procházím podle směru hodinových ručiček (červené šipky) a vracím se (žluté šipky) až poté, co jsou všechny větve vyřešeny.

Vrcholy tak navštívím (dostanou se "pod hledáček" algoritmu) dle abecedního pořadí v obrázku.

Nyní samozřejmě potřebuji způsob, jak číslovat velikost housenky. Zde budu potřebovat řešit, kolik listů skutečně jsou sousedy určitého vrcholu. Zdali je vrchol listem se dá snadno zjistit, mám-li daný seznam sousedů. Jelikož však housenka může mít pouze 4 nohy, nemusím počítat nadbytečné listy, nejedná-li se o koncový vrchol (tam můžu pátý list použít jako "hlavičku").

Popsaný algoritmus funguje tak, že pro každý uzel zjistím, které dvě cesty z něj mají nejdelší váhu, ovšem nepočítám cestu směrem k výchozímu vrcholu (ta je jenom jedna, jelikož mám strom).

$1$. Nastavím u vrcholů příznak "list". (Jelikož jsem úlohy na procházení grafů zpravidla řešil pomocí seznamů, tak pro každou vlastnost mohu zřídit jednotlivý seznam, a stejné indexy tak odpovídají stejnému vrcholu).
$2$. Nastavím $vahu$ vrcholů jako $0$, $delku1$ jednotlivých vrcholů jako $1$ a $delku2$ také jako $1$.
$3$. Vyberu jakýkoli list a otevřu jeho souseda.
$4$. Poznačím si, který vrchol tento list otevřel.
$5$. Je-li $vaha$ vrcholu $0$, zjistím, kolik vrcholů jsou jeho listy a nastavím $vahu$ na tuto hodnotu +1 (nejvýše $5$), což znamená, kolik tento vrchol přičítá k délce housenky.
$6$. Postupně projdu všechny neotevřené sousedy, kteří nejsou listy. Narazím-li na takový vrchol, otevřu jej a jdu na $4$.
$7$. Jakmile jsem otevřel všechny vrcholy kromě otevírajícího, spočítám následující: $delka1$ tohoto vrcholu $+ vaha$ otevírajícího vrcholu. Tímto číslem buďto nahradím $delka1$ nebo $delka2$ (nebo ani jedno) otevírajícího vrcholu - musím si pamatovat dvě nejvyšší hodnoty.
$8$. Prohlásím tento vrchol za uzavřený a vrátím se na otevírající vrchol (je to DFS, takže jsem musel již prozkoumat všechny sousedy; navíc zadáním je neorientovaný graf, takže každou hranu mohu projít 2x).
$9$. Pro každý ne-list spočítám $delka1+delka2-vaha$. Nejvyšší hodnota je součástí výsledné housenky; její další dvě části zjistím z toho, který soused má $delka1$ + $vaha$ rovnou hodnotě $delka1$ nebo $delka2$ tohoto vrcholu.
$10$. Poté již postupuji pouze pomocí hodnoty $delka1$ jednotlivých vrcholů. Vždy si vyhlédnu toho souseda, ve kterém jsem ještě nebyl (při hledání housenky) a beru vrchol s maximální hodnotu $delka1$, přičemž tebtokrát to může být i list.

## Správnost

Konečnost - z obrázku je vidět, že algoritmus začíná "obracet", když se dostanu do konečného vrcholu. Ten totiž nemá žádného jiného nelistového souseda, takže se musí uzavřít a vepsat svou hodnotu do předchozího vrcholu (rozeberu dále). Takto postupuji, než uzavřu jednu větev z nějakého uzlu a začnu prohledávat další větev. Tím prozkoumám všechny vrcholy.

Hodnoty ($delka1$, neuvedu-li jinak) jednotlivých vrcholů na cestě vedoucí ke konečnému vrcholu bez uzlu jsou triviální; předpokládejme, že všechny vrcholy budou mít $vahu$ 1, takže hodnota $delka1$ bude postupně $1,2...$ od konce (např. od vrcholu $E$). První uzel na této cestě ($D$) pak bude mít hodnotu $delka1$ závisející na nejdelší (nejhodnotněší) větvi, která je "za" ním. Tato hodnota pak ovlivní předcházející uzly ($B...$)

Jelikož však DFS se vrací do prvního vrcholu poté, co jsou všechny vrcholy prozkoumány, nejvyšší hodnotu by měl vždy výchozí vrchol. Ten však volím víceméně náhodně, a nemusí být tak vůbec součástí housenky.

K tomu slouží hodnota $delka2$, která měří hodnotu druhé nejlepší cesty z daného vrcholu. (Samozřejmě, není-li vrchol uzlem, pak má pouze jednu neotevírající cestu a tato hodnota pak nemá žádný význam.) V obrázku má tak uzel $B$ nejvyšší hodnotu, ale ze všech nelistů by měl vrchol $A$ nejvyšší hodnotu, i když je vidět, že cesta $CBDG$ je delší než cesta $ABDG$. To z toho důvodu, že algoritmus přiřadil vrcholům $C$ i $H$ hodnotu 1, nicméně díky $delka2$ znám váhu cesty $CB$, a vím tak, že bude lepší než cesta $BA$.

Desátý krok pouze řeší ten problém, že začínám ve středu housenky. Proto musím najít její začátek a konec, vyberu tak dvě nejlepší cesty a jdu po nich hledáním následujícího vrcholu s nejlepší hodnotou. Tím projdu v každém směru po nejlépe ohodnocené cestě a skončím v listu konečného vrcholu.

## Složitost (horní odhad)
Algoritmus má dvě větší části: zapisování hodnot a najítí housenky ($9.-10.$)
Jelikož při zapisování cest pouze procházím graf a nemusím nic přepočítávat vícekrát, měla by složitost být jen $O(m+n)$.
Při hledání housenky mohou být problémy s hledáním maxima. Nicméně platí, že jakmile maximum (kterým směrem se mám "posunout") najdu, všechny nepotřebné vrcholy již mohu ignorovat, takže složitost bude $O(n)$.