ranní tělocvik - řešení

Nepochopili jste zadání či naopak vzorové řešení? Chcete se zeptat na některé jiné algoritmy?
Zamčeno
dzejkob
Příspěvky: 5
Registrován: 03-03-2018 18:59
Škola: Soukromá střední škola výpočetní techniky, Litvínovská 600 Praha 9
Rok ukončení studia: 2018

ranní tělocvik - řešení

Příspěvek od dzejkob »

Již jsem obdržel ohodnocení mého řešení druhé úlohy - a nemohu se ubránit reakci. Především tento bod:

"b) Algoritmus opravdu pokryje některé případy, ovšem zdaleka ne všechny."

Netrpím přesvědčením, že moje řešení je nějak přehnaně efektivní - nicméně stále jsem toho názoru, že je zcela funkční. Dívám se tedy znovu do zadání a čtu:
"Délka vlákna mezi pavouky A a B je minimální počet pavouků přes které musíme projít, abychom se dostali po vlákně od pavouka A k pavoukovi B" a "detekci existence a případně nalezení postavení tří hráčů takového, že mezi
každou dvojicí hráčů je stejná minimální délka vlákna".

Co jiného je "minimální počet pavouků přes které musíme projít" než nález nejkratší / optimální cesty? Moje řešení je tedy jednoduchá implementace A* algoritmu, kdy jednoduše zvaliduji nejkratší cesty jednotlivých hráčů a když se rovnají, tak je rozmístění platné.

Podobně pak hledám možné platné rozmístění, kdy informace z jednoho průchodu použiju pro dva body. Co se týče náročnosti, tak u A* může být až exponenciální. Různé optimalizace hledání cest v libovolném grafu mi přišly opravdu dost složité, proto jsem konstatoval, že jde "pouze o pavouky v tělocvičně" a ponechal A*.

Tak si říkám, zda jsem nepochopil zadání špatně, ale nemohu na nic přijít.

Jak jste řešili úlohu vy?

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: ranní tělocvik - řešení

Příspěvek od blazeva1 »

Řešení vypadá na první pohled dobře, ovšem je zde nejeden zakopaný pes.
Začne to hezky, protože sekce 'Detekce existence platného rozmístění' A, B, C a 'Hledání platného rozmístění' jsou dobře.
Pak se ale ponoříme do sekce 'Možné optimalizace' a zde začne peklo. Padnou dvě nezdůvodněná tvrzení a na jejich základě děláme prořezávání. Pokud si tato pravidla pročteme bez dalšího přemýšlení, tak zjistíme, že druhé pravidlo zamezí nalezení řešení na S3 -- jeden vrchol spojený s třemi dalšími. Na S3 průchod ze středu nic nenajde, a průchod z listu prořeže zbylé listy, protože je 'nemá smysl uvažvoat, protože k nim vede pouze tato jediná cesta'.
Tato drobnost měla nějaký bodový postih, avšak nyní přijde to gró -- analýza.
Hledání nejkratší cesty na grafu je O(n+m) kde n je počet vrcholů a m je počet hran, tento algoritmus je tzv. BFS a v implementaci pod názvem 'findPath'. A* je heuristické prohledávání prostoru, avšak v našem prostoru nelze heuristiku (např. na letovou vzdálenost vrcholů) uplatnit. Algoritmus tedy pustí z každého vrcholu bfs a potom pro každou dvojici zkusí jestli je vzdálenost stejná jako od startu, vychází O(n*(n+m+(n^2(n+m)))) = O(n^3 * (n+m)). Místo toho jsme se něco dozvěděli o průměrném stupni a exponenciální složitosti.
Páč to byla čistě teoretická úloha, tak kód z pohledu hodnocení přeskočme.

Co bylo v řešení správně? Máme řešení, které funguje, když si z něj něco odmyslíme.

Jak se to dalo řešit? Vrchol stupně 3 existenci řešení zaručuje. Pokud tam není, tak jde o disjoint union cest a cyklů. Cesty řešení nemohou obsahovat, takže koukneme na cykly, a zde existuje řešení právě na těch, které mají počet vrcholů dělitelný beze zbytku třemi. Složitost O(n+m).

Sice jsem to nehodnotil, ale s hodnocením souhlasím.

S přáním mnoha bodů ve 3. kole,
Vašek

dzejkob
Příspěvky: 5
Registrován: 03-03-2018 18:59
Škola: Soukromá střední škola výpočetní techniky, Litvínovská 600 Praha 9
Rok ukončení studia: 2018

Re: ranní tělocvik - řešení

Příspěvek od dzejkob »

Děkuji za reakci. To testování cest všech uzlů ve vlně mi taktéž přišlo šílené, ale nenapadlo mě nic lepšího, tak jsem zkoušel nějaké optimalizace, které jsem ale nestihl implementovat - kdyby ano, tak bych to zrevidoval.

Co se kódu týče, tak mě by to opravdu nebavilo, kdybych si to nemohl spustit, takže tam je java kód. Je tedy uveden místo "pseudokódu" a slouží k demonstraci principu. Když si spustím scénář se 4 uzly (viz. rozmístění obrázek uzly 0, 1, 2, 3) tak to rozmístění najde. Když tam zadám celý ten obrázek, tak najde mnoho dalších (všechny). Žádné optimalizace tam nejsou.

Mě jenom mrzí, že mám tak žalostně málo bodů, když to jednak detekuje platné rozmístění - a i to rozmístění hledá.

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: ranní tělocvik - řešení

Příspěvek od blazeva1 »

Hledání rozmístění je více-méně ok. Žalostně málo bodů máš za to, že je řešení neoptimální. Teoretická úloha zaměřena na to se hluboce zamyslet a rozhodnout problém co nejlépe, tohle řešení k tomu přistupuje spíše implementací jasného a jednoduchého algoritmu.

Je jasné, že si někteří užijí kódování víc, jiní méně -- snažíme se tu nastolit balanc obou přístupů a i proto jsou některé úlohy čistě programovací či mixované.

Vašek

dzejkob
Příspěvky: 5
Registrován: 03-03-2018 18:59
Škola: Soukromá střední škola výpočetní techniky, Litvínovská 600 Praha 9
Rok ukončení studia: 2018

Re: ranní tělocvik - řešení

Příspěvek od dzejkob »

Tak už vidím výsledky - u čtvrté úlohy mám ale prázdné políčko - podobně v profilu je "nebylo ohodnoceno", přestože odevzdáno mám (lze stáhnout). Je to chyba, nebo to ještě není dokončeno?

blazeva1
Organizátor
Příspěvky: 38
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: ranní tělocvik - řešení

Příspěvek od blazeva1 »

U druhého kola chybí u čtvrté úlohy opravit pár řešení. Většina z vás zde použila inovativní řešení, a tak jsou opravy komplikovanější, než se předpokládalo. Bude ohodnoceno do neděle 11.3.

Zamčeno