NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
shaman
Člen
Avatar
shaman:22.2.2017 14:58

Ista ceska firma vyhlasila sutaz o cestu okolo sveta. Staci len napisat jednoduchy algoritmus ktory vypocita najlacnejsiu multicity trasu.

Viac info na stranke sutaze: https://travellingsalesman.cz/

Odpovědět
22.2.2017 14:58
try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }
Avatar
shaman
Člen
Avatar
shaman:22.2.2017 15:00

Nadpis sa uz neda editovat, pravopisnych trolov vopred pozdravujem. :)

Nahoru Odpovědět
22.2.2017 15:00
try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }
Avatar
Matúš Petrofčík
Tvůrce
Avatar
Odpovídá na shaman
Matúš Petrofčík:22.2.2017 15:06

Oni už majú takú súťaž už minimálne pol roka. Aj na PyCon 2016 v Brne som videl tie ich letáky.

Ale tak nie zle :)

Nahoru Odpovědět
22.2.2017 15:06
obsah kocky = r^2 ... a preto vlak drnká
Avatar
shaman
Člen
Avatar
Odpovídá na Matúš Petrofčík
shaman:23.2.2017 14:54

To som nevedel. Viem ze pracuju s pythonom lebo zhanaju furt python developerov ale sutaz celkom zaujimava.

Nahoru Odpovědět
23.2.2017 14:54
try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }
Avatar
Matúš Petrofčík
Tvůrce
Avatar
Odpovídá na shaman
Matúš Petrofčík:23.2.2017 15:58

Myslím že to bola súťaž, už si nepamätám presne, a ani neviem či im tam vôbec niekto prispel. Také papiere boli kde bolo veľmi podobné zadanie, a na druhej strane prázdne miesto kde sa to dalo riešiť, prípadne mail a ich web tam bol tuším. :)

Nahoru Odpovědět
23.2.2017 15:58
obsah kocky = r^2 ... a preto vlak drnká
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na shaman
Martin Dráb:23.2.2017 21:59

Staci len napisat jednoduchy algoritmus ktory vypocita najlacnejsiu multicity trasu.

Jestli to dobře chápu, tak se jedná o problém obchodního cestujícího, i když asi zjednodušený tím, že platí trojúhelníková nerovnost. Pokud se ale chceme dostat k optimu, tak to je prostě NP-hard, takže se moc nedá čekat, že by "jednoduchý algoritmus" pomohl. Heuristiky existují (a pokud vím, dost dobré), ale o nich oni určitě vědí.

Nahoru Odpovědět
23.2.2017 21:59
2 + 2 = 5 for extremely large values of 2
Avatar
coells
Tvůrce
Avatar
Odpovídá na Martin Dráb
coells:24.2.2017 17:10

Ano, zmínka o jednoduchém algoritmu mě také pobavila :-)

Máš pravdu, že je to hledání Hamiltonovské kružnice, ale zadání je složitější než původní TS.
Kvůli časové souslednosti máš K množin o N vrcholech, které vzájemně tvoří bipartitní dvojice.
Takže místo o(N2) hran jich máš O(K*N2) s omezujícími podmínkami a neplatí trojúhelníková nerovnost.

Pro zajímavost, u NP úloh v soutěžích, co jsem viděl, vždy vyhrály s obrovským náskokem genetické algoritmy.

 
Nahoru Odpovědět
24.2.2017 17:10
Avatar
shaman
Člen
Avatar
Odpovídá na coells
shaman:28.2.2017 9:49

Rad som pobavil. :) Co su geneticke algoritmy? Mas nejaky link?

Nahoru Odpovědět
28.2.2017 9:49
try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }
Avatar
Petr Nymsa
Tvůrce
Avatar
Odpovídá na coells
Petr Nymsa:28.2.2017 13:33

Jak se vůbec dají hodnotit algoritmy na NP-hard úlohách? Pdole jakých kriterií? Čistě rychlost nebo něco i jiného?

Nahoru Odpovědět
28.2.2017 13:33
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
coells
Tvůrce
Avatar
Odpovídá na Petr Nymsa
coells:28.2.2017 14:05

V podstatě je můžeš hodnotit, jak chceš.
Soutěžní úlohy bývají doplněné o ohodnocovací funkci, kterou musíš optimalizovat.
Například Hamiltonovská cesta je rozhodovací úloha v NP-hard, ale délka nejdelší nalezené cesty na ohodnoceném grafu je typická optimalizační úloha a není o nic jednodušší.
Čas nemá smysl řešit, obvykle se uměle omezí čas i pamět na nějaký limit.

shaman stačí googlit, najdeš toho tuny

 
Nahoru Odpovědět
28.2.2017 14:05
Avatar
dez1nd
Člen
Avatar
Odpovídá na shaman
dez1nd:19.9.2017 6:37

a já chtěl napsat "Algoritmus" :D

 
Nahoru Odpovědět
19.9.2017 6:37
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 11 zpráv z 11.