Fórum studentů MFF UK

3. Najbližšie k odpovedi je asi toto: http://cgi.csc.liv.ac.uk/~michele/TEACH ... 10.4.4.pdf - "Clever Greedy Algorithm"

Keby sa niekomu nechcelo čítať a lúštiť, (čo sa mne určite nechcelo):
Buď graf
,
kde L je n vrcholov. následne množina n/i vrcholov, ktoré sú spojené postupne s i-ticou vrcholov z L. Teda v každý spojený s 1 vrcholom z L, v každý spojený s dvojicou vrcholov z L ... a jediný vrchol spojený so všetkými vrcholmi z L. (pre referenciu kukni na obrázčok vyššie v pdf).

Aproximačný algoritmus vezme vždy vrchol z pre max i. Tak teda použije vrcholov (v prípade násobku (n,n-1,...,1) práve toľko vrcholov), pričom optimálny vezme vrcholy z L, teda n vrcholov. Odtiaľ asi jasne vidno, že APPROX > 2OPT.

Nuž, i je tu háčik, a síce, že v počiatočnom bode chodu aproximačného algoritmu majú vrcholy z L rovnaký stupeň ako v maximálnom R. Ale ako sa aj v pdf vyššie píše, náhoda je blbec, teda ak sa podarí, podarí sa aj riadna pomerová chyba.
Ono dalo by sa aj vypočítať priemerná odchýlka nejakou strašidelnou sumou všetkých možných chodov approximačného algoritmu (čo by vyšlo n/2... žeby? Možno?), no to už asi zabŕdam do iného predmetu. Berte teda na vlastné uváženie.

jo mas pravdu, sem se prekoukl, sem myslel ze odstrnuje sousedici vrcholy

qk píše:nomohla by se ta trojka resit tak, ze bych si vzal graf, kde by byly 2 hvezdy (stred + dejmetomu 12 vrcholu spojenych se stredem) a ty by byli spojene useckou. Tenhle algoritmus by potom vybral jeden ze stredu ty hvezdy a vzal ho a i jeho sousedy, takze by zustalo 12 rozpojenych vrcholu...takze 13 vrchlolu je k, zatimco idealni reseni ma k jen dva....nebo je to blbost?

Pokud jsem to dobre pochopil, tak algoritmus bere vrcholy od tech s nejvetsim stupnem, takze by vzal jeden stred, dal ho do pokryti, vsechny hrany s nim spojene odstranil a pak sel na druhy stred. Ten by taky hodil do pokryti a uz by mu nezustala zadna hrana. Takze idealni pripad.

nomohla by se ta trojka resit tak, ze bych si vzal graf, kde by byly 2 hvezdy (stred + dejmetomu 12 vrcholu spojenych se stredem) a ty by byli spojene useckou. Tenhle algoritmus by potom vybral jeden ze stredu ty hvezdy a vzal ho a i jeho sousedy, takze by zustalo 12 rozpojenych vrcholu...takze 13 vrchlolu je k, zatimco idealni reseni ma k jen dva....nebo je to blbost?

K tomu 2. pr. este, ze mi sme to na cvikach robili aj pomocou 3 - SAT (t. j. v kazdej klauzuli, ci co to je su prave tri literaly).
A to tak, ze pre kazdu klauzulu sa nakresli trojuholnik, pre kazdy literal hrana (u, non(u)), ktora sa potom pripoji k trojuholniku danej klauzule a to tak, ze ak je v klauzuli u, tak sa pripoji k trojuholniku, u, inac non(u).
A potom, kladne ohodnotenie jednotlivych premennych dava k-vrcholove pokrytie daneho grafu a k=<pocet premennych> + 2*<pocet klauzuli>.
Plus este v kazdom trojuholniku treba oznacit dva dalsie vrcholy (preto ta dvojka v tom vztahu).

A tak.

Tak ten prvni nebyl zas tak tezky. nechate setridit ty dve posloupnosti delky n a pak staci porovnat nejmensi z prvni posloupnosti s nejvetsim v druhe posloupnosti, druhy nejmensi s druhym nejvetsim ... atd az porovnate nejvetsi z prvni s nejmensim v druhe. Ty ktere vypadnou z techto porovnani jako mensi tvori n-tici mensich, ty vetsi tvori n-tici ... vetsich. Tedy staci vam k tomu n komparatoru v jedne vrstve. K dukazu ... no ono je to skoro videt. Kdyz to porovnavate tak az do urciteho indexu vsechny ty porovnani "vyhrava" jedna posloupnost. (bude tam stejna nerovnost bud > nebo <). No a kdyz to dopadne opacne, tak zase musi uz porad vyhravat ta druha posloupnost. Jestli to neni jasny doporucuju si to nakreslit (take jsem to tak nejdrive udelal), treba pro 2n=8.

Po ustnim jsem se ptal na ten treti ... a ten odhad nefunguje. Ale konstrukce protiprikladu je obtizna (podle slov zkousejiciho). Zacina se nejak s (alespon)12-dvojicema vrcholu spojene hranou (dvojice mezi sebou ma hranu)... pod to se prida vrstva o 1 mensi, napojena na tu jednu radu dvojic, pod to dalsi vrstva, pod to dalsi .. az zbyde jeden vrchol. Ten algoritmus bude postupovat od spoda a postupne ubirat ty vrstvy az zase zbudou ty dvojice (tu pak nejak rozebere). Pritom optimum jsou vrcholy z dvojice, na ktere jsou napojeny vsechny ty spodni vrstvy ...

Druhá úloha sa dokazuje pomocou kliky a doplnkového grafu, kde doplnkový graf grafu G(V,E) je graf G'(V,E'), ktorý obsahuje všetky hrany, ktoré pôvodný graf neobsahuje. Potom platí, že vrcholy, ktoré v grafe G NETVORIA kliku, sú vrcholovým pokrytím grafu G'. Skúste si to nakresliť a hneď vám to bude jasné.

Tak to je maso.

Tak dnes nas na pisomke (teda aspon mna) Cepek nemilo prekvapil tymito prikladmi:

1. Predpokladejme, ze mame 2n (po dvou ruznych) prvku a1,a2,...,a2n, ktere chceme rozdelit na n nejmensich a nejvetsich. Dokazte, ze pote co tridici sit paralelne setridi prvky a1,...,an a prvky an+1,an+2,...,a2n postacuje jiz k dosazeni vysledku sit konstantni hloubky.

2. Problem Vrcholoveho pokryti (VP) lze sformulovat nasledovne:
Zadani: Neorientovany graf G(V,E) a prirozene cislo k.
Otazka: Existuje podmonozina vrcholov W (W je podmnozina V) velikosti nejvyse k, ktera pokryva vsetky hrany, t.j. W takova, ze kazda hrana ma aspon jeden zo svojich koncovych vrcholov na mnozine W?
Dokazte, ze je tento porblem NP-uplny. K dukazu jeho NP tezkosti pouzijte nektery z NP-uplnych problemu probiranych na prednasce, t.j. nektery problem z mnoziny(KLIKA, HK, TSP,SP,ROZ,SAT)

3. Mejme nasledujici aproximacni algoritmus pro hledani minimalneho Vrcholoveho Pokryti VP (t.j VP obsahujici nejmensi mozny pocet vrcholu). Dokud graf obsahuje nejake hrany, tak opakuj nasledujici akci: vyber vrchol nejvyssiho stupne (pokud je takych vice, tak vyber libovolny z nich), pridej ho do pokryti a z grafu odstran vsechny hrany incidentni s vybranym vrcholem. Dokazte nebo vyvratte: uvedeny aproximacny algoritmus ma (na mnozine vsech zadani VP) pomerovou chybu 0<=2 (0 mene rovno 2).


NEviem ako vam, ale mne to nepride az tak jednoduche. Ked som uz na tej skuske bol tak som si to aspon opisal, aby ste si to tu precitali. Ja som z toho nic neodovzdal.
Ak niekto viete ako vyriesit nejaky z tych to prikladov tak to tu prosim hodte.

vela stastia.