Základní informace o projektu
- forest
- 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
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/
Stránky projektu naleznete zde:
http://bob.myisland.as/tsp/
- Marty McFly
- 5.26315789474 %
- Příspěvky: 23
- Registrován: úte 26 čer, 2007 13:38
- Bydliště: Vatín
- Kontaktovat uživatele:
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
- KPX
- 42.1052631579 %
- Příspěvky: 885
- Registrován: pát 03 lis, 2006 23:24
- ID CNT statistics: 349
- Bydliště: Praha
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.
- forest
- 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
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í.
- forest
- 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
TSP by měl být brzy další z projektů podporujících konzole PS3.
- forest
- 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
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/
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/
Re: Základní informace o projektu
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.
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.
- forest
- 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
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
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
Re: Základní informace o projektu
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í.
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í.