Základní informace o projektu

Fórum o projektu
Odpovědět
Zpráva
Autor
Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Aktuální stav projektu

#1 Příspěvek od forest »

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/

Pallando
42.1052631579 %
42.1052631579 %
Příspěvky: 763
Registrován: sob 08 zář, 2007 11:16
ID CNT statistics: 3749
Bydliště: Ostrava

#2 Příspěvek od Pallando »

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

Uživatelský avatar
Marty McFly
5.26315789474 %
5.26315789474 %
Příspěvky: 23
Registrován: úte 26 čer, 2007 13:38
Bydliště: Vatín
Kontaktovat uživatele:

#3 Příspěvek od Marty McFly »

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 :-)
Obrázek

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

#4 Příspěvek od forest »

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.

Uživatelský avatar
KPX
42.1052631579 %
42.1052631579 %
Příspěvky: 885
Registrován: pát 03 lis, 2006 23:24
ID CNT statistics: 349
Bydliště: Praha

#5 Příspěvek od KPX »

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.
Obrázek

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

#6 Příspěvek od forest »

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

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

#7 Příspěvek od forest »

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.

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: BOINC / TSP

#8 Příspěvek od forest »

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

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: BOINC / TSP

#9 Příspěvek od forest »

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

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Základní informace o projektu

#10 Příspěvek od forest »

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/

Honza
63.1578947368 %
63.1578947368 %
Příspěvky: 3245
Registrován: pát 03 lis, 2006 10:46

Re: Základní informace o projektu

#11 Příspěvek od Honza »

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.

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 19635
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: Základní informace o projektu

#12 Příspěvek od forest »

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

Honza
63.1578947368 %
63.1578947368 %
Příspěvky: 3245
Registrován: pát 03 lis, 2006 10:46

Re: Základní informace o projektu

#13 Příspěvek od Honza »

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

Odpovědět

Zpět na „TSP“