  |
|
| ° Forum ° Rejestracja ° Szukaj ° | |
| Auto giełda ° wnętrzowe stacje transformatowe |
 |
Matma / Ukadanie grafikow - algorytm |
| << . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 ... 13 . 14 . >> |
| Autor | Wiadomość |
| Maciej Woźniak
|
Posted: 8 Paź 2008 19:03:50 Bez większego problemu podam mapę z 100000000000
punktów, podam dla niej trasę i udowodnię, że jest ] optymalna. To nie znaczy, że potrafię rozwiązać problem komiwojażera dla 100000000000 punktów. To jest belkot, co pan pisze To co pan pisze, to są głównie wyzwiska, czasem, tak jak w tym przypadku, bzdury, z rzadka coś sensownego. |
| A.L.
|
Posted: 8 Paź 2008 19:12:05 On Wed, 8 Oct 2008 11:42:27 -0700 (PDT), Wit Jakuczun On Wed, 8 Oct 2008 09:10:15 -0700 (PDT), Wit Jakuczun
Rozwiązania przybliżone. Nawet prosty algorytm genetyczny takie coś wyliczy. Nie opowiadaj banialuków. Widać, że mimo sugestii, nie zajrzałeś do polecanej książki. AG nie jest dobrą heurystyką do problemu TSP. Rozkraczy się przy zadaniu wielkości parudziesięciu miast. Nie mówiąc o wariacjach problemu TSP. panie Kolego, on nie zajzry bo ksiazka kosztuje 50 dolcow, wymaga znajomosci angielskiego, a jak juz by jja dostal to nie przebrnie poza rozdzial zwany "Podziekowania" Też mi się wydaje, że to przypadek beznadziejny... Wystarczy popatrzec co wypisuje na "fizyce". Wystepuje czesto na "paranauki", nie mowiac o tym ze jest cennym dyskutantem na "filozofii" A.L. |
| Simp
|
Posted: 8 Paź 2008 20:12:42 Dla przypadkowej sieci zawsze będzie pełno różnych cykli o minimalnej długości. Najwyżej zazwyczaj. Niemniej, weź sobie 10000 punktów. Dla każdej pary punktów wylosuj odległość. Liczbę rzeczywistą, powiedzmy, z przedziału (0,10). Prawdopodobieństwo, że znajdziesz w ogóle 2 różne cykle o tej samej długości, wynosi według mnie 0. Masz inne zdanie? Musisz jeszcze podać precyzję tych liczb rzeczywistych. Przyjmując precyzję typu double, chyba 53 bity, otrzymamy długości całkowite z przedziału: (0, 2^53). No i dlatego będzie niewielka szansa znalezienia tras równej długości, ale trzeba by to wyliczyć. |
| Michal Przybylek
|
Posted: 8 Paź 2008 20:23:55 Bez większego problemu podam mapę z 100000000000
punktów, podam dla niej trasę i udowodnię, że jest ] optymalna. To nie znaczy, że potrafię rozwiązać problem komiwojażera dla 100000000000 punktów. To jest belkot, co pan pisze To co pan pisze, to są głównie wyzwiska, czasem, tak jak w tym przypadku, bzdury, z rzadka coś sensownego. Kiedy AL ma właśnie rację - w praktyce liczy się to, czy potrafimy rozwiązywać praktyczne problemy, a nie czy istnieją jakieś wydumane problemy, których rozwiązać nie potrafimy. W tym sensie, klasyczna teoria złożoności (mówiąca właśnie o złożoności pesymistycznej) jest do pewnego stopnia biciem piany (to, że z tego bicia piany wychodzą czasami sensowne wnioski, to już zupełnie inna historia). Nas nawet nie interesuje przypadek średni. Nas po prostu interesuje przypdek spotykany w rzeczywistości. Np. algorytm simplex, świetnie sprawdza się w rzeczywistych problemach, choć łatwo jest znaleźć wydumane sytuacje, z którymi będzie miał problem. Rzeczywistości na szczęście to nie przeszkadza. |
| A.L.
|
Posted: 8 Paź 2008 22:57:35 On Wed, 8 Oct 2008 21:03:50 +0200, Maciej Woźniak Bez większego problemu podam mapę z 100000000000
punktów, podam dla niej trasę i udowodnię, że jest ] optymalna. To nie znaczy, że potrafię rozwiązać problem komiwojażera dla 100000000000 punktów. To jest belkot, co pan pisze To co pan pisze, to są głównie wyzwiska, czasem, tak jak w tym przypadku, bzdury, z rzadka coś sensownego. Z Panem nei ma o czym dyskutowac, bo to Pan generuje bialy szum. Dla Panskiej informacji, problem komiwojazera nie ma nic wspolnego z mapami, losowaniem i podobnymi pierdolami. Formuluje sie tak: dany jest graf nieskierowany z wagami, posiadajacy cykle Hamiltona. Sposrod wszystkich cykli Hamiltona znalezc taki ktorego suma wag jest najmniejsza. Jest to sformulowanie najprostsze, jest wiele innych, bardziej skomplikwoanych Jak Pan ma cos na ten temat do powiedzenia, to z checia poslucham A.L. |
| mlwozniak
|
Posted: 9 Paź 2008 07:36:25 To jest belkot, co pan pisze
To co pan pisze, to są głównie wyzwiska, czasem, tak jak w tym przypadku, bzdury, z rzadka coś sensownego. Z Panem nei ma o czym dyskutowac, bo to Pan generuje bialy szum. A pan jest głupim, stetryczałym dziadem i też nie ma z panem o czym dyskutować, bo pan generuje wyzwiska, bzdury i z rzadka coś sensownego. Dla Panskiej informacji, problem komiwojazera nie ma nic wspolnego z mapami I fakt, że na stronie z rozwiązaniami, o których mówimy, są 3 rysunki w tym 2 mapy, to czysty przypadek. |
| mlwozniak
|
Posted: 9 Paź 2008 07:42:04 Dla Panskiej informacji, problem komiwojazera nie ma nic wspolnego z
mapami I fakt, że na stronie z rozwiązaniami, o których mówimy, są 3 rysunki w tym 2 mapy, to czysty przypadek. Och, pomyliłem się, 4 rysunki i 3 mapy. Ale głupiec ze mnie. |
| << . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 ... 13 . 14 . >> |