[PHP] alogorytm Opcje

[Taifun]

Witam,
poszukuję pomysłu na algorytm, który oblicza możliwie jak najkrótszą trasę. Np. mieszkam w Krakowie i chcę coś załatwić. Łączę się z bazą i sprawdzam pobliskie miasta oczywiście razem z Krakowem i podaje możliwie najbliższą miejscowość gdzie to coś można załatwić.

[korro]

Witam.

Mój pomysł jest taki:
1. rozwiązujesz Kraków na koordynaty (długość i szerokość geograficzną) - reverse geocoding
2. w bazie masz miasta i ich koordynaty
3. obliczasz odległość między miejscem z punku 1 i miastami w bazie
4. sortujesz asc i masz wynik.

Pozdrawiam.

Ten post edytował korro 5.05.2009, 20:59:16

[marcio]

Nie znam sie na algorytmach ale pamietam klase bim2 ktora napisal do swojej gry moze pomoze rozwiazac twoj problem: http://forum.php.pl/index.php?showtopic=10...t=0&start=0

Ten post edytował marcio 5.05.2009, 21:45:18

[v1t4n]

Otóz to sie zwie problem komiwojażera. Nie ma rozwiązania idealnego ale pełno jest tego na google.

[nu_moon]

Witam.

Mój pomysł jest taki:
1. rozwiązujesz Kraków na koordynaty (długość i szerokość geograficzną) - reverse geocoding
2. w bazie masz miasta i ich koordynaty
3. obliczasz odległość między miejscem z punku 1 i miastami w bazie
4. sortujesz asc i masz wynik.

Pozdrawiam.

Twój pomysł ma jedną wadę - jeśli obliczę odległość między miastami w bazie, pierwszy i tak będzie wynik Kraków - dane miasto i nie będziesz miał trasy, a jedynie odległość. Żeby zbudować tego typu algorytm musisz jakoś rozwiązać ten problem.

Otóz to sie zwie problem komiwojażera. Nie ma rozwiązania idealnego ale pełno jest tego na google.

Nie do końca, problem komiwojażera dotyczy sytuacji gdzie mamy siatkę miast i musimy połączyć wszystkie miasta.
Różnica w problemie komiwojażera polega na tym że tam masz podaną siatkę odległości z miasta a i b
http://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera

Klasycznie rozwiązanie tego problemu dla tylko 2 punktów zawsze da ci warość z tabeli ( klasyczny problem komiwojarzera rozpatruje trasę zaczynającą się w danym punkcie i kończącą się w tym samym a trasa to suma losowych przebiegów po wszystkich miastach)


Moja koncepcja jest generlanie podobna (btw. Poczytaj o algorytmach genetycznych. ):



W skrócie można to opisać tak.
Potrzebujesz dwuwymiarową siatkę układu współrzędnych gdzie będziesz umieszczał koordynaty miast.
Wartości które podasz muszą być w odpowiedniej skali, tak by wyniki był w miarę dokładny.

Możesz np. za punkt odniesienia obrać np. lewy górny róg kwadratu w którym mieści się mapa kraju, bądź użyć szerokości / długości geograficzną i zapisywać odległości w km od tego punktu jako koordynaty miasta jako x i y wyrażone w km (punkt przecięcia).

Jeśli zdecydujesz się na współrzędne geograficzne, będziesz musiał mieć naprawdę dokładne wyniki (pewnie sekundy to zamało).
Musisz też obliczyć ile jedna sekunda np. w linii prostej ma kilometrów....

Odległość między 2 miastami obliczysz z twierdzenia pitagorasa.

Teraz puszczasz możliwe dużą liczbę losowych przebiegów po miastach na zasadzie losowo wybranych kierunków i wybierasz najoptymalnieszją trasę ( najkrótsza suma przekątnych ). Problem jest o tyle skomplikowany że nie bardzo wiadomo czy między miastem A i B jest właściwe połączenie drogowe więc kierunek wyznaczony przez algorytm będzie bardzo przybliżony.

Żeby uniknąć problemu o jakim wspomniałem na początku można by np (nie komplikując struktury danych), przyjąć że maksymalny krok to np.1/20 odległości w linii prostej.

Przykład:

Szukam trasy z Katowic do Sopotu.
Na podstawie współrzędnych obliczam że jest to ok 650km w linii prostej.
Stosuje dokładość 1/20 czyli maksymalny promień poszukiwań kolejnego miasta to ok 32 km/2 (zaczynamy w krakowie, promień okręgu od miejsca docelowego czyli 17 km w dowolną stronę od punktu w którym jesteśmy itp itd.).

Algorytm można zoptymalizować stosując wagi, tzn wyznaczamy mniej więcej kierunek w jakim trzeba się poruszać i staramy się częściej losować odpowednie koordynaty. Jako optymalizację można np. przerywać przeszukiwanie drogi która już daje wynik większy niż najmniejszy znaleziony albo przekracza o xx% odległość w linii prostej itp itd. możliwości jest sporo...

Z listy przebiegów wybieramy najmniejszy który dotarł do celu (bo prawdopodobnie większość nie dotrze wcale).

O skuteczności działania algorytmu będzie decydować przyjęta dokładność i ilość przebiegów.
Mam nadzieję że pomogłem bo problem rozwiązałęm jedynie teoretycznie, choć kiedyś miałem pomysł jak napisać coś podobnego

Ten post edytował nu_moon 5.05.2009, 23:23:56

[korro]

Twój pomysł ma jedną wadę - jeśli obliczę odległość między miastami w bazie, pierwszy i tak będzie wynik Kraków - dane miasto i nie będziesz miał trasy, a jedynie odległość. Żeby zbudować tego typu algorytm musisz jakoś rozwiązać ten problem.

Kolejny krok to wrzucenie punktów na mapę google, a google samo wyznaczy trasę.
To moja koncepcja.

[Zyx]

Żadna siatka nie jest potrzebna. Zagadnienie wyszukiwania najkrótszej drogi na siatce to szczególny przypadek wyszukiwania najkrótszej ścieżki w grafie. W przypadku siatki jest on nieskierowany i bez wag, więc cały algorytm to najzwyklejsze w świecie przeglądanie grafu wszerz (znane jako algorytm BFS). Zamiast tego, możesz stworzyć sobie graf połączeń pokazujący, skąd można dotrzeć dokąd, połączeniom przypisać wagę oznaczającą czas/odległość. Wtedy masz do dyspozycji dwa algorytmy:

Algorytm Dijkstry
Algorytm Floyda-Warshalla - znajduje ścieżki między wszystkimi parami miast.

A problemu komiwojażera tu nie mieszajcie, bo to jest zupełnie inny rodzaj problemu .