Programování

Cesta kolem světa (a do Brna) od Kiwi.com za nejlepší vyřešení problému obchodního cestujícího

Cesta kolem světa (a do Brna) od Kiwi.com za nejlepší vyřešení problému obchodního cestujícího

Kiwi.com hledá vývojáře. Firma proto dnes vyhlásila programátorskou soutěž, ve které vítězný tým vyhraje cestu kolem světa... a určitě neméně atraktivní možnost podívat se do Brna.

Veškeré podrobnosti jsou na webu travellingsalesman.kiwi.com. Stejně jako loni v únoru jde o to, kdo nejlépe vyřeší obtížný optimalizační Problém obchodního cestujícího (Wiki).

Podmínky a pravidla

Úkolem je najít nejlevnější možné spojení mezi více zadanými oblastmi. Soutěžící dostanou od Kiwi.com data o letech a budou hledat nejlepší algoritmus, který vyhoví pravidlům:

  • Začít cestu v zadané oblasti
  • V každé oblasti navštívit přesně jedno město podle vlastního výběru
  • Mezi oblastmi se přesouvat každý den
  • Cesta musí pokračovat ze stejného města, kam cestující přiletěl
  • Celý výlet skončí ve městě, kde začal

Zní to velice jednoduše, stačí přece vyzkoušet a porovnat všechny možné varianty. Je jich ale tolik, že výpočet velmi brzy dokáže vyčerpat veškerý dostupný výkon, takže se k nejlepšímu výsledku nedá v rozumném čase dostat. Jde o tzv. NP-těžkou úlohu (Wiki), nedeterministicky polynomiální problém.

Problém obchodního cestujícího řeší různé algoritmy, které relativně brzy dojdou k více-méně dobrému, ale zřejmě nikdy k optimálnímu výsledku.

Dnes začala registrace do soutěže, výsledky je třeba poslat do 29. října. V listopadu Kiwi vyhlásí výsledky. Vývojáři mohou k řešení použít libovolný programovací jazyk z tohoto seznamu.

Diskuze (24) Další článek: Steve Wozniak má problém. Studenti jeho drahého inženýrského programu Woz U si stěžují na nízkou kvalitu

Témata článku: Technologie, Programování, Brno, Kód, Algoritmus, Vyřešení, Možná varianta, Nejlepší výsledek, Optimální výsledek, Programátorská soutěž, Wiki, Vyřešení problému, Dostupný výkon, Vítězný tým, Kolem světa, Vývojář, Rozumný čas, Obchodní cestující, Oblast


Určitě si přečtěte

Šmírování kamerami Googlu: Koukněte, co šíleného se objevilo na Street View

Šmírování kamerami Googlu: Koukněte, co šíleného se objevilo na Street View

Google stále fotí celý svět do své služby Street View. A novodobou zábavou je hledat v mapách Googlu vtipné záběry. Podívejte se na výběr nejlepších!

redakce | 6

3D tisk pro naprosté zelenáče: Co vyrobíte na laciném stroji za pár tisíc korun

3D tisk pro naprosté zelenáče: Co vyrobíte na laciném stroji za pár tisíc korun

** Domácí 3D tisk je dnes už finančně dostupný prakticky všem ** Lacinou tiskárnu pořídíte za pár tisíc korun ** Jak vlastně tisk probíhá a jak navrhnout, co vytisknout

Jakub Čížek | 66

10 novinek Androidu 10, které vás budou bavit

10 novinek Androidu 10, které vás budou bavit

Jan Láska, Vladislav Kluska | 27

13 praktických tipů a triků pro Mapy.cz, které možná neznáte

13 praktických tipů a triků pro Mapy.cz, které možná neznáte

** Mapy.cz neslouží jen k zobrazení podkladů a plánování tras ** Nabízejí celou řadu dalších praktických funkcí a možností ** Vybrali jsme třináct tipů a triků, o kterých možná (ne)víte

Karel Kilián | 31

20 tipů a triků pro Gmail: Užitečné maličkosti, které zefektivní práci s e-maily

20 tipů a triků pro Gmail: Užitečné maličkosti, které zefektivní práci s e-maily

** V Gmailu je řada užitečných funkcí, které možná všechny neznáte ** Odeslání mailu můžete například pozdržet či naplánovat na později ** Nad Gmailem můžete mít s několika triky daleko lepší kontrolu

Karel Kilián | 25

Antivir zdarma: 8 bezplatných řešení, která zatočí s havětí v počítači

Antivir zdarma: 8 bezplatných řešení, která zatočí s havětí v počítači

** Součástí Windows 10 je integrovaný antivirový program. Stačí to? ** Představíme vám sedm aplikací na boj proti virům a malwaru ** Všechny jsou k dispozici zdarma a některé ani nemusíte instalovat

Karel Kilián | 30