jak na to!

tak boris nadhoď

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í ....

:-P

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

Re: :-P

s tryskovým pohonem..

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!

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

tschuraku hloupej

oukej

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

...

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

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.

Blazni

Jiz to mam davno vyreseno

ale nemam odkaz kam to poslat

ma snad nekdo zajem ?

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/

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?)

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.

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.

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.

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 :-(