ranní tělocvik - řešení
Napsal: 04-03-2018 12:27
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?
"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?