Szukanie najkrótszej drogi w grafie Opcje

[Shlizer]

Witam.
Mam pewien problem ze skryptem PHP, który chcę wykonać od kilku dni. Czuję się trochę jak ciemna masa, bo problem nie wydaje się skomplikowany, a mimo to nie mam pojęcia jak się do niego zabrać.

Ale do rzeczy.
Skrypt ma generować najkrótszą możliwą drogę w grafie na podstawie danych wejściowych - węzła początkowego i końcowego. Węzły są wrzucone do bazy danych i posiadają swój unikalny ID oraz opis. Istnieje też druga tabela opisująca ich relacje (węzeł1, węzeł2, które są połączone oraz ich wagę). Mam funkcję Szukaj(int,int), która przyjmuje wartości: ID źródła i ID ujścia.
Wiem, że dobrym sposobem będzie przeszukać kolejno najbliższe węzły źródła, zliczając ich poszczególne wagi, potem ich sąsiedztwo itd. aż trafimy na ujście. Następnie zebrać wszystkie trasy i wybrać tą o najmniejszej wadze. Jednak gdy przychodzi czas, żeby napisać kod, bladego pojęcia nie mam jak to zrobić.

Może mógłby ktoś mnie jakoś nakierować w jaki sposób wywoływać funkcje rekurencyjnie, jak przechowywać i tworzyć trasy, czy coś? =/
Może ktoś ma lepszy sposób na reprezentację tych danych, bo prawdę mówiąc za każdym razem trzeba sprawdzać, czy w połączeniu węzeł źródłowy jest reprezentowany jako węzeł1, czy węzeł2 w bazie..

Jeszcze jedno: skrypt też można zrobić na klasach, gdzie dane są po prostu wpisane w tablice / struktury danych, a ponieważ nie będą zmieniane można je wpisać na sztywno.
Dodatkowo jest taki problem, że nie wszystkie węzły są powiązane ze sobą na zasadzie jeden do jednego. Czasem jest to 'podróż w jedną stronę', ale wydaje mi się, że jak poradzę sobie z powyższym problemem to już z tym zagadnieniem nie powinno być kłopotu.

Jak są jakieś niejasności to chętnie odpowiem.

[golaod]

Sam sobie odpowiadasz na pytania:
google: algorytm prima i kruskala, minimalne drzewo rozpinające.

[erix]

Skrypt ma generować najkrótszą możliwą drogę w grafie na podstawie danych wejściowych - węzła początkowego i końcowego. Węzły są wrzucone do bazy danych i posiadają swój unikalny ID oraz opis. Istnieje też druga tabela opisująca ich relacje (węzeł1, węzeł2, które są połączone oraz ich wagę). Mam funkcję Szukaj(int,int), która przyjmuje wartości: ID źródła i ID ujścia.
Wiem, że dobrym sposobem będzie przeszukać kolejno najbliższe węzły źródła, zliczając ich poszczególne wagi, potem ich sąsiedztwo itd. aż trafimy na ujście. Następnie zebrać wszystkie trasy i wybrać tą o najmniejszej wadze. Jednak gdy przychodzi czas, żeby napisać kod, bladego pojęcia nie mam jak to zrobić.

O ile pamiętam, to było już coś takiego na forum.

Chyba nawet któryś użytkownik gotową klasę zmajstrował.

[dr_bonzo]

To bl raczej algorytm A*/ do szukania drogi na "mapie kwadratow"

[Shlizer]

Sam sobie odpowiadasz na pytania:
google: algorytm prima i kruskala, minimalne drzewo rozpinające.

Wiem czym jest algorytm Dijkstry. Problem nie polega na wiedzy teoretycznej, ale na jej implementacji. Nie mam bladego pojęcia jak przedstawić niektóre rzeczy w kodzie (niektóre zrozumiałem po skryptach z innych języków). W Internecie przegrzebałem całą masę stron i nigdzie nie ma przykładu tego algorytmu dla php, dlatego pytam.
Tak swoją drogą - jak w php oznacza się nieskończoność? Rozumiem, że wystarczy bardzo duża liczba?

Edit: swoją drogą wierzchołki grafu nie znajdują się w żadnym układzie współrzędnych. Ich wagi to nie zawsze ich odległość, ale raczej koszt transportu i choć faktycznie im dalsza droga tym drożej, nie rośnie to tak, jak literki na osiach.

To bl raczej algorytm A*/ do szukania drogi na "mapie kwadratow"

Widziałem ten temat i to z lekka inne zagadnienie w mojej opinii.

Ten post edytował Shlizer 20.08.2009, 21:54:28

[ayeo]

Witam!

Jeśli mówisz o tzw Problemie Komiwojażera to pozostaje rekurencja. Matematycznie podobno nierozwiązywalny problem.Jest przewidziana ogromna nagroda dla osoby, która rozwiązałaby ten problem. CO do samej implementacji rekurencyjnej to wiedząc czego szukasz na pewno znajdziesz.

Pozdrawiam!

[thek]

Jeśli chodzi o problem drogi, to powiem tylko tyle, że komiwojażera rozwiązując metodami stricte matematycznymi trudno dobrze i szybko rozwiązać. Chyba najlepszą mi znaną metoda jest zdefiniowanie sobie "funkcji oceny" i zaprzęgnięcie do tego samodzielnie napisanego algorytmu genetycznego. Ja w ten sposób rozwiązywałem problem skoczka szachowego odwiedzającego wszystkie pola szachownicy. Dodam tylko, że istnieje na niej takie pole (bodajże C4), z którego start nie ma rozwiązania metodami iteracyjnymi. Zadanie uruchomione nawet na klastrze tydzień by chodziło i nie dało by prawidłowego wyniku. Problemem przy stosowaniu tych algorytmów jest dobre zdefiniowanie "funkcji oceny" oraz "naprawiania genomu". Nie wspominając już o tym, że są one bardzo zachłanne.

EDIT: Bym zapomniał dodać, że algorytmy genetyczne podają zazwyczaj rozwiązania optymalne, ale niekoniecznie idealne. Innymi słowy w matematycznym zadaniu podały by wynik oszacowany, ale niekoniecznie prawidłowy. Stąd właśnie są najczęściej stosowane do zadań optymalizacyjnych, a nie obliczeniowych.

Ten post edytował thek 21.08.2009, 23:01:31

[Shlizer]

Nie do końca chodzi o ten problem.
Tutaj mam się dostać z punktu A do punktu B (trasa nie jest istotna - nie muszę przejść każdym polem) i zebrać jak najmniej punktów (ceny transportu w to miejsce).
Hm.. no cóż.. posiedzę jeszcze trochę nad tym to coś wykombinuję..

[cojack]

O Boże, strzel mnie piorunem, kolego kup sobie http://helion.pl/ksiazki/ALGO3.htm a jak nie to czytaj o http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

@Btw co Ty na wsizie w rzeszowie studiujesz?

Ten post edytował cojack 23.08.2009, 00:24:42

[Shlizer]

Książkę mam (!) + dwie książki o algorytmach Sysły. O algorytmie Dijkstry wiem. Jakby szanowny kolega poczytał temat to wiedziałby, że nie chodzi o teorię (kolega podał książkę, w którym o algorytmie jest jedna strona - przykład jest ale nijak nie ma się on do rozwiązań, które tu opisałem), ale o praktykę, czyli technicznie - co, jak..
swoją drogą radzę sobie jakoś powoli.. co prawda wyliczanie może zarzynać serwer, ale co tam.. =p

[ucho]

http://pl.php.net/manual/en/spl.datastructures.php
Bez tego mógłby być pewien problem - to znaczy na tablicach też działa ale wolniej niż by mogło. Nie napisałeś cu takiego w algorytmie Dijkstry sprawia Ci problem. Nie wiem także skąd pomysł że potrzebna do tego jest rekurencja

[golaod]

Wszyscy mieszacie jakby to nie wiadomo co strasznego było:
Tworzysz Shlizer( dla algorytmu kruskala albo prima ) macierz sąsiedztwa:
A B C D
A -1 1 -1 -1
B 1 -1 3 2
C -1 3 -1 2
D -1 2 2 -1

(jak się wkradł błąd co do wag no to nie moja wina na szybko pisałem (IMG:style_emoticons/default/tongue.gif) )

I jak masz taką tablicę dwu wymiarową to zaznaczasz sobie wierzchołek startowy czytaj czy A czy B czy C czy D i tworzysz zbiór uporządkowany sąsiedztwa( od najmniejszej wagi ) następnie łączysz wierzchołek startowy z tym o najmniejszej wadze a do zbioru dodajesz sąsiedztwa nowego wierzchołka usuwając przy tym ze zbioru ten który się właśnie połączyło. Itd itd przy okazji sprawdzając czy węzły nie kierują się do tego samego wierzchołka.
na koniec funkcja array_sum na utworzonej tablicy drzewa spinającego i zadanie gotowe.

Ten post edytował golaod 24.08.2009, 12:30:46

[cojack]

Shlizer jak masz książkę to: 239 strona, algorytm Floyda-Warshalla.

[Shlizer]

Nie wiem także skąd pomysł że potrzebna do tego jest rekurencja

Ja nie pisałem, że jest potrzebna. Chociaż może być pomocna, wydaje mi się, że i pętle powinny starczyć.
Dzięki golaod i cojack. Postaram się to przerobić na php i zobaczę co z tego wyjdzie.