  |
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
|
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
 |
Matma / GRAFY I INNE... |
| << . 1 . 2 . 3 . >> |
| Autor | Wiadomość |
| Maciek
|
Posted: 6 Mar 2001 18:54:40 (.....) No cóż, wydawało mi się, że z warunku "najkrótsza droga" wynika to, że każde musi byc odzwiedzone jednokrotnie. Poniekad. Dla grafu 3-wezlowego: (A)---------(B)----------------------------(C) AC = AB + BC, w cyklu A-B-C-A droga z C do A biegnie przez B. Czy zaliczymy to jako powtorna wizyte w B czy nie, to kwestia czysto formalna. W wielu przypadkach praktycznych jednak zatrzymanie sie w B i ponowne wyruszenie w dalsza droge do A zwieksza koszt. Przelot ponad B bez zatrzymania jest tanszy niz miedzyladowanie. To daje ostra nierownosc w kazdym trojkacie. A wtedy faktycznie najkrotszy cykl Hamiltona przez kazdy wierzcholek grafu przechodzi raz. Maciek |
| Maciek
|
Posted: 6 Mar 2001 18:54:48 [ciach] Jest algorytm dzialajacy w czasie wielomianowym O(N^3) ktory znajduje siezke nie dluzsza niz 1.5*dlugosc sciezki najkrotszej. Dla _kazdego_ grafu ? To ja poprosze o opis tego algorytmu. AFAIR wyznaczenie cyklu Hamiltona to sie da zrobic w czasie wielomianowym tylko dla pewnych typow grafow (takich, gdzie odleglosci miedzy wezlami spelniaja nierownosc trojkata.) Wyznaczenie "cyklu Hamiltona" czy "najkrotszego cyklu Hamiltona"? Bo jesli to pierwsze, to niezaleznie od odleglosci w czasie liniowym: wezel pierwszy, drugi, .... n-ty, pierwszy, dziekujemy. Maciek |
| Jakub Wroblewski
|
Posted: 6 Mar 2001 20:28:49 Witam, Z innych
listów w tym wątku widzę, że problem jest też formułowany dla "odległości" nie spełniających nierówności trójkąta. Przyznam, że o czymś takim nie słyszałem. Jakieś przykłady? TSP z nierownowscia trojkata to raczej szczegolny przypadek, niz regula. Przyklad niemetryzowalnego TSP? Za "odleglosc" przyjmij czas przejazdu po drogach laczacych miasta (nie zezwalamy na powtorny wjazd do odwiedzonego miasta) - taki parametr nie musi byc symetryczny ani spelniac war. trojkata; w zasadzie mozna przekonujaco uzasadnic dowolna macierz "odleglosci". "Praktyczne" zastosowanie niemetryzowalnego TSP: pokazanie, ze zagadnienie istnienia cyklu Hamiltona jest szczegolnym przypadkiem TSP. Jeszcze praktyczniejsze zastosowanie niemetryzowalnego TSP: Zalozmy, ze mamy n komputerow wyposazonych w karty sieciowe, kazda z nich ma 2 wyjscia. Kazda (lub prawie kazda) karta pracuje w innym standardzie, ale dostepne sa kabelki pozwalajace na polaczenie dowolnych dwoch komputerow. Polaczyc wszystkie komputery w siec, nie uzywajac koncentratorow, rozgaleziaczy itp. (to nam implikuje architekture typu pierscien lub "sznurek" - jak to sie fachowo nazywa?). Zminimalizowac koszt budowy sieci, znajac ceny poszczegolnych rodzajow kabelkow. Widac, ze w powyzszym zadaniu z przyczyn zasadniczych nie jestesmy w stanie wrocic do odwiedzonego juz "miasta", a w dodatku ceny kabelkow nie musza spelniac nierownosci trojkata (bo zostaly wziete z sufitu przez producentow). Pozdrawiam, Jakub Wroblewski |
| Hessi
|
Posted: 6 Mar 2001 21:04:27 (..)w tresci nie ma nakazu, zeby kazde z miast bylo odwiedzane dokladnie jednokrotnie.
Oki moj blad : kazde miasto moze byc odwiedzone jednokrotnie kazde ma polaczenie z innym |
| Filip
|
Posted: 6 Mar 2001 21:13:17 Graf podany w zadaniu jest gesty, wiec podane przez ciebie metody (szczegolnie MST), powinny dac rozsadny wynik, w rozsadnym czasie. Dyskusje na temat tego ze jest to problem NP-zupelny sa nie na miejscu (mam na mysi te powyej). Problem jest dosc szczegolny. Graf jest gesty (bardzo gesty) a to wiele zmienia... Filip |
| Piotr Wyderski
|
Posted: 7 Mar 2001 08:19:46 Oki moj blad : kazde miasto moze byc odwiedzone jednokrotnie
kazde ma polaczenie z innym Aaaa... to nie pozostaje mi nic innego, jak dolaczyc sie do zyczen Pawla Gory :-) Wyglada na to, ze ktos sie chce zabawic Twoim kosztem. Pozdrawiam Piotr Wyderski |
| Pawel F. Gora
|
Posted: 7 Mar 2001 08:31:08 TSP z nierownowscia trojkata to raczej szczegolny przypadek, niz
regula. Przyklad niemetryzowalnego TSP? <cut ciekawe przykłady Znów się czegoś na sieci nauczyłem. Dziękuję. |
| << . 1 . 2 . 3 . >> |