Dzień dobry,
Mam do napisanie algorytm, który oblicza najkrótszą odległość pomiędzy dwoma punktami na powierzchni kuli. Algorytm ten ma wykorzystywać metodę dziel i zwyciężaj, jednak nie do końca wiem jak mam to zrobić. Obliczam te odległości i pojawiają się schody, bo nie wiem jak powinienem je przechowywać (może jakieś drzewo dla każdego punktu przechowujące odległości do pozostałych?). Może jest ktoś, kto ma pomysł jak to zrobić? Będę wdzięczny za jakąkolwiek pomoc.
Żeby to policzyć potrzeba tylko paru funkcji trygonometrycznych , to po co tu dziel i zwyciężaj.
Takie są wymagania w treści zadania, żeby wykorzystać dziel i zwyciężaj. Tylko dalej nie wiem jak najlepiej przechowywać te ortodromy.
Ogólnie chyba tak musisz to robić:
odległość pomiędzy punktami A i B: d(A, B) -> min;
takie coś znaczy tyle że dla dowolnego punktu C na trasie pomiędzy A i B:
d(A,B) = d(A, C) + d(C, B) -> min,
ale wtedy automatycznie: d(C, B) -> min, co jest chyba oczywiste?
Jak jest opisane położenie punktów A i B? Jeśli przez podanie szerokości i długości geograficznej, to można tak: wyznaczmy środek łuku AB - oznaczamy go S. Wtedy d(A,B) = d(A,S) + d(S,B). Kontynuujemy dzielenie na pól tak długo aż odległości między końcami łuku staną się "bardzo małe". Wtedy zamiast liczyć długość łuku liczymy długość odcinka. Algorytm mało wydajny, ale stosuje zasadę dziel i zwyciężaj.
Zacytowana w ostatnim poście treść zadania nie ma nic wspólnego z problemem, który opisałeś w pierwszym poście.
Mój błąd. W pierwszym poście opisałem ten problem zbyt ogólnikowo, zamiast od razu wstawić treść zadania. Proszę o wybaczenie.
Przepraszam za spam, ale chciałem być zauważony. Wie ktoś jak rozwiązać ten problem (nie z pierwszego postu, ale ten zacytowany) bo nadal się z tym męczę. Na moje nieszczęście nie można tu zastosować brute force'a i nie wiem jak to prawidłowo rozwiązać.
Tutaj http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12 opisany jest algorytm typu dziel i zwyciężaj szukania pary najbliższych punktów na płaszczyźnie. Po zmianie wzoru na odległość, powinien zadziałać dla punktów na sferze.
To zadanie jest dla studentów 2 roku z algorytmiki. Bardzo nie ładnie drogi studencie
UMCS napisał(a):
To zadanie jest dla studentów 2 roku z algorytmiki. Bardzo nie ładnie drogi studencie
I co z tego? Nikt tu nikomu zadania nie pisze tylko gość się pyta o porady.