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



Bude to o prsa. Facebook a Instagram pořád neví, kdy jsou zobrazené bradavky porno

Bude to o prsa. Facebook a Instagram pořád neví, kdy jsou zobrazené bradavky porno

**Meta má zjednodušit pravidla a být ke všem spravedlivá **Facebook s Instagram věnují samostatný odstavec bradavkám **Pravidla ale neřeší nebinární, transsexuální a intersexuální osoby

Petr Urban
InstagramFacebookSociální sítě
Za WhatsApp se bude platit! Za předplatné dostanete funkci, která je u konkurence zadarmo

Za WhatsApp se bude platit! Za předplatné dostanete funkci, která je u konkurence zadarmo

** Bylo to jen otázkou času ** Už i WhatsApp nabízí prémiové předplatné ** Za poplatek dostanete funkci, která je u konkurence zadarmo

Martin Chroust
předplatnéWhatsAppMobilní aplikace
Telefon jako kapesní skener v klubech. Vědci přišli se snadnou metodou pro detekci drog v nápojích

Telefon jako kapesní skener v klubech. Vědci přišli se snadnou metodou pro detekci drog v nápojích

** Drogy nasypané do nápojů jsou stále velkým problémem ** Jejich odhalení a dokázání je časově i technicky velmi náročné ** K detekci GHB v nápoji nově poslouží jakýkoliv smartphone

Martin Chroust
StudieDrogySmartphony
Návod, jak dostat maximum z Peněženky Google

Návod, jak dostat maximum z Peněženky Google

Služba Google Wallet (Peněženka Google) schlamstla před několika měsíci platební aplikaci Google Pay. Díky tomu se původní platforma rozrostla o další funkce. Je zde však i prostor pro zlepšení.

Jan Spěšný
Šedý trh s předplatným se vymyká kontrole. Spotify, Netflix nebo Disney+ můžete mít doslova za pár korun

Šedý trh s předplatným se vymyká kontrole. Spotify, Netflix nebo Disney+ můžete mít doslova za pár korun

** Sdílení účtů mezi kamarády je jen začátek ** Dnes letí nákupy předplatných v Indii nebo na Aliexpressu ** Superlevné „netflixy“ ale mohou nakonec spíš škodit

Lukáš Václavík
PředplatnéNetflixSpotify
Jak rozmazat dům, aby vás sousedi nemohli šmírovat. Jde to v Mapách Google i na Mapy.cz

Jak rozmazat dům, aby vás sousedi nemohli šmírovat. Jde to v Mapách Google i na Mapy.cz

** Nelibí se vám, když cizí lidé okukují váš dům? ** Všechny mapové aplikace nabízejí možnost rozmazání snímku ** Máme návod pro Apple Maps, Bing Maps, Mapy Google a Mapy.cz

Karel Kilián
SoukromíNávodyMapy
Všichni žijeme v Bublině. Je velká 1000 světelných let a magnetizovaná

Všichni žijeme v Bublině. Je velká 1000 světelných let a magnetizovaná

** O bublinách v galaxiích toho víme jen velmi málo ** Theo O’Neill a jeho kolegové se to snaží zlepšit ** Zmapovali magnetická pole naší Lokální Bubliny

Stanislav Mihulka
Astronomie