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ć.

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.

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

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

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.



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

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

Ż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 .