GoldenLine
Zaloguj się

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Witam,
Mam problem natury naturalnej. Otóż próbuję znaleźć najbardziej optymalny algorytm do wyszukiwania najkrótszej ścieżki od pkt A do pkt B. Wagi ścieżek są takie same, można to sobie zobrazować jako macierz wypełnioną 0, 1 oraz A i B, gdzie 0 to jest przejście a 1 to przeszkoda. Oczywiście można by wykorzystać tutaj algorytm przeszukiwania wszerz by sprawdzić czy istnieje ścieżka, ale poszukuje czegoś bardziej złożonego by dodatkowo wygładzał ścieżkę (tzn nie chodził przy samych przeszkodach, zachowywał się bardziej naturalnie). Rozmiar macierzy nie ma tutaj znaczenia, oczywiście nie oczekuje cudów przy 1000 x 1000 < 1s ;)

Mam nadzieje że dość jasno wytłumaczyłem problem.

P.S. A* nie zdał egzaminu.
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Przemek Czekaj:
Otóż próbuję znaleźć najbardziej optymalny algorytm do wyszukiwania najkrótszej ścieżki od pkt A do pkt B.
Nie pamiętam już wcale tych różnych algorytmów grafowych, więc trochę pofantazjuję (jak piszę bzdury to proszę mnie powstrzymać ;)).

Wyobraźmy sobie, że w punkcie A wlewamy wodę. Woda pokonuje korytarze, czyli w każdym kroku pole już zatopione zalewa wodą tych swoich sąsiadów, na których nie ma przeszkody. Jeśli na trasie pojawi się zakręt to przepływ zwalnia, podobnie jeśli korytarz rozszerzy się - takie proste intuicje. W ten sposób woda szybciej przebędzie drogę wygładzoną, której szukasz. Algorytm oczywiście iterujemy aż zalejemy punkt B - wymaga to niestety pamiętania wszystkich przebywanych ścieżek.
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Przemek Czekaj:
czy istnieje ścieżka, ale poszukuje czegoś bardziej złożonego by dodatkowo wygładzał ścieżkę (tzn nie chodził przy samych
"wygładzał ścieżkę"?
przeszkodach, zachowywał się bardziej naturalnie).
"bardziej naturalnie"?
Mam nadzieje że dość jasno wytłumaczyłem problem.
Niestety nie :).
P.S. A* nie zdał egzaminu.
Czemu?

O algorytmie Dijkstry słyszałeś?Wit Jakuczun edytował(a) ten post dnia 27.09.11 o godzinie 20:44
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Wit Jakuczun:
O algorytmie Dijkstry słyszałeś?

Tak, zaimplementowałem go, niestety nie sprawdził się tak jakbym tego oczekiwał.

Poza tym, ten algorytm jest przeznaczony dla grafów które posiadają wagę pomiędzy wierzchołkami, w moim przypadku wagi są równe, także niepotrzebny nakład.
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Przemek Czekaj:
Wit Jakuczun:
O algorytmie Dijkstry słyszałeś?

Tak, zaimplementowałem go, niestety nie sprawdził się tak jakbym tego oczekiwał.
A czemu nie?
Poza tym, ten algorytm jest przeznaczony dla grafów które posiadają wagę pomiędzy wierzchołkami, w moim przypadku wagi są równe, także niepotrzebny nakład.
O jakim nakładzie mówisz? Ten graf jest także dla grafów z wagami
równymi.
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Przemek Czekaj:
P.S. A* nie zdał egzaminu.

No to już dużo szybszego nie znajdziesz. A* to taka Dijkstra z heurystykami. Z tego co widzę, opis Tomka to tak naprawdę opis przeszukiwania grafu wszerz. Dokładnie na tym pomyśle opiera się algorytm Dijkstry.

Dijsktrę zaimplementowałem kiedyś tutaj w PHP jako ćwiczenie:

http://amichalski.googlecode.com/files/dijkstra.php

(kod nie był optymalizowany ani specjalnie testowany, stanowi punkt wyjścia)

Sam algorytm to u mnie 40 linijek, w pseudokodzie zaś nie przekracza 15. Jeśli wagi nie mają znaczenia, to zapisujesz po prostu wszystkie wagi jako 1.

Mam wrażenie, że jeśli A* nie zdał egzaminu, to albo go źle zaimplementowałeś, albo musisz przeformułować problem, bo, jak sam stwierdziłeś, zupełnie słusznie, w algorytmice "cudów" nie ma i w przypadku macierzy 1000x1000 obliczeń trochę może być.Adam Michalski edytował(a) ten post dnia 01.10.11 o godzinie 01:52
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Coś z domeny gier:
http://bit.ly/4xFkEt
Link do wypowiedziLink

konto usunięte

Temat: Algorytm wyszukiwania najkrótszej ścieżki

Adam Michalski:
Przemek Czekaj:
P.S. A* nie zdał egzaminu.
Mam wrażenie, że jeśli A* nie zdał egzaminu, to albo go źle zaimplementowałeś, albo musisz przeformułować problem, bo, jak sam stwierdziłeś, zupełnie słusznie, w algorytmice "cudów" nie ma i w przypadku macierzy 1000x1000 obliczeń trochę może być.

Tu się zgodzę, znalazłem o wiele lepsze rozwiązanie tego algorytmu które działa bardzo wydajnie, błąd w implementacji. Dziękuje ;)
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj