Fa – megoldás

2013.04.03. 05:46

Az eredeti feladat itt.

Megoldás

A legegyszerűbben úgy oldhatjuk meg a feladatot, ha minden csúcsra leellenőrizzük, hogy teljesíti-e a feladat feltételét, majd ezek közül megadjuk a gyökérhez legközelebbit. Rögzített csúcsra az ellenőrzést egy ügyes szélességi kereséssel oldhatjuk meg, például úgy, hogy míg az egyik ág irányában bejárjuk a gráfot, minden meglátogatott csúcsnak eltároljuk a (másik ágbeli) tükörképét, és figyeljük, hogy ellentmondást kapunk-e. Ez tehát O(N) lépésben eldönthető, vagyis az összes csúcsot N2-tel arányos időben tudjuk megvizsgálni. Ezek után még egy szélességi kereséssel megkereshetjük a gyökérhez legközelebbi jó csúcsot.

Az izgalmasabb kérdés az, hogy hogyan lehet ezt optimalizálni. Először is észrevehetjük, hogy teljesen fölösleges olyan csúcsra ellenőrizni, amelyből csak egy ág vezet ki (itt csak óvatosan: ha egy ága sincs, akkor viszont jó a csúcs). Az is egy természetes hozzáállás, hogy ahelyett, hogy minden csúcsot megvizsgálnánk, majd szélességi kereséssel megkeresnénk a legközelebbi jót, az egész ellenőrzősdit egy nagy szélességi bejárásba pakoljuk, és a csúcsokat a gyökértől való távolság szerinti sorrendben vizsgáljuk. Vagyis amint találtunk egy jó csúcsot, befejezhetjük a programot, hiszen az automatikusan egy gyökérhez legközelebbi lesz. Sajnos azonban ezek nem javítanak érdemben a futásidőn: bizonyos esetekben továbbra is N2-tel arányos lépésszámra lesz szükség, ahogy a mellékelt ábra is mutatja:tst13_fa.png

Ehhez képest meglepő lehet, hogy egy harmadik egyszerű észrevétel (ami valójában az elsőnek a továbbfejlesztett változata) drasztikusan lecsökkenti a futásidőt: ugyanis elég csak olyan csúcsokat megvizsgálni, amelyeknek ugyanannyi leszármazottja van mindkét ágon. A meglepetést valószínűleg nem csökkenti, ha azt állítom, hogy ezeknek a csúcsoknak a megvizsgálása összesen O(N log N) lépésben megoldható. No de miért is? A dolog azon múlik, hogy összesen legfeljebb N/2i+1 olyan csúcs van, amelynek mindkét ágon k leszármazottja van, ahol 2i <= k < 2i+1. Ez azon múlik, hogy ilyen csúcsok közül egyik sem lehet leszármazottja a másiknak (ha az A csúcs a B-nek leszármazottja, akkor a B-nek legalább 2i+1 leszármazottja van az A felőli ágon), tehát azok diszjunkt részfáknak a gyökérpontjai, és minden részfa mérete legalább 2i+1. Namost, ha egy csúcsnak k leszármazottja van mindkét ágon, akkor azt k-val arányos lépésben meg tudjuk vizsgálni, szóval az összes szóban forgó csúcs ellenőrzése 2i+1 * N/2i+1 = N-nel arányos lépésben megoldható. És ez igaz minden i=0,1,...,log2N-re, szóval a futásidő valóban O(N log N). Ehhez persze előre ki kell számolni minden csúcsra a jobb és bal oldali leszármazottak számát, de ez megintcsak lineáris időben megoldható egy szélességi kereséssel.

Megjegyzés: Most, hogy ezt láttuk, igazából az is belátható, hogy az eredeti algoritmus mindenféle optimalizáció nélkül is O(N log N) időben fut. Pontosabban csak annyira kell figyelni, hogy a csúcs megvizsgálásakor a szélességi keresés azonnal megszakadjon, amint ellentmondást talál a két ág között. Így a lépésszám nem a részfa méretével, csak a két ág közül a kisebbének a méretével lesz arányos, és a fenti gondolatmenet ugyanúgy működik.
Megoldásom (nem a hivatalos megoldás!)

A bejegyzés trackback címe:

https://versenyprogramozas.blog.hu/api/trackback/id/tr385164524

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.