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


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

Windows Sandbox: Testovací Desítky nabízejí pískoviště pro vaše lumpárny

Windows Sandbox: Testovací Desítky nabízejí pískoviště pro vaše lumpárny

** Před deseti lety měly Windows 7 tzv. XP Mode ** Microsoft se k nápadu opět vrací ** V Desítkách budou schované další Desítky

Jakub Čížek | 18

Prohnali jsme prohlížeče benchmarky. Nový Edge je opravdu Chrome a je rychlý!

Prohnali jsme prohlížeče benchmarky. Nový Edge je opravdu Chrome a je rychlý!

** Prohnali jsme nový Edge webovými benchmarky ** Potvrzují, že je to Chrome ** V animacích a vektorech je možná nejlepší

Jakub Čížek | 44

Co pořídit k počítači: tipy na osvědčené klávesnice, sluchátka a další příslušenství

Co pořídit k počítači: tipy na osvědčené klávesnice, sluchátka a další příslušenství

** Toto jsou tipy Živě.cz na příslušenství k počítači, se kterým neuděláte chybu ** Klávesnice, myši, tiskárny, sluchátka... ** Vybíráme jak příslušenství na běžnou práci, tak na hraní her

David Polesný | 26

Portál občana už funguje. Na státní web vypadá až překvapivě použitelně

Portál občana už funguje. Na státní web vypadá až překvapivě použitelně

** Portál občana už funguje, vyřídíte na něm první požadavky ** Funkce se budou postupně rozšiřovat ** Web je docela moderní a přehledný

David Polesný | 66