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.

[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