Klávesové zkratky na tomto webu - základní
Přeskočit hlavičku portálu

Diskuse k článku

Získejte 1 000 000 dolarů
za vyřešení hádanky

Zní to neuvěřitelně, ale za nalezení nejkratší možné cesty obchodního zástupce mezi několika městy můžete získat milion dolarů. Odměnu vypsal Clayův matematický institut (CMI) v Cambridgi v Massachusetts. Máte šanci milion získat právě vy?

Upozornění

Litujeme, ale tato diskuse byla uzavřena a již do ní nelze vkládat nové příspěvky.
Děkujeme za pochopení.

Zobrazit příspěvky: Všechny podle vláken Všechny podle času

jaja

jak na to!

tak boris nadhoď:-)

0/0
7.8.2007 11:14

tlachal

Vždyť je to klasický NP-complete problem

dá se to převéz např. na kachlíčkovací algoritmus atd. Ale hlavně komplikovanosti tohoto problému stojí kryptovací algoritmy - například používané pro koncept privátního-veřejného klíče. Pokud by existovalo logické řešení (silové - tj. dostatečně výkoný stroj je samozřejmě možné) tak by se musely hledat úplně jiné technologie kryptování ....

0/0
4.2.2007 22:57

morbidni_kreten

:-P

Jo, už to mám, nejlepší je jezdit buldozerem!

0/0
4.2.2007 19:58

morbidni_kreten

Re: :-P

s tryskovým pohonem..

0/0
4.2.2007 19:59

boris

prvni krok k pochopeni problemu neni o matematice !!!

znam prvni krok k tomu, rozlustit tento problem. ... pokud ma nekdo vazny zajem, napis mi na boris.simonik@atlas.cz

Pozn. na zakladni skole jsem resil matematicke rovnice strednich skol ... a pokud chces cennou radu, zaplatis![>-]

0/0
4.2.2007 19:42

lukinoo

Re: prvni krok k pochopeni problemu neni o matematice !!!

;-D:-©Rv tschuraku hloupej

0/0
4.2.2007 20:25

redy

Re: prvni krok k pochopeni problemu neni o matematice !!!

jeste ze se na stredni opakuje to co, se clovek naucil na zakladce :D

0/0
4.2.2007 22:17

yamamotor

oukej

pouzij internet misto cestovani....nebo helikopteru jestli se ti nechce cestovat autem...zatim problem vyresen a pocty si nechte do skoly

0/0
4.2.2007 19:33

FDP

...

...klasika... ...operation research a Simplextabelle...

0/0
4.2.2007 19:16

vlastikw

Re: ...

klasiky miluju, kort kdyz si mysli ze simplex vyresi vsechno - ten uz je davno nahrazovan efektivnejsimi metodami Branch and Bound a Branch and Cut. Simplex sice funguje relativne dobre, ale teoreticky v nejhorsim pripade prochazi vsechny moznosti.

0/0
18.2.2007 22:30

vyrobce

Blazni

8-o8-o

Jiz to mam davno vyreseno

ale nemam odkaz kam to poslat

ma snad nekdo zajem ?

0/0
4.2.2007 19:03

Karel Pochop

Re: Blazni

Myslím že tohle bude dostatečné, ale s tím zasílání řešení je to trochu složitější.

http://www.claymath.org/millennium/Rules_etc/

0/0
4.2.2007 19:19

vyrobce

Re: Re: Blazni

:-):-):-)

Dekuji

0/0
4.2.2007 19:26

Azmidiske

Výpočty

A proč by se měly propočítávat všechny možnosti? Nestačilo by do výpočtů zahrnout jen možnosti, kde se z jednoho města jede dál např. jen do 5 nejbližších (nebo jinékritérium, např. jen do měst vzdálených X km)? Tím by se přeci ušetřilo strašně možností (do dalších 12 měst bych to vlbec nepočítal, protože když např. pojedu přes nejdřív z NY do LA a pak se budu vracet po jednotlivých městech, musí to být nutně delší než jet rovnou po městech ne?)

0/0
4.2.2007 18:27

Estd

Re: Výpočty

Ruzne heuristiky samozrejmne existuji, ale ty nezaruci optimalni reseni o ktere tu jde. Napr je celkem trivilani nalezt cestu maximalne 2x tak dlouhou nez je optimum.

0/0
4.2.2007 18:40

asd

Re: Výpočty

:) tak to zkus matematicky dokazat, ze pokud vyberes jen X nejblizsich mest, cesta vysledna cesta bude vzdy nejkratsi... obecne to takhle samozrejme nefunguje

0/0
4.2.2007 18:40

KSFJ

Re: Výpočty

hezka myslenka ale :-)

jak poznas ze je to mesto blizko? pocitac neumi to co ty "kouknu a vidim" o by musel porovnat vzdalenosti se vsemi mesty a uz jses tam kde jsi byl.

0/0
4.2.2007 19:00

xy

Re: Re: Výpočty

o tom to neni, protoze pocitac se taky umi "koukat" kdyz mu zadas souradnice. Problem je, ze ani ty ocima neurcis nejkratsi vzdalenost.

0/0
4.2.2007 21:58

salam_humusajn

Nový typ počítače

Nový typ počítače tento matematický problém rozhodně nemůže vyřešit, jak se v článku tvrdí, protože třídy problémů P a NP (kam patří travelling salesman) jsou jasně definované vzhledem k abstraktním Turingovým strojům a ne k nějakým "současným počítačům". Naprostá většina informatiků si myslí, že s vysokou pravděpodobností P<>NP, což je ekvivalentní tomu že efektivní řešení tohoto problému neexistuje.

Jinak "travelling salesman" je spíš takové zlidštění abstraktně definovaného problému. Obchodníkům by jeho řešení ovšem příliš nepomohlo - pokud by nějaké efektivní existovalo, znamenalo by to automaticky, že existuje efektivní řešení na všechny problémy ze třídy NP a tím pádem by se např. naprostá většina dnešních bezpečnostních kódů stala lehce prolomitelnými.

0/0
4.2.2007 17:49

Olda

Re: Nový typ počítače

Pak by se z obchodního cestujícího stal kurýr s tajnou depeší (protože by ji nšlo bezpečně zakódovat) jedoucí po optimálně spočítané trase.

0/0
4.2.2007 18:24

S-Tony

Aha

Podle mně by to měl fakt radši řešit někdo kdo matice vůbec nerozumí. Protože pro matematika je to neřešitelný problém, ale pro laika nikoli :-)

Vyřesit to není problém, problém je dokázat že lepší řešení neexistuje :-(

0/0
4.2.2007 17:35

LubosTX

Je to zrejme NP-uplny problem

a jeho reseni zavisi na vyvoji naseho chapani fascinujici otazky P=?NP. Cela vec je subtilnejsi nez clanek sdeluje ...8-o

0/0
4.2.2007 17:22

99,5

Kdybych

o tomhle problému nevěděl už přes 30 let, protože nás to učili ve škole, z článku bych ho rozhodně nepochopil.

0/0
4.2.2007 16:59

opportunity

Re: Kdybych

R^

0/0
11.2.2007 0:16

Kokesch

Co takhle krok stranou?

Zkuste spíše vymyslet, jak to udělat, aby ten cesťák vůbec nemusel jezdit. Optimalizovat se má to co se vyplatí optimalizovat. Např. je blbost vymýšlet, jak pošťácké auto rozveze dopisy s fakturami za elektřinu od ČEZu k jednotlivým domácnostem a firmám, které od něj odebírají elektřinu. Jednodušší je postavit elektronický portál, na kterém si všichni mlžou přes internet faktury stáhnout. Ušetří se tuny papíru a pošťák může zůstat na podpoře sedět doma. Taky se nespálí žádný benzín či nafta a nikdo už primárně nemusí kácet stromy na výrobu papíru.

Qui bonno? Všichni tak budou better-off. Budem na tom líp. ;-D

0/0
4.2.2007 16:57

redy

Re: Co takhle krok stranou?

jako vtip to neni spatne

0/0
4.2.2007 17:28

Kokesch

Re: Re: Co takhle krok stranou?

Když myslíš ... uvidíme. Do roka a do dne Kozino.

0/0
4.2.2007 17:41

redy

Re: Re: Re: Co takhle krok stranou?

tady se jedna o obecnou rovinu a o tvorbu algoritmu, ktery by nasel optimalni reseni tak, aby to netrvalo 10 ci 100 let.

Tvuj ukrok stranou je fajn a nic proti nemu nemam. Dokonce ho podporuji, ale to jsme se presunuli do trochu jine dimenze...

0/0
4.2.2007 17:54

Trm

,,nezodpovezeny problem matematiky'' TO SNAD NE!

Autor je hovado. HOVADO. Jinak to nejde nazvat. Prosim vas, pani novinari, misto popularizacnich clanku, v kterych jsou NESMYSLY, radsi piste ty vase blaboly o tom, jak zase nejaky vtipalek vylepip billboard, aby nekoho pospinil. Tohle vam jde, ale na zbytek evidentne nemate.

0/0
4.2.2007 15:15

Karl

Re: ,,nezodpovezeny problem matematiky'' TO SNAD NE!

Ty si hovado!!! A jestli Te zajimaji nejake "vtipne" billboardy, tak si cti sracky jako je Blesk a ne iDnes!!!

0/0
4.2.2007 16:01

Klokan

Re: ,,nezodpovezeny problem matematiky'' TO SNAD NE!

Tak to vyřeš, chytráku. Budeš mít pokoj od takových článků a k tomu milion dolarů

0/0
4.2.2007 16:03

redy

sachovnice

55340232152408653823

0/0
4.2.2007 15:02

99,5

Re: sachovnice

9223372036854775809

0/0
4.2.2007 17:02

btw

Re: Re: sachovnice

8-o těžko může vyjít lichý číslo, na konci je 8. A ten první je úplně vedle ;-D

0/0
4.2.2007 18:21

asd

Re: Re: Re: sachovnice

2^63=9223372036854775808 ;-)

0/0
4.2.2007 18:45

asd

Re: Re: Re: Re: sachovnice

a stejne je to zajimavy, kdyz ma sadhovnice 64 policek ze ;-D

0/0
4.2.2007 18:46

Pokk

Re: Re: Re: sachovnice

Pokud je na prvním políčku 1 zrníčko, na druhém 2, ... celkem bude na pokrytí celé šachovnice třeba LICHÝ počet zrníček... :-P:-P:-P

0/0
4.2.2007 18:54

Slavik

Re: Re: Re: Re: sachovnice

tak ted jsi to rozsek R^

0/0
4.2.2007 19:23

btw

Re: Re: Re: Re: sachovnice

ovšem, ale řeč je tu ale o počtu na posledním poli (2^63)

0/0
4.2.2007 19:26

redy

Re: Re: Re: sachovnice

ten prvni spocital vsechny zrnicka, ktere na sachovnici budou ;)

0/0
4.2.2007 21:47

btw

Re: Re: Re: Re: sachovnice

bohužel opět nemohu souhlasit. součet všech zrn = suma n;2^(x+1);-1<=x<=62] = 2^64 - 1 = 18446744073709551615 !

0/0
4.2.2007 23:36

btw

Re: Re: Re: Re: Re: sachovnice

sorry, před tou dvojkou má bejt taky hranatá, ne n;

0/0
4.2.2007 23:38

redy

Re: Re: Re: Re: Re: sachovnice

v tom pripade nekde maple udelal chybu (nebo spis ja, kdyz jsem u to zadaval ke spocitani) ;)

0/0
5.2.2007 16:29

99,5

Re: Re: Re: Re: Re: sachovnice

R^ Reaguji opožděně a omlouvám se, máš samozřejmě pravdu. Odvodil jsem si to včera indukcí od 2 políček, bohužel jen v hlavě  a špatně.

0/0
5.2.2007 18:00

inosh

Ten článek mě dostal

Moje práce se častým cestováním po ČR velice podobá obchoďákovi. Vždycky jsem si říkal, proč, sakra, navigace ani např.mapy.cz nenabízí zadání kupř. 5 měst tak, aby výsledkem byla nejekonomičtější (nejkratší) trasa. Díky za vysvětlení a doufám, že nějaká chytrá hlava taky pomůže nám v reálném životě.

0/0
4.2.2007 14:53

asd

Re: Ten článek mě dostal

no pro pet mest ti to spocte kazdy lepsi soft s planovacem cest ;)

0/0
4.2.2007 18:48

inosh

Re: Re: Ten článek mě dostal

Fakt? Ja pouzivam TomTom navigaci a jinak jen freeweby jako supermapy, mapy atp. Deje vedet, jaky program pouzit. Kdyz usetrim 10 km denne, budu rad.  :)

0/0
4.2.2007 18:53

asd

Re: Re: Re: Ten článek mě dostal

napada me infomapa, route 66

0/0
4.2.2007 20:26

lives

Re: Re: Re: Re: Ten článek mě dostal

Infomapa do 10 prujezdnich mist ani nezobrazuje zadny varovani, pokud jich mas vic nez 10 tak te informuje ze to muze trvat. V praxi pouzitelne je to pro max 12 mist. To se da jeste mluvit o vypoctu v "realnem case" - do jedne minuty.

0/0
4.2.2007 23:09

Geodis

bli.t na pr.del

:-©(Y)

0/0
4.2.2007 14:35





Finance.iDNES.cz radí

Víte, že investiční doporučení na růst kurzu dolaru tu byla už před rokem?

Další rady k nezaplacení

Dopřejte si vše a přesto utrácejte chytře!

V sekci osobni.finance.idnes.cz naleznete výhodné nabídky finančních produktů, energií a telefonování.

Vstupte do obchodu

Poraďte se s odborníkem

Nevíte si rady s finančními otázkami? Naši odborníci vám vždy poradí v každé životní situaci.

Vstoupit do poradny

Najdete na iDNES.cz



mobilní verze
© 1999–2017 MAFRA, a. s., a dodavatelé Profimedia, Reuters, ČTK, AP. Jakékoliv užití obsahu včetně převzetí, šíření či dalšího zpřístupňování článků a fotografií je bez souhlasu MAFRA, a. s., zakázáno. Provozovatelem serveru iDNES.cz je MAFRA, a. s., se sídlem
Karla Engliše 519/11, 150 00 Praha 5, IČ: 45313351, zapsaná v obchodním rejstříku vedeném Městským soudem v Praze, oddíl B, vložka 1328. Vydavatelství MAFRA, a. s., je členem koncernu AGROFERT.