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


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

Internet poslední naděje. Kdo má nejlepší tarif „LTE na doma“?

Internet poslední naděje. Kdo má nejlepší tarif „LTE na doma“?

** Srovnali jsme fixní LTE připojení od tuzemských operátorů ** Liší se rychlostmi, cenou i podmínkami ** Na co všechno dát pozor?

Lukáš Václavík | 42

Lukáš Václavík
LTEPoskytovatelé internetuPřipojení k internetu
Teď už Chromium ovládne Windows 10 úplně. Microsoft dokončil WebView2

Teď už Chromium ovládne Windows 10 úplně. Microsoft dokončil WebView2

** Před dvěma lety se Microsoft zasnoubil s Chromem ** Nový Edge není zdaleka jejich jediné dítě ** Ještě důležitější je komponenta WebView2

Jakub Čížek | 50

Jakub Čížek
Windows 10ChromeSoftware
AMD uvádí grafické karty Radeon RX 6800, 6800 XT a 6900 XT. Útočí přímo na modely od Nvidie

AMD uvádí grafické karty Radeon RX 6800, 6800 XT a 6900 XT. Útočí přímo na modely od Nvidie

** AMD představilo tři nové grafické karty ** Všechny s architekturou RDNA2, kterou používají i PS5 a Xbox Series ** Karty útočí přímo na GeForce RTX 3000

Karel Javůrek | 77

Karel Javůrek
Radeon RX 6000Grafické kartyAMD
10 míst na mapách Googlu, která nesmíte vidět. Nahradily je čtverečky

10 míst na mapách Googlu, která nesmíte vidět. Nahradily je čtverečky

** Deset míst, které nesmíte vidět ve webových mapách ** Jsou to letiště, základny i elektrárny ** Nejvíce míst tají Francie

Jakub Čížek | 21

Jakub Čížek
Mapy GoogleMapy
Podívejte se, co dokáže vyrobit jedna z nejexotičtějších 3D tiskáren v Česku

Podívejte se, co dokáže vyrobit jedna z nejexotičtějších 3D tiskáren v Česku

** Na jaře tiskla unikátní české respirátory ** Používá ji třeba Škoda Auto, a.s. ** Zajeli jsme se podívat do pražského showroomu 3Dees

Jakub Čížek | 12

Jakub Čížek
3D tiskČeskoTechnologie
Nové mapy Google: Česko vypadá, jako by bylo kdesi na ruské Sibiři
Jakub Čížek
Mapy GoogleMapy
Jak v prohlížeči vypnout oznámení zasílaná webovými stránkami

Jak v prohlížeči vypnout oznámení zasílaná webovými stránkami

** Obtěžují vás neustálé dotazy webů, zda chcete zobrazovat oznámení? ** Můžete je zakázat, a to jak kompletně, tak i pro jednotlivé stránky ** Připravili jsme návody pro Chrome, Firefox, Edge a Operu

Karel Kilián | 11

Karel Kilián
Jak na InternetTipyProhlížeče
Google chystá funkci, která z chytrého Gmailu udělá hloupý Gmail
Lukáš Václavík
SoukromíGmailGoogle
Obří GeForce RTX 3090 vyfocená ve skříni. Moc místa vám nezbyde
Karel Javůrek
GeForce RTX 3000Grafické kartyNvidia