Převod na CNF

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Převod na CNF

Příspěvek od Ellrohir »

Jsem asi úplně blbej (a je to taky dost daný tím, že jsem díky mé tristní lenosti vynechal řadu přednášek, kde se asi právě tyto věci řešily :| ), ale nejsem naprosto schopen poradit si se zadáním :

"Převeďte problém Hamiltonovské kružnice do CNF"

Co to je CNF vím, co to je Hamiltonovská kružnice vím taky...ale jak z ní udělat nějakou "konujkci disjunkcí logickejch výrazů" to nedávám :?

mám dojem, že jsem u někoho v učebních materiálech před zkouškou viděl něco jako "algoritmus převodu problému", kterým by se to snad dalo řešit, ale ani s pomocí mistra Googla ho teď nemůžu najít...poradíte někdo napůl zoufalému "dostmožnáposlednípůlrok" matfyzákovi? :oops:
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Převod na CNF

Příspěvek od Osiris »

Ellrohir píše:...
Nedalo by se prostě říct, že SAT (odpoví ano, pokud je formule v CNF splnitelná) je NP-úplný, a problém HK leží ve třídě NP (snad jasné), proto převod musí existovat? Kdybys to chtěl formálně, tak si sežeň povalující se na foru skripta ze Složitosti I, kde se tohle předvádí.
Osiris
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Převod na CNF

Příspěvek od Ellrohir »

no to nevím, jestli by to stačilo, možná jo, ale v tomhle fakt plavu hrozně...mám následující příklad :

43 Hamiltonovská kružnice ZAPOCET
Dokažte: HAM "menší nebo rovno"p CNF. (Motivace: programování v
CNF.)
Pozn. Kódovanie hrán vs. kódovanie poradia vrcholov.
A vyjadrenie (dostatocných) omedzení. (Stacia 2 zo 4:
1x aspon 1 a 1x najviac jeden, alebo duálne)
idea: kodovanie kruznice: premenna xv,i – ak vrchol v
je i-ty na ham. kruznici.
kodovanie omedzeni (v CNF!): vrchol v je na nejakej
pozicii (tj. na Ham. kruznici) prave raz (tj. aspon raz
a najviac raz), na pozicii i je prave jeden vrchol (dtto),
vrcholy u a v na poziciach i a i+1 smu byt sucasne, ak
je medzi u a v hrana. (trikove)
Odhadnite pocet omedzeni (a ich dlzku), resp. celkovy
pocet premennych. (Je polynomialny?)

a "naveden" jsem byl, že mám ke splnění příkladu převést Hamiltonovu kružnici na CNF...jelikož nevím, jak se to má dělat, tak klidně "vezmu za vděk" tím, co říkáš ty a hádat se o to nebudu...otázka je, co na to cvičící, v tomto případě Hric (ano, pořád ještě nemám zápočet z ADS II a už začíná být sakra pozdě :roll: )
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Převod na CNF

Příspěvek od Osiris »

Ellrohir píše:no to nevím, jestli by to stačilo, možná jo, ale v tomhle fakt plavu hrozně...mám následující příklad :

43 Hamiltonovská kružnice ZAPOCET
Dokažte: HAM "menší nebo rovno"p CNF. (Motivace: programování v
CNF.)
Pozn. Kódovanie hrán vs. kódovanie poradia vrcholov.
A vyjadrenie (dostatocných) omedzení. (Stacia 2 zo 4:
1x aspon 1 a 1x najviac jeden, alebo duálne)
idea: kodovanie kruznice: premenna xv,i – ak vrchol v
je i-ty na ham. kruznici.
kodovanie omedzeni (v CNF!): vrchol v je na nejakej
pozicii (tj. na Ham. kruznici) prave raz (tj. aspon raz
a najviac raz), na pozicii i je prave jeden vrchol (dtto),
vrcholy u a v na poziciach i a i+1 smu byt sucasne, ak
je medzi u a v hrana. (trikove)
Odhadnite pocet omedzeni (a ich dlzku), resp. celkovy
pocet premennych. (Je polynomialny?)

a "naveden" jsem byl, že mám ke splnění příkladu převést Hamiltonovu kružnici na CNF...jelikož nevím, jak se to má dělat, tak klidně "vezmu za vděk" tím, co říkáš ty a hádat se o to nebudu...otázka je, co na to cvičící, v tomto případě Hric (ano, pořád ještě nemám zápočet z ADS II a už začíná být sakra pozdě :roll: )
Vždyť tam máš napsanou ideu, tak kde je problém? Prostě vytvoříš hromadu formulí v CNF.

Alespoň ti dám radu na tohle, ostatní je obdobné:
vrchol v je na nejakej pozicii (tj. na Ham. kruznici) prave raz (tj. aspon raz a najviac raz)

alespoň jednou: F1 = x1i OR x2i OR x3i OR ... OR xvi
nejvýše jednou: F2 = Pro každé dva k nerovna se l: NOT(Xki) OR NOT(xli)

Zdůvodnění: alespoň jednou v F1 musí být xki jednička - jinak by F1 nebyla splňěna
nejvýše jednou: předpokládejme, že pro k nerovna se l máme obě na hodnotě 1. Pak NOT(1) OR NOT(1) = 0 - SPOR, nesplnili jsme formuli

Počet formulí F1 je 1.
Počet formulí typu F2 je v*v

No a takhle to mechanicky přepíšeš dál, celé ti to psát nebudu.
Osiris
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Převod na CNF

Příspěvek od Ellrohir »

já jsem zřejmě silně zabržděnej a mezi více nadanými tady budu pravděpodobně za debila (daný zjevně tím, že jsem vtipně "vynechal" přednášky, kde se tohle bralo a z prstu si to člověk holt nevycucá, když to v životě neslyšel), ale ani tuhle nápovědu úplně nepobírám...resp. chápu proč je F1 a F2 zapsaný tak, jak jsou, ale nechápu, co si mám představit pod těma "xkama"...jasně, sou to nějaký nuly a jedničky, ale jak je určím, nebo co představujou? :?:

nehledě na to, že - kdybych tohle "slepě opsal" - nemám stejně ponětí jak udělat to "vrcholy u a v na poziciach i a i+1 smu byt sucasne, ak je medzi u a v hrana."

jinak možná by bylo lepší, než se mi to snažit zdlouhavě vysvětlovat, přihrát link na nějakej text, ve kterým problematiku obecně nějak hezky vysvětluje přednášející osoba...to je asi to, co mi nejvíc chybí...zatím jsem nenašel na webu nic, odkud bych to sám pochopil... :idea:
Schiroo
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 1. 2. 2006 13:54
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Převod na CNF

Příspěvek od Schiroo »

Zadání:
Mám graf G(V,E), černou krabičku, která řeší SAT.

Postup:
Očísluju vrcholy grafu od 1..n (abych mohl určit, které pozici budu říkat první na HK).
Pro každý vrchol definuju Xvi (proměnná X s indexy v,i), která bude mít hodnotu:
1 - pokud vrchol v leží na i-té pozici v hamiltonovské kružnici
0 - jinak
Tedy proměnných Xvi bude celkem n^2, neboť vrcholů grafu mám n a různých pozic na hamiltonovské kružnici mám také n. Speciálně pro první vrchol (označme ho p) bude platit Xp1 = 1. Pokud by mi pro graf, jehož vrcholy označím abcd řekl SAT, že Xa1 = 1, Xb3 = 1, Xc4 = 1, Xd2 = 1, pak hamiltonovskou kružnici tvoří vrcholy v pořadí adbc.

Poté sestavím formule:
1,
Pro každý vrchol do formule přidám
vrchol v se vyskytuje alespoň na jedné pozici aneb vrchol (v je na pozici 1 v HK) nebo (v je na pozici 2 v HK) nebo ...nebo (v je na pozici n v HK) neboli (Xv1 = 1) or (Xv2 = 1) or ... (Xvn = 1) neboli
Xv1 or Xv2 or Xv3 or ...

2,
Pro každou dvojici vrcholů do formule přidám (jako náhradu za tvrzení, že se vrchol vyskytuje jen na jedné pozici)
žádné dva u,v se nevyskytují na stejné pozici
aneb
[ NOT(u je na pozici 1) or NOT(v je na pozici 1) ] AND [ NOT(u je na pozici 1) or NOT(v je na pozici 2) ] AND ... AND [ NOT(u je na pozici n) or NOT(v je na pozici n) ]
aneb
[NOT(Xu1) or NOT(Xv1)] AND ... AND [NOT(un) or NOT(Xvn)]

3,
Poté pro každou 'nehranu', tj. dvojici vrcholů u,v, které nejsou spojeny hranou přidám (dělám část vrcholy u a v na poziciach i a i+1 smu byt sucasne, ak je medzi u a v hrana):
když u je na pozici 1, pak v není na pozici 2 AND když u je na pozici 2, pak v není na pozici 3 AND ..
aneb
Xu1 => NOT(Xv2) AND Xu2 => NOT(Xv3) AND ... AND Xu{n-1} => NOT(Xvn)
aneb
[ NOT(Xu1) OR NOT(Xv2) ] AND [ NOT(Xu2) OR NOT(Xv3) ] AND ... AND [ NOT(Xu{n-1}) OR NOT(Xvn) ]

Nakonec spojím formule z 1,2,3 pomocí AND, neboť chci, aby platilo všechno. Nyní bych měl ověřit, že délka vytvořené formule je polynomiální, což přenechávám za DU :) Na tuto mojí formuli pustím SAT, on mi právě n proměnných Xij ohodnotí 1 (protože jsem ho vymýšlel, aby to tak musel udělat).

Doufám, že to je blbovzdorné (a dobře :D )
May the source be with you!
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Převod na CNF

Příspěvek od Ellrohir »

tak zdá se, že už je mi to mnohem jasnější...určitě moc díky za čas na mě :)

jenom ale - nechybí tam ještě 4. formule, která by zajišťovala, že když hrana v grafu JE, tak vede mezi vrcholy na sousedních pozicích na ham. kružnici?

takhle bych jí zapsal...

[(Xu1) and (Xv2)] or … or [(Xu{n-1}) and (Xvn)]


nebo stačí ta třetí formule, aby vyloučila možnost, že mezi 2 vrcholy bude hrana "nevhodně" (mezi 1. na HK a třeba 6. na HK)...podle mě ne...podle mě ta třetí jenom říká, že když mám 1. vrchol na HK a z něj nevede hrana do v, tak v není 2. vrchol na HK...
Schiroo
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 1. 2. 2006 13:54
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Převod na CNF

Příspěvek od Schiroo »

podle mě ta třetí jenom říká, že když mám 1. vrchol na HK a z něj nevede hrana do v, tak v není 2. vrchol na HK...
Ano, říká přesně tohle. Ale stačí to - cíl je říct, že pokud po sobě dva vrcholy následují v HK, pak mezi nimi je hrana.
když hrana v grafu JE, tak vede mezi vrcholy na sousedních pozicích na ham. kružnici?
Tohle nechceš, aby platilo. Říká to, že každá hrana v grafu se musí někde vyskytnout na HK, což není pravda. Na HK bude každý vrchol z grafu (plyne ze zadání HK), ale ne každá hrana. HK má n vrcholů a n+1 hran (je to kružnice), zatímco graf může mít až (n nad 2) hran - tedy spousta hran z grafu nebude na HK.
aby vyloučila možnost, že mezi 2 vrcholy bude hrana "nevhodně" (mezi 1. na HK a třeba 6. na HK)...podle mě ne...
Hrana mezi 1. a 6. vrcholem na HK mi vůbec nevadí, ať tam klidně je (takových tam bude hodně - , a všechny ty, které jsem nevybral do HK budou spojovat některé vrcholy z HK).
May the source be with you!
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Převod na CNF

Příspěvek od Ellrohir »

aha...takže jsem to nepochopil zas tak dobře, jak jsem myslel :o chyba byla nejspíš v pochopení zadání (sem myslel, že tohle má o grafu říct, jestli to je HK - to jest, že to je cyklus přes všechny vrcholy a nic dalšího)...už se nehádám :) a ještě jednou díky :wink:
Schiroo
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 1. 2. 2006 13:54
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Převod na CNF

Příspěvek od Schiroo »

Není zač, rád jsem zavzpomínal :) Cyklus přes všechny vrcholy by znamenal totéž, jako 'je to cyklus a je to souvislé'' a to bych si dovolil řešit i v lineárním čase :D
May the source be with you!
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“