  |
|
| ° 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ść |
| prodrive
|
Posted: 5 Mar 2001 22:22:57 [ciach..] Problem ten nie ma rozsadnych rozwiazan.(tzn dzialajacych w czasie wielomianowym) Jest to problem NPC i jest on klasy O(N!). Jedynym sposobem jest sprawdzenie wszystkich drog i wybranie najkrotszej. Brzmi to fajnie ale dla np.dla 20 miast komputer rozwiazywal by ten problem przez kilkadziesiot tysiecy lat (zakladajac ze w ciagu 1 sek analizuje 1000000 drog). Jest algorytm dzialajacy w czasie wielomianowym O(N^3) ktory znajduje siezke nie dluzsza niz 1.5*dlugosc sciezki najkrotszej. A moze masz znalezc najkrotsza droge pomiedzy dwoma miastami - to juz latwo zrobic. Pozdrawiam |
| Pawel F. Gora
|
Posted: 6 Mar 2001 09:27:44 Poszukuje pomocy (najlepiej do czwartku : 8 .III. 2001) z zadaniem z
informatyki Chodzi bowiem o algorytm (lub przynajmniej pomysł na niego), który na podstawie współrzędnych n miejscowości będzie obliczał najkrótszą drogę takążeby dotrzećdo wszystkich miast(miasta są połączone każde z każdym). Rozumiem, że do najblizszego czwartku masz rozwiązać problem komiwojażera. Życzę sukcesów. Jeśli natomiast chcesz zapoznać się z istniejącymi (niedoskonałymi!) próbami rozwiązania tego problemu, zapuść swoją ulubioną wyszukiwarkę z hasłem "traveling salesman" (może też być "travelling salesman", ale pisownia amerykańska da więcej linków). Paweł Góra Institute of Physics, Jagellonian University, Cracow, Poland A physical entity does not do what it does because it is what it is, but is what it is because it does what it does. |
| Hessi
|
Posted: 6 Mar 2001 12:25:44 A moze masz znalezc najkrotsza droge pomiedzy dwoma miastami - to juz
latwo zrobic.
Niestety miast ma być n (i n ma byćmniejsze od 256) i przez wszystkie n miast musze przejechać... |
| Piotr Wyderski
|
Posted: 6 Mar 2001 17:37:23 Poszukuje pomocy (najlepiej do czwartku : 8 .III. 2001) z zadaniem z informatyki Chodzi bowiem o algorytm (lub przynajmniej pomysł na niego), który na podstawie współrzędnych n miejscowości będzie obliczał najkrótszą drogę takążeby dotrzećdo wszystkich miast(miasta są połączone każde z każdym). Rozumiem, że do najblizszego czwartku masz rozwiązać problem komiwojażera. Życzę sukcesów. To nie jest problem komiwojazera, w tresci nie ma nakazu, zeby kazde z miast bylo odwiedzane dokladnie jednokrotnie. Calkiem mozliwe, ze dzieki temu to sie da zrobic w czasie wielomianowym. Gdyby np. zaczac od skonstruowania minimalnego drzewa rozpinajacego tego grafu, to sie od razu dostaje taka sciezke o dlugosci max. dwa razy wiekszej niz minimalna. Moze cos sie uda wymyslic na tej bazie ? Pozdrawiam Piotr Wyderski |
| Piotr Wyderski
|
Posted: 6 Mar 2001 17:47:50 [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.) Pozdrawiam Piotr Wyderski |
| Jakub Wroblewski
|
Posted: 7 Mar 2001 03:07:04 Witam, 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. O ile wiem, to TSP jest nieaproksymowalny w czasie wielomianowym, tzn. dla dowolnej stalej c znalezienie trasy najwyzej c razy dluzszej od minimalnej jest NP-trudne. Natomiast ograniczenie 1.5 da sie osiagnac wielomianowo dla przypadku metrycznego, co pokazano w: N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1975. Wiecej o aproksymowalnosci: D.S. Hochbaum (ed.). Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston 1997. Pozdrawiam, Jakub Wroblewski |
| Pawel F. Gora
|
Posted: 6 Mar 2001 18:20:26 Poszukuje pomocy (najlepiej do czwartku : 8 .III. 2001) z zadaniem z informatyki Chodzi bowiem o algorytm (lub przynajmniej pomysł na niego), który na podstawie współrzędnych n miejscowości będzie obliczał najkrótszą drogę takążeby dotrzećdo wszystkich miast(miasta są połączone każde z każdym). Rozumiem, że do najblizszego czwartku masz rozwiązać problem komiwojażera. Życzę sukcesów. To nie jest problem komiwojazera, w tresci nie ma nakazu, zeby kazde z miast bylo odwiedzane dokladnie jednokrotnie. No cóż, wydawało mi się, że z warunku "najkrótsza droga" wynika to, że każde musi byc odzwiedzone jednokrotnie. 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? Nb, wszyscy inni też mówią o wyjściowym zagadnieniu "TSP" i jakoś nikt nie protestuje :-) Paweł Góra Institute of Physics, Jagellonian University, Cracow, Poland A physical entity does not do what it does because it is what it is, but is what it is because it does what it does. |
| . 1 . 2 . 3 . >> |