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


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

Řidiče Tesly ukolébal autopilot, policisté ho zastavili až po 11 kilometrech

Řidiče Tesly ukolébal autopilot, policisté ho zastavili až po 11 kilometrech

** Policisty poblíž San Franciska zaujala Tesla se spícím řidičem ** Donutili vozidlo zpomalit a následně probudili překvapeného řidiče ** Vozidlo podle dostupných informací jelo v režimu autopilota

Karel Kilián | 70

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