Vyřešte problém obchodního cestujícího a Kiwi vám zaplatí cestu kolem světa

No prave, jde o to, ze matematici a jini jinak vzdelani lide mnohdy uz nevidi pres dogmata slozitych vypoctu, co se na skole ucili roky, nekdy nejakou mnohdy i selskou logiku, na kterou prijde i baba blazkova (ta samozrejmne neni schopna programovat a tak se to nakonec svet asi nedozvi)....

A to už se někdy stalo, že na nějaký ožehavý matematický problém přišel "nematematik" selským rozumem? Zřejmě chápu, co jste tím chtěl říct, ale matematici jsou matematici z nějakého důvodu a já např. nikdy neslyšel o tom, že by na něco přišel někdo úplně mimo obor. Nabídka firmy je zajímavá a asi něco málo rozpoutá, ale přikláním se k názoru, že to je povedaná reklama, bez jakéhokoliv očekávání nějakého výsledku.

Ta firma chce zlepšit svůj alogirtmus, který už teď nějak má. A věřím, že někdo kdo si na něco podobného dělá PhD s tím může pomoc - pomůže firmě a sám za to něco dostane.takže za mě win-win. Opakuji, nikdo nečeká, že to vyřeší NP problém jako celek.

presne, chcu len zdokonalit svoj algoritmus....
získaju takmer zadarmo zlepsenie a reklamu

Titulek je správně, i když nepřesně. Mělo být nejlépe nejlépe vyřeště... On totiž titulek neříká, že to musí být řešeno v polynomiálním čase. Stačí v konečném čase.

Problém obchodního cestujícího není žádným svatým grálem matematiky v tom smyslu, že by nebyl znám obecný algoritmus k jeho exaktnímu vyřešení, ten je naopak docela prostý. Jediný problém spočívá v tom, že složitost toho algoritmu je exponenciální a tedy velice rychle vede k neúnosně velké potřebě výpočetního výkonu. To, co musí řešit každý vyhledávač spojení, ať už jde o letenky nebo třeba o vlaky, není exaktní řešení za libovolně dlouhý čas, ale v určitém omezeném čase s omezenými prostředky najít co možná nejlepší řešení (nejblíže tomu exaktnímu, ideálnímu). No a tahle "soutěž" je určitě prostor pro prezentaci neotřelých nápadů a příležitost pro firmu vyzobnout si vhodného adepta do svého týmu. Tak trochu kombinace reklamy (na kiwi.com) a výběrového řízení (na pozici programátora). Sympatický pokus.

ne.

otázne je, či chcú nájsť najlepší variant bez obmedzenia času- to sa dá jedine bruteforce -to ale nechú
alebo do nejakého času čo najlepší-čiže dajme tomu do minúty

Ale tak pořád ty kompy počítaj docela rychle, dá se jich využít víc a i když to s n roste exponenciálně, tak pro drtivou většinu dotazů najdou optimální řešení do sekundy. A ten zbytek se už nějak vyheuristikuje...

Vy máte hlavně problém s tím jak všechno přesně hádáte na čem to poběží a co budete muset patlat. A hlavně je pravda že se vám nechce programovat milionkrát naprogramované,abyste skončil na místě miliontémprvním to by byla skutečně vážná stráta vašeho vzácného strojového času.

Máte pravdu souhlasím s vámi. Můj osobní problém je s tím, že si například budu chtít data seřadit podle ceny. A místo toho abych využil už někým naprogramovaný třídící algoritmus, tak si ho budu muset napsat sám, protože nebude dostupná knihovna kde je už vytvořený.
Jako, budu rád pokud se mýlím, ale dost mě naštve když budu mít pravdu.

https://github.com/yusufshakeel/C-Project/tr... ...
MIT licence.
Proste rekni, ze se ti do toho nechce a nevymejslej vymluvy.

>> místo toho abych využil už někým naprogramovaný třídící algoritmus
takze chcete len polepit cudzi kod do vasej implementacie ?

Nikdo vás nenutí to programovat v Cčku... Na linuxu běží implementace snad všech známých programovacích jazyků.

Vyhledávač letenek snad nehledá cestu mezi všemi letišti... Tohle optimální řešení nemá, maximálně nějaké heuristiky, aby se nemusely zkoušet všechny možnosti, to bychom se výsledku nedožili.

Ale hleda a kombinuje cestu s ruznymi letisti... diky tomu, jak se tvori ceny letenek, tak je to ukazkovauloha pro vyhledavac...

kliknu na stránku kiwi.com / about a hned druhý titulek je, že mají business postavený na tom, že kombinují letenky od společností, které spolu normálně nekooperují. Takže kluci z brna na tom postavili business a za stamiliony (či kolik mají investic) to točej, ale tobě zatím ani nedošlo, že je to oportunita na trhu. "vtipné"...

To se pletete. Problém obchodního cestujícího je úplně něco jiného než vyhledávač letenek. Vyhledávač letenek je problém nalezení cesty v síti z bodu A do bodu B. Ten má jednoduché a rychle řešení.Obchodní cestující je úplně jiný problém. Ten musí navštívit všechna zadaná místa. Při hledání letenek nechcete navštívit všechna letiště světa.

Toto je presne problém obchodného cestujúceho.
Príklad - svadobná cesta.
Chceš si pozrieť Maledivy, Maurícius, Srí Lanku, Dubaj, Bali, Hawaii, New York a Dominikánsku republiku. Hľadáš najlacnejšie a/alebo najrýchlejšie spojenie týchto miest.
Alebo aj inak. Hľadáš proste len spojenie medzi letiskami VIE a MLE. To spojenie proste nie je priame. Hľadáš preto najrýchlejšie a zároveň najlacnejšie spojenie. K tomu sa pridá dajmetomu kritérium, že to musí byť cez DXB alebo cez DOH. A sme presne pri probléme obchodného cestujúceho. Nezáleží ti, či poletíš s jednou spoločnosťou, druhou, alebo mixom.

Ta svatebni cesta opravdu je problem obchodniho cestujiciho. A i kdyz neznam vyjledavace letenek, pochybuju, ze to bezne umi.
Ale to druhe uz je nesrovnatelne jednodussi. To je na obycejny dijkstruv algoritmus pro hledani nejkratsi cesty. Pokud trvate na tranzitu na konkretnim letisti, je to rozlozeni na dva. Kdybyste tam dal dva mozne prestupni body, budiz, vypocitaji se dva vysledky a vybere se lepsi. Porad je to uloha s podstatne nizsi slozitosti.

Pak zalezi na implementaci. A to je sakra znat.

tak sa prihlas, vyhras 600 euro

Nemate pravdu.

A jak to vaše řešení dopadlo ? Umístil jste se na bedně ?

A umite to dokazat?

to ze je problem NP uplny neznamena, ze neexistuje jiny algoritmus, nez brute force. algoritmy existuji, jen nejsou dost rychle.

Jakožto člověk, který před lety psal (a programoval) diplomku na téma Pravděpodobnostní metody řešení NP-úplných problémů (genetické algoritmy), mohu konstatovat, že nemáte tak docela pravdu.Existují jiné algoritmy než brutal force, ale pokud chcete najít tu nejlepší variantu, neexistuje jiná cesta. Ostatní algoritmy hledají pouze dostatečné dobré cesty. Ano, může se stát, že mezi těmi dostatečně dobrými bude náhodou i ta nejlepší, ale vy nebudete vědět, že to je ta nejlepší.

Myslím, že zde jde o efektivitu řešení. Možná jste si všimli, že kiwi hledá neustále programátory v Ruby/Pythonu, možná Perl. Namotivují studenty, to znamená mladé mozky. Zjistí, kdo umí myslet efektivně. Není důležité najít nejlepší cestu, je důležité najít co nejlepší cestu v co nejkratším čase. Možná někdo přijde s něčím novým. Vítězům nebo možná i všem medajlistům se otevře pracovní příležitost. Protože se bude jednat o ověřené mozky. Žádný pohovor to nenahradí. Tohle je efektivita v praxi.
Je to nádherná soutěž a škoda, že nejsem student s pár lidmi okolo.

No a to je definice NP úplného problému. Pro určitou složitost zadání neexistuje dostatečně efektivní postup. Že se dočkám řešení za 100 let, není uspokojivé.
Správně jste měl asi napsat, že možná algoritmy existují, ale nejsou známé.

> to budou porovnávat prosím co?
Tipuju že to, jak dobré to dává výsledky. Stačí se kouknout na návrh cesty od dvou algoritmů a můžete hodnotit cenu, čas, počet přestupů nebo něco mezi...

Neznám podmínky, ale měla by existovat nějaká ohodnocovací funkce, která o cestě řekne, jak moc je dobrá.

Tak jim nekdo doda nejaky evolucni algoritmus a oni misto, aby za to zaplatili je poslou na vylet.

Vsak jim to doda nekdo, kdo chce na vylet a ne kdo chce zaplatit...

Četl jsi vůbec to zadání nebo hodnotíš jenom podle titulku?Nikdo netvrdí a ani nečeká, že jej bez kvantového počítače vyřeší. Velice jednoduše bude existovat jeden set zadání (body na cestě a ceny) a algoritmus má složit do 30s co nejoptimálnější řešení (předpokládám, že při shodě budou řešit rychlost).
Ten, který to stihne nejlépe vyhrál. A pokud se nikdo nepřihlásí tak to může být klidně ten co je seřadí a proletí podle abecedy.Tak až budeš příště zase spravedlivě rozhořčenej, tak si zjisti proč.

Doufam ze jste nevystudoval zadnou vysokou skolu. Byla by to pro ni ostuda.

On to není úplně typický problém obchodního cestujícího. Oni totiž nechtějí porovnávat vzdálenosti, ale ceny, které se navíc ještě během dnů mění. Takže cena A->B je jiná první a druhý den. Takže se to ještě víc komplikuje.

To není tak úplně pravda. Algoritmu je jedno, jestli hodnotou cesty z A do B je "ujeto 1000 km" nebo "zaplaceno 1000 Kč". Jednou je jednotkou km, jednou Kč, ale čísla jsou jasná.

Není to jedno. Problém je, že město A je dnes i zítra stejně vzdálené od města B. Ale cena letenky z města A do města B je dnes jiná než bude zítra. A předpokládám, že v případě letenek to bude hrát zásadní rozdíl, neboť neobletíte všechny destinace během jednoho dne.

Tak buď koupíš vše najednou a pak neřešíš zítřejší cenu, nebo to kupuješ po částech a pak neřešíš tak složitou úlohu.Takže je to jedno.

Jak to, ze neresim? Naopak. Vysledek muze byt klidne: "kdyz dneska poletite do A a pak zitra koupim do B pak do C atd., tak vas to bude stat vic nez kdyz dneska do B a zitra koupim do C a pak koupim do A". A jestli se rozhodnu, ze poletim do A a az pak budu resit co dal, tak uz druhou moznost nemam sanci pouzit. A takove rozhodnuti muze byt treba to 25. mesta. Dokonce by to mohlo byt i tak, ze to poradi: "mezi mesty G a H poletite az 16. den, ale nejlepsi bude koupit letenku online uz 5. den". A razem je to o rady jinak slozita uloha.

Jenže to jaksi předpokládá, že víš kolik ta letenka bude stát za pět dní a to nevíš, jinak by nedávalo smysl tu cenu snižovat. A pokud by se zvyšovala, tak je nejlepší koupit rovnou.Ale budiž, donutil jsi mě chvíli přemýšlet a pokud to uděláš taky tak zjistíš, že když budeme znát dopředu ceny letenek na všech trasách na každý den, tak to můžeme zapracovat do algoritmu a složitost hledání optimální trasy se tím nezvýší, zajímavé, že?Takže je to ještě víc jedno než předtím