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, Vývojář, Nejlepší výsledek, Wiki, Programátorská soutěž, Optimální výsledek, Možná varianta, Dostupný výkon, Algoritmus, Obchodní cestující, Vyřešení, Rozumný čas, Vítězný tým, Vyřešení problému, Oblast


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

Dell XPS 13: Když vás ostatní doženou až za tři roky

Dell XPS 13: Když vás ostatní doženou až za tři roky

** XPS 13 nastartoval trend notebooků bez rámečků ** Letošní model kompletně přechází na USB-C ** Navzdory malému tělu se řadí výkon ke špičce

Tomáš Holčík | 34

Loopwheels znovu vymyslelo kolo. Místo drátů má v ráfcích kompozitové pružiny, které vylepší komfort jízdy

Loopwheels znovu vymyslelo kolo. Místo drátů má v ráfcích kompozitové pružiny, které vylepší komfort jízdy

** Proč vymýšlet kolo? Protože ho lze vymyslet lépe! ** Kola Loopwheels nabízejí integrované odpružení ** Cílem je poskytnout pohodlnější a klidnější jízdu

Karel Kilián | 14

Jak funguje největší akumulátor v Česku: podívejte se do elektrárny Dlouhé Stráně

Jak funguje největší akumulátor v Česku: podívejte se do elektrárny Dlouhé Stráně

** Přečerpávací vodní elektrárna Dlouhé stráně je obdivuhodné technické dílo ** Stejná turbína vyrábí elektřinu i tlačí vodu zpět do horního jezera ** Strojovna elektrárny je zabudována v podzemí

David Polesný | 35

Lenovo přivezlo na IFA 2018 skutečné inovace. Tyto tři notebooky stojí za to

Lenovo přivezlo na IFA 2018 skutečné inovace. Tyto tři notebooky stojí za to

** Yoga C930 nabídne revoluční reproduktor v kloubu displeje ** Yoga Book C930 představuje zdařilý reparát podivného Yoga Booku ** ThinkPad X1 Extreme se může pochlubit extrémní výbavou v tenkém těle

Tomáš Holčík | 16

PortraitPro: Vyzkoušeli jsme program, který prý udělá z každé „žáby“ krasavici

PortraitPro: Vyzkoušeli jsme program, který prý udělá z každé „žáby“ krasavici

** V digitálním světě nemůžete věřit všemu ** Nová generace 3D fotoeditorů zvládne divy ** Vyzkoušeli jsme PortraitPro, který vám změní i kontaktní čočky

Jakub Čížek | 10


Aktuální číslo časopisu Computer

Jak vytvořit a spravovat vlastní web

Velký test herních klávesnic a DVB-T2 tunerů

Vše o formátu RAW

Vybíráme nejlepší základní desku