Szukanie najkrótszej drogi w grafie [inaczej]

Odpowiedz Nowy wątek
2006-11-08 20:08
0

Witam !

Stanąłem oto przed takim problemem. Za zadanie mam obliczyć najkrótszą drogę z każdego spośród pierwszych dwudziestu wierzchołków do każdego z pozostałych pierwszych dwudziestu wierzchołków w danym grafie (nieskierowanym). Graf ma jednak dużo wiecej wierzchołków (maks. 20000) i oczywiscie moze zajsc sytuacja ze najkrótsza droga np. z wiercholka 5 do 18 prowadzi przez wierzcholek nr. 17564 :/ . Idealnie pasowałby do tego algorytm Roya - Warshalla. Niestety pojawia sie pewien problem. Maksymalna ilosc pamieci jaką moge wykorzytsac (ograniczenie dotyczy stosy, sterty itd.) to 64 Mb. W przypadku grafu o 20000 wierzchołków deklarując tablice dwuwymiarową int t[20000][20000] zużywam jakies 20000 20000 4 / (1024 * 1024) Mb co daje nam około ponad 1000 Mb [???]

Czy ktoś zna inną metode która moglaby mi pomoc</b>


I wrogu dziękuje bo siłe hoduje na tym co on knuje...

Pozostało 580 znaków

2006-11-08 21:42
nicka
0

A nie możesz poprostu puścić DFS(lub BFS) dla każdego z 20 wierzchołków? to rozwiązanie liniowe i pamięci też potrzebuje tyle co jest danych. Nie napisałeś żeby to był graf z wagami więc nie wiem skąd tutaj warshall?

Pozostało 580 znaków

2006-11-09 00:00
0

niewiem czy Cie dobrze rozumiemale jezeli tak to poszukaj w necie "problemu komiwojazera" SSN mialem gdzieś to opisane ale nie moge znaleść pozdr


świadomość bycia kretynem nie pozwala sie rozwijać

Pozostało 580 znaków

2006-11-09 07:20
Pipkens
0
t4iglo napisał(a)

Niestety pojawia sie pewien problem. Maksymalna ilosc pamieci jaką moge wykorzytsac (ograniczenie dotyczy stosy, sterty itd.) to 64 Mb. W przypadku grafu o 20000 wierzchołków deklarując tablice dwuwymiarową int t[20000][20000] zużywam jakies 20000 20000 4 / (1024 * 1024) Mb co daje nam około ponad 1000 Mb [???]

Sąsiednie wierzchołki można trzymać też w liście! Zatem będzie tyle list co wierzchołków.

Pozostało 580 znaków

2006-11-09 09:34
_t4iglo
0

Jest to graf z wagami, a moim celem jest znalezienie najkrótszej drogi z wierzcholka 1 do wierzchołka N przechodzącego przez pierwsze 20 wierzchołków.

Sorry za nieścislości

Dodam jeszcze że graf jest cykliczny.

Pozostało 580 znaków

2006-11-09 10:20
0

Ładnie to tak oszukiwać? Na OI zadania należy rozwiązywać samodzielnie.

Pozostało 580 znaków

2006-11-09 12:23
_t4iglo
0

Nie oszukuje :)
Sam algorytm już napisałem, zastanwiam się tylko jak liczyć drogi w grafie między niesąsiednimi węzłami bez przekraczania limitu pamieci...

Zadanie na OI wyglada inaczej, ma dodatkowo wymagania co dokolejnosci poruszania sie w grafie itd. itd. Ja pytałem tutaj tylko o aspekt pamięci. Nie mam zamiaru publikować czyjegoś gotowego rozwiązania.

Pozostało 580 znaków

2006-11-09 13:16
nicka
0

Warshalla chyba nie da się wprost( albo i <ort>wogóle</ort>) zrobić na listach sąsiedztwa ale Dijkstre tak, jeżeli graf ma wagi ujemne to należy go odpowiednio przerobić - poszukaj w internecie. Powiem tylko że metoda typu dodanie do każdej wagi pewnej liczby X aby wszystkie były dodatnie nie zadziała i trzeba poszukać ;)
Dijkstra ma złożoność taką że powinna szybko przerobić podany przez Ciebie rozmiar danych

Pozostało 580 znaków

2006-11-11 22:06
0

Ludzie, bez "czitowania", to jest test Waszych umiejętności, a nie naszych. W koszu powinno wylądować bez gadania.


Pozostało 580 znaków

2006-11-12 09:39
nicka
0

no właśnie - umiejętnoście, a nie wiedzy!! niektórzy mają w szkole nauczycieli co tylko popatrzą na zadania z oi i <ort>odrazu</ort> to co sie może przydać przerabiają na lekcjach, a inni uczniowie muszą uczyć się sami i szperać po książkach i w internecie.

Pozostało 580 znaków

2006-11-14 16:05
reejettie
0

Zobaczymy wasze umiejetnosci w 2gim etapie panowie "programisci" [rotfl] , zycze szczescia w zadaniach ... "WTF bez googli?" [diabel]

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0