Czech National Team

Vyšel nový projekt TSP, bohužel si u něho zatím netroufnu popsat co přesně se na něm bude dělat. Pokud to někdo ze současných informací na webu projektu pochopí, budu rád když to sem napíše.
Stránky projektu naleznete zde:

http://bob.myisland.as/tsp/

Nejsem sice žádný matematik, ale to, co řeší, je teorie grafů (konkrétně tedy nejkratší vzdálenost pro spojení několika bodů).

Jestli jsem to dobře pochopil, jde o to najit nejkratsi cestu mezi n body. Jde o problem obchodniho cestujiciho, ktery musi projet cile cesty co nejoptimalneji (nejkratsi cestou, tudis nejrychleji..). Jako priklad pouzil autor projektu mesta v USA a mezi nima hleda nejoptimalnejsi cestu. Nebo tak nějak

Tak to už by mohlo být to co v tom textu na projektu popsáno je. Fakt si netroufám to z těch několika vět sám přeložit oč jde a odkaz na nějaké podrobnosti nikde není.

Díky moc Marty a kdyby z toho někdo vyčetl ještě více, budeme jen rádi.

No, navic jeste pisou, ze na reseni toho problemu obchodniho cestujiciho si vybrali 48 hlavnich mest americkych statu, protoze na dopravni vzdalenosti mezi nimi existuje dobra a presna databaze. A ze je to cvicny problem na odladeni projektu. Az to odladi, chteji se venovat necemu serioznejsimu, ale asi ze stejneho soudku, neco o genetickych algoritmech.

TSP přešlo, jako již spousta jiných projektů, na fixní kredit za odvedenou práci.

Ikdyž projekt přešel na fixní kreditové ohodnocení, stále má quórum 3, což se nelíbí mnoha počtářům na projektu, tak možná dojde alespoň ke snížení na 2.

Generátor nových jednotek by měl nyní makat každých 30 minut místo 2h a tak by mělo být více práce na zpracovávání.

TSP by měl být brzy další z projektů podporujících konzole PS3.

Tento matematický projekt, se zabývá tzv. „Problémem obchodního cestujícího“.
Na mapě je zvoleno n měst a jejich vzájemná vzdálenost pro každou z dvojic. Problémem obchodního cestujícího je určit takové pořadí návštěv jednotlivých měst, aby každé město bylo navštíveno pouze jednou, výsledná délka byla co nejkratší a cestující se vrátil zpět do města, kde cestu začal.
Jako příklad použil autor projektu na úvod města v USA a mezi nimi hledá nejoptimálnější cestu. Pro výpočty bude používáno několik metod, tedy i aplikací.

Stránky projektu: http://bob.myisland.as/tsp/

Zkusim doplnit a upresnit, nebot ta posledni veta na me pusobi dojmem, ze se trochu potratilo porozumeni. "Následující úkoly se budou zabývat například mravenčími koloniemi" - nejde o práci lesníků v chráněné oblasti. "podobnými oblastmi využití této metody" - no tou oblasti je prace TSP; které další podobné jsi měl na mysli?

Nosnym tematem projektu je opravdu problem obchodniho cestujiciho.
Duraz ale neni kladem na nalezeni nejkratsi cesty (jak by se z popisu mohlo zdat), ale zkouseni a testovani ruznych metodologickych pristupu k tomuto problemu.
Zakladni metoda Brute Force (hruba sila) slouzi jako nastroj validizujici ostatni metody - kuprikladu prave rozpracovavana metoda mravenci kolonie.

Akcent tohoto projektu je v tom, ze se k jasne definovanemu tematu snazi pristupovat ruznymi metodami.

Já to pochopil tak, že ty města USA jsou úvodním tématem a dále se budou výsledky a další výpočty používat na jiné zaměření.
Pokud jde v podání mravenčí kolonie pouze o jinou metodu, tak těch je hned několik jak jsem četl. Některé jsou jen srovnávací, jiné rychlé a méně přesné atd.
Díky za upřesnění, ten popis upravím, či spíše tu poslední větu smáznu.

Edit:Tak jsem tu poslední větu přepracoval

Já to zase pochopil jedním ze základních pohledů vědy, tedy rozlišením výzkumný problém/tema a metoda.

TSP je obecný problém v matematice, resp. kombinatorice. Města jsou taková klasická ilustrace, pochopitelná i pro běžné lidi.
Metodu lze ale dál dopracovávat a města třeba groupovat podle států, regionů nebo do jiných clusterů. Takové téma řeší třeba politik, když navstěvuje různé státy.
Nebo je lze řadit i lehce hierarchicky - každý cluster má své centrum. A mezi centry jsou extra trasy. To je úloha pro logistické firmy, kde náklady na krátké trasy jedou v rámci clusteru a velké vzdálenosti mezi clustery. Zde je třera brát v potaz nejen vzdálenost, ale také čas. A zde nemusí být podmínkou, že se nutně musí vracet do výchozího bodu - protože by to třeba znamenalo, že se kamion bude vracet prázný.
A nebo to lze aplikovat v geometrii. Zadáním je pak zjistit, kolik vrcholů potřebuji, abych popsal křivku aniž bych znížil její přesnost o více než x procent? A to zase není daleko třeba od bezierových křivek a optimalizací cest třeba v Adobe Illustratoru a už jsme doma...chtěl jsem říci u grafiky.

Všechno jsou to úlohy výzkumného tématu TSP nebo na něm založené.


No a pak máme metody, nebo přesněji algoritmy výpočtu. Od jednoduché Brute Force (v podstatě náhodné), iterativní, heristické atd.
Každý z těchto algoritmů vyhovuje na různé nasazení - podle počtu uvažovaných lokalit, náročnosti výpočtu, rychlosti vyhledání dostatečně optimálního řešení (tj. ne nutně nejlepšího) atd. Viz třeba ten problém logistické firmy, kde není jeden cestující a pár destinací, ale stovky pohybujících se cestujících nesoucí desetitisíce balíčků v rámci mnoha clusterů. Zde nejde o to najít nejlepší řešení, ale rychle najít dostatečně dobré řešení.