Witam, mam takie zadanie dostaje do 500 000 punktów na płaszczyźnie xi,yi gdzie xi i yi może być z przedziału -107 do 107 i muszę znaleźć trójkąt o najmniejszym obwodzie. Czy ma ktoś jakiś pomysł? zależy mi na czasie wykonania no i oczywiście pamięci ponieważ mam jej tylko 128mb, wiec jakiś brute force odpada.
0
0
Ja bym spróbował tak:
- przyjąć minimalny_obwód jako +nieskończoność
- dla punktu wyznaczyć jego najbliższego sąsiada - temat szeroko opisany w literaturze (nearest neighbor search algorithm), trzeba by dobrać jakąś implementację ale chyba nawet linear search zda egzamin.
- dla tak wyznaczonej pary (punkt i najbliższy sąsiad) jeżeli odległość między punktami tworzącymi parę jest mniejsza niż minimalny_obwód wyznaczyć punkt środkowy.
- dla tak wyznaczonego punktu znaleźć najbliższy punkt (nie będący żadnym z powyższych).
- dla tak wyznaczonej trójki (punkt, najbliższy sąsiad, punkt najbliższy środkowej) obliczyć obwód. Jeżeli jest mniejszy niż aktualny obwód to zapisać go jako minimalny_obwód.
- Powtórzyć dla każdego punktu. Ostatecznie zmienna minimalny_obwód będzie równa najmniejszemu możliwemu obwodowi.
Cała trudność sprowadza się do wybrania efektywnego algorytmu znajdowania najbliższego sąsiada.
0
@dymul, jeśli słowo trójkąt ma znaczenie potoczne - trzy punkty wyznaczają trójkąt <==> gdy nie są współliniowe - to twój algorytm nie zadziała.
Dane punkty leżą na prostych o równaniach y=0, y=2, y=4,.... Na każdej takiej prostej prostej leżą trzy punkty o współrzędnych x 0, 1/2 i 1. Każda trójka punktów postaci (punkt, najbliższy sąsiad, punkt najbliższy punktowi środkowemu) będzie wyznaczała trójkąt "zdegenerowany" (o współliniowych wierzchołkach).
0
Co racja, to racja, trójkątów zdegenerowanych nie uwzględniłem w algorytmie ale dodać takie obostrzenie jest łatwo i to bez pogarszania złożoności. Chodziło mi bardziej o to aby dać autorowi wątku punkt zaczepienia. I w tym miejscu nasuwają mi się dwa pytania:
- Algorytmy to nie jest moja specjalność, ten wpadł mi do głowy tak po prostu - na logikę wydaje się być poprawny ale czy dałoby się jakoś udowodnić poprawność tego algorytmu?
#Jaki algorytm znajdowania najbliższego sąsiada byście zastosowali w tym przypadku?
0
Pewnie wystarczy zrobić z tego sieć, tz. znaleźć minimalne otoczenie
dla każdego punktu i połączyć te punkty... chyba dwa najbliższe inne punkty niewspółliniowe.
Potem wyliczamy już jedynie te rozłączne trójkąty, znaczy takie bez punktów w środku.
Tym sposobem zredukujemy liczbę trójkątów chyba do rzędu n zaledwie,
no a wszystkich kombinacji trójek jest coś w stylu: n(n-1)(n-2)/6 == n^3, czyli aż o dwa rzędy więcej.