NOVINKA - Vstup do světa AI s ONLINE víkendovým kurzem Práce s umělou inteligencí od A do Z. Přihlas se ještě dnes!
NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 18:35

Mam zadaný ukol, který delam asi 2 dny a nejsem schopný to nejak spackat. Tak dkyby nahodou si stim někdo vedel rady. Mam cas jenom do pulnoci pak to musi odevzdat. Diky.

Implementujte algoritmus pro nalezení optimálního řešení Set-Cover problému. Předpokládejte, že universum je podmnožinou přirozených čísel. Vstupní instanci program načte z textového souboru. Každý z řádků tohoto souboru obsahuje mezerou oddělená čísla, a odpovídá jednomu prvku ze systému podmnožin universa. Samotné universum je pak tvořeno sjednocením těchto podmnožin.

Odpovědět
16.12.2012 18:35
Jste dobří jen v tom, co vás baví.
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Mini
David Hartinger:16.12.2012 18:49

Nějaké lidštější zadání by nebylo?

Nahoru Odpovědět
16.12.2012 18:49
New kid back on the block with a R.I.P
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 19:21

Taky si rikam, proste vygenerovat podmnoziny nejake mnoziny, a poté zjistit nejmenši pokryti no, prsote mnozinu ktera pokryva celou mnozinu(což byal ta vstupni)

Nahoru Odpovědět
16.12.2012 19:21
Jste dobří jen v tom, co vás baví.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:16.12.2012 19:25

Jestli to chapu dobre:

  • Mas soubor, ve kterem jsou radky a na kazdem radku jsou v textove forme cisla oddelena mezerou
  • Mas zjistit vsechny cisla, ktery se v souboru vyskytujou

je to tak?

Nahoru Odpovědět
16.12.2012 19:25
https://www.facebook.com/peasantsandcastles/
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 19:28

No zjistit, hlaven pak zjistit to opkryti mnoziny. nejmenší. Jinak Set-Cover je progr. problém viz. http://en.wikipedia.org/…over_problem

Nahoru Odpovědět
16.12.2012 19:28
Jste dobří jen v tom, co vás baví.
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 19:33

Jinak tady je pdf kde je o tom napsano i s pseudokodem, ale moje hlava to prsote porad nebere. http://leteckaposta.cz/597785411
je to asi ve stredu, je tam nadpis Set-Cover

Editováno 16.12.2012 19:34
Nahoru Odpovědět
16.12.2012 19:33
Jste dobří jen v tom, co vás baví.
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:16.12.2012 19:38

Mělo by to být podle tohoto:
http://en.wikipedia.org/…over_problem

Na vstupu je n podmnožin, jejichž sjednocením je universum. Naším úkolem je vyházet co nejvíc podmnožin tak, aby sjednocením zbylých podmnožin bylo stále umiversum.

Nahoru Odpovědět
16.12.2012 19:38
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:16.12.2012 19:38

Mělo by to být podle tohoto:
http://en.wikipedia.org/…over_problem

Na vstupu je n podmnožin, jejichž sjednocením je universum. Naším úkolem je vyházet co nejvíc podmnožin tak, aby sjednocením zbylých podmnožin bylo stále umiversum.

Nahoru Odpovědět
16.12.2012 19:38
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 19:41

Ano přesně tak ;-). Je to ukol do Algoritmické matematky, meli sme toho vic. Jediny tohle fakt nevim jak udelat. Tak kdyby ste mohli helpnout. Na jazyce nezalezi (Java, C#), hlavně ne najkej lisp, scheme atd :D

Nahoru Odpovědět
16.12.2012 19:41
Jste dobří jen v tom, co vás baví.
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Mini
Kit:16.12.2012 19:53

Podle toho PDF bys na to měl jít backtrackingem. Odebrat jednu podmnožinu a ověřit si, zda je stále podmínka splněna. Pokud ano, odebrat další. Pokud ne, vrátit se o krok zpět a odebrat jinou. To vše nejlépe rekurzí.

Úspěšný stav si ulož, ale jen pokud je počet podmnožin menší, než předchozí uložený stav.

Nahoru Odpovědět
16.12.2012 19:53
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 20:00

Backtracking neni nutný, mužeme pouzit i Greedy metodu. Tohle chápu, ale nedal sem to dohromady za celej den. Sem pišu prtoože sem zoufalej už

Nahoru Odpovědět
16.12.2012 20:00
Jste dobří jen v tom, co vás baví.
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 20:10

Navíc na to mam necely 4 hodiny už. Mam to posalt do 12ti hodin. Kite nepořešil bys to? Je mi to blbý ale bud tohle nebo přisti rok ten predmet

Nahoru Odpovědět
16.12.2012 20:10
Jste dobří jen v tom, co vás baví.
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Mini
Kit:16.12.2012 20:26

Jenže já za tebe nemůžu řešit tvé úkoly. Zkusil jsem se podívat na tu problematiku, protože mě to zaujalo, ale dělat se mi to nechce.

Ještě mě napadlo jednodušší řešení u toho backtrackingu. Jako u batohu. Prostě pořád přidávat, dokud není splněna podmínka universa. Poznamenat řešení, pokud je kratší. Pak couvnout a pokračovat dalšími větvemi. Pokud jsou větve vyčerpány, opět couvnout.

S rekurzí bys to měl mít za chvilku hotové.

Nahoru Odpovědět
16.12.2012 20:26
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:16.12.2012 20:29

Tady jsem se o to pokusil, snad jsem to pochopil dobře. Není to moc otestovaný, nejsou ošetřený chyby...
http://satik.eu/…setcover.zip

Nahoru Odpovědět
16.12.2012 20:29
https://www.facebook.com/peasantsandcastles/
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 20:38

To já pravě taky si myslel. Ale nevědel sem si pak rady. Ok no, Kdyby nahodou se někomu chtělo tak do 12ti. Kdybych nebyl tak zoufalej tak sem nepiši. Ale jde mi o kredity ve skole no.

Nahoru Odpovědět
16.12.2012 20:38
Jste dobří jen v tom, co vás baví.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Mini
Luboš Běhounek Satik:16.12.2012 20:39

Viz můj předchozí příspěvek, je to přes rekurzi.

Btw o kredity jde tobe, ne nám, tak se tu kvůli tvému úkolu nikdo nepřetrhne, jen teď jsi měl štěstí, že jsem měl čas a chuť si tohle vyzkoušet napsat ;)

Editováno 16.12.2012 20:43
Nahoru Odpovědět
16.12.2012 20:39
https://www.facebook.com/peasantsandcastles/
Avatar
Mini
Člen
Avatar
Mini:16.12.2012 20:42

To jo :D Takovou hlavu jak vy bych chtěl mět :D Každopadně moc děkuju a omlouvam se za to že sem pišu aby ste mi něco udělali. Vím jaky toje a jak to vypadá ale byl sem zoufalej. Zachranil si mi 5 kreditu :) Díky moc :-)

Nahoru Odpovědět
16.12.2012 20:42
Jste dobří jen v tom, co vás baví.
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:16.12.2012 21:07

Týjo, to je rychlost :) Nechceš to sem přidat do ukázkových programů? Práce s množinami se někomu určitě ještě hodí.

Nahoru Odpovědět
16.12.2012 21:07
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:16.12.2012 21:09

Ok :)

Nahoru Odpovědět
16.12.2012 21:09
https://www.facebook.com/peasantsandcastles/
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 19 zpráv z 19.