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 N²-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 N²-tel arányos lépésszámra lesz szükség, ahogy a mellékelt ábra is mutatja:

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/2ⁱ⁺¹ olyan csúcs van, amelynek mindkét ágon k leszármazottja van, ahol 2ⁱ <= k < 2ⁱ⁺¹. 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 2ⁱ⁺¹ 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 2ⁱ⁺¹. 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 2ⁱ⁺¹ * N/2ⁱ⁺¹ = N-nel arányos lépésben megoldható. És ez igaz minden i=0,1,...,log₂N-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.

Megoldásom (nem a hivatalos megoldás!)

A bejegyzés trackback címe:

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.