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


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

Velká podzimní aktualizace: Co nového teď najdete ve Windows 10

Velká podzimní aktualizace: Co nového teď najdete ve Windows 10

** Microsoft se opět snaží spojit telefony a počítače. ** Místo velkých novinek se zaměřil spíše na drobná vylepšení. ** Vyhledávání je konečně použitelné a hledá téměř všude.

Vladislav Kluska | 78

Američtí mariňáci si tisknou kasárna z betonu na 3D tiskárně

Američtí mariňáci si tisknou kasárna z betonu na 3D tiskárně

** Americká námořní pěchota nedávno představila 3D tištěná kasárna pro vojáky ** Ty jim tiskne velká 3D tiskárna na beton ** Výsledkem je solidní obytný prostor, který je slušně chráněný před nepřátelskou palbou

Stanislav Mihulka | 18

Jak horko bude ve vašem městě, až vám bude 80 let? Podívejte se, jak se projeví klimatické změny!

Jak horko bude ve vašem městě, až vám bude 80 let? Podívejte se, jak se projeví klimatické změny!

** Srpen byl třetí nejteplejší za posledních více než sto let ** Bude to ale daleko horší, jak ukazuje aplikace NYT ** V Praze vzroste počet horkých dní na čtyřnásobek

Karel Kilián | 21


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