Cześć wszystkim.
Muszę napisać program (c#) który będzie znajdował najkrótszą ścieżkę ( i rysował ją na schematycznej mapie) między wybranymi miastami. W tym celu zrobiłem 2 tabele w sql , w jednej posiadam nazwy miast, nr id oraz ich współrzędne, w drugiej natomiast zawarłem połączenia między miastami : nr idmiasta1, nr idmiasta 2 oraz odległość. Nie wiem niestety jak się zabrać za obliczenie tejże trasy między nimi, jakiego algorytmu użyć (Doradzono mi algorytm Dantziga , niestety materiały jakie do niego dostałem są dla mnie czarną magią , mogę użyć innego). Oczywiście jest to jakby graf :P gdzie wierzchołkami są miasta a wagami odległości. Na razie doszedłem do tego że przy wyborze miasta startowego i docelowego program pobierze mi ich id oraz współrzędne. Niestety nie wiem co dalej, byłbym wdzięczny gdyby ktoś doradził mi jakiś odpowiedni algorytm, który byłby w miarę przystępnie opisany bądź jeżeli ktoś potrafiłby napisać mi schemat krokowy co powinienem dalej zrobić.
Jeżeli chodzi o rysowanie trasy to wydaje mi się że taki mechanizm mógłby zadziałać mianowicie pkt ( miasta) które wchodzą w skład trasy przechować w tablicy ( np po numerach id) a potem po prostu rysować linię między kolenymi pkt zaczynając od miasta startowego.
Za herezje przepraszam, zaczynam dopiero przygodę z programowaniem :) I dziękuję za jakiekolwiek rady, uwagi i pomoc :)
Dijkstra.
Dzięki, krótko ale na temat :) wygląda na to że będzie najlepszy.
Nie, ale skoro chcesz to robić na bazie danych to jednak ...
Najlepiej to by było użyć jakiejś przestrzennej bazy danych -> http://en.wikipedia.org/wiki/Spatial_database
Sporo standardowych baz ma wsparcie do takich celów i warto z niego skorzystać a nie wymyślać koło na nowo ;)
Myślę że zwykłe bazy danych mi wystarczą do tego programu :P
Wybrałem algorytm Dijkstry, starałem się go najpierw w miarę zrozumieć zanim zacznę pisać kod by się potem nie poplątać ,ale mam kilka niejasności.
Przedstawię mój "schemat postępowania":
- tworzę tablicę w której przechowuję wszystkie miasta ( nr ID miast z bazy danych) - to są moje wierzchołki.
2.tworzę drugą tablicę w której będę przechowywał wybrane miasta.
3.Wybieram miasto początkowe - jego id zostaje usunięte z 1 tablicy, ląduje w 2 , droga ustawiona na 0, do zmiennej IdOstatnioDodane przypisuję IdPoczątkowego.
4.Szukam następników, czyli z drugiej bazy danych ( gdzie znajdują się odległości miedzy poszczególnymi miastami ) pobieram miasta których IdMiasta1= idOstatnioDodane, szukam wśród nich najkrótszej odległości. Jak już znajdę to do IdOstatnioDodane wpisuję IdMiasta2 , zostaje ono usunięte z 1 tablicy, dodane do 2 tablicy, droga+=odległość;
5.mając nowe IdOstatnioDodane znowu wyszukuję jego następników , znowu wybieram najkrótszą drogę i powtarzam cały schemat.
i tutaj mam problem bo nie wiem co mam zrobić w momencie gdy dojdę do miasta które jest moim miastem końcowym ?
Mam dodać to miasto do 2 tablicy i zakończyć działanie "szuknia" , czy mam go ciągnąć do momentu aż 1 tablica będzie pusta?
Próbowałem rozrysować sobie pewną ścieżkę wg tego schematu i danych w tablicach, gdy zakonczyłem "papierową" kompilację w momencie gdy doszedłem do miasta końcowego to owszem, mogłem wyznaczyć drogę z miasta początkowego do końcowego wg miast które miałem w tablicy 2 ale nie była ona najkrótszą.
o_O ? To co opisałeś to jakaś dziwna implementacja algorytmu zachłannego, który wcale nie zwróci ci ścieżki najkrótszej.
Podstawowa zasada algorytmów zachłannych jest taka, że algorytmy te działają tylko dla problemów z własnością optymalnej podstruktury. To znaczy, że takie algorytmy są optymalne tylko dla problemów, w których rozwiązanie optymalne jest złożeniem optymalnych rozwiązań podproblemów. W twoim przypadku wcale tak nie jest, a przynajmniej niekoniecznie.
To co opisałeś nie ma nic wspólnego z algorytmem Dijkstry, który opiera się o relaksacje wierzchołków grafu. Może spróbuj najpierw z algorytmem Bellmana-Forda? To jest generalnie ta sama idea co Dijkstra, ale nie wykorzystuje się tam pewnej sprytnej optymalizacji. Bellman-Ford to jest algorytm na kilka linijek raptem.
Cześć, udało mi się ogarnąć algorytm , wszystko pięknie działa , ścieżka się rysuje. mam niestety kolejny problem.
chciałbym wyświetlić teraz wszystkie odległości jakie mam do pokonania na trasie.
z racji tego że posiadam listę obiektów gdzie każdy ma wartośći takie jak from,to , weight chciałbym teraz wyszukać te odpowiednie.
robię to za pomocą
while (fromTo[f]>0)
{
List<Edge> oedlist = Edges.FindAll(oElement => oElement.From.Equals(fromTo[f]));
Edge oedgf =oedlist.Find(oed => oed.To == fromTo[f + 1]);
textBox1.Text += oedgf.Weight.ToString();
oedlist.Clear();
f++;
}
gdzie fromTo[0] to miasto z ktorego "jade", fromTo[1] to miasto do ktorego jadę itd. po uruchomieniu dostaje wprawdzie te odległości w textboxie ale wywala mi "Object reference not set to an instance of an object".
Jak mam sobie z tym poradzić ?
mógłbym oczywiście zrobić też zapytanie do bazy gdzie podawałbym te miasta i zwracana by była dana odległość ale wydaje mi się że skoro mam obiekt który posiada te dane to mógłbym go wykorzystać.
Wystarczy dodatkowa składowa przy węźle, oznaczająca skąd do niego dotarliśmy.
Za każdym razem jak zmieniasz odległość do węzła zmieniaj również pole skąd do niego dotarliśmy.
Po zakończeniu algorytmu będziesz mieć odwróconą trasę.
Aby tej trasy nawet nie odwracać to przy odpaleniu algorytmu szukasz do węzła docelowego do węzła startowego.