od Osiris » 4. 2. 2009 15:42
Snad jen načrtnu svoje řešení (měl jsem vše dobře)
1) Pouze aplikace algoritmu na hledání 2-souvislých komponent. Jednoduše otestujeme, zda 2-souvislá komponenta se sestává pouze z 1 hrany (pak je ta most).
2) Uděláme si hezký rekurzivní algoritmus. Vezmeme první formuli a ohodnotíme první literál na 1. Pak smažeme ty formule, kde je literál ohodnocen na 1 a ohodnotíme ty formule, kde je negovaný - vyjdou 1 formule, které musí být ohodnoceny vždy na 1. Po smazání se zavoláme rekurzivně na zbytek neohodnocených formulí. Pokud to nejde splnit, vrátíme se a ohodnotíme druhý literál na 1. Pokud i to je nesplnitelné, pak je formule celá nesplnitelná. Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?
3) Dělá se převodem SATu, červené jsou klauzule, černé proměnné a jejich negace, hrany vedou mezi proměnnými a jejich negacemi a mezi literály a formulemi, které je obsahují. Pokud existuje maximální nezávislá černá množina, dostaneme splňující ohodnocení a pokud neexistuje, formule nejde splnit.
Pak na ústním jsem dostal takovou směsku okolo #P, silná NP-úplnost, aproximační algoritmy apod. po 40 minutách jsem odcházel s 1 v indexu. Hodně štěstí ostatním!
Snad jen načrtnu svoje řešení (měl jsem vše dobře)
1) Pouze aplikace algoritmu na hledání 2-souvislých komponent. Jednoduše otestujeme, zda 2-souvislá komponenta se sestává pouze z 1 hrany (pak je ta most).
2) Uděláme si hezký rekurzivní algoritmus. Vezmeme první formuli a ohodnotíme první literál na 1. Pak smažeme ty formule, kde je literál ohodnocen na 1 a ohodnotíme ty formule, kde je negovaný - vyjdou 1 formule, které musí být ohodnoceny vždy na 1. Po smazání se zavoláme rekurzivně na zbytek neohodnocených formulí. Pokud to nejde splnit, vrátíme se a ohodnotíme druhý literál na 1. Pokud i to je nesplnitelné, pak je formule celá nesplnitelná. Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?
3) Dělá se převodem SATu, červené jsou klauzule, černé proměnné a jejich negace, hrany vedou mezi proměnnými a jejich negacemi a mezi literály a formulemi, které je obsahují. Pokud existuje maximální nezávislá černá množina, dostaneme splňující ohodnocení a pokud neexistuje, formule nejde splnit.
Pak na ústním jsem dostal takovou směsku okolo #P, silná NP-úplnost, aproximační algoritmy apod. po 40 minutách jsem odcházel s 1 v indexu. Hodně štěstí ostatním! :)