[Delphi]Para najbliżej leżących siebie punktów w układzie

0

W jaki sposób można sprawdzić jaka jest najmniejsza odległość między dwoma z pośród wileu punktów, których współrzędne zawiera tablica w(w[i,1]=x, w[i,2]=y gdzie i <1,10000>). Znam [URL=http://upload.wikimedia.org/math/4/e/2/4e2ba8fc772df25a2c56ed7ae04b8e68.png]wzór na wyznaczanie odległości między dwoma punktami[/URL], ale w jaki sposób sprawdzić wszystkie kombinacje (skonstruować pętle) i wybrać parę punktów najbliżej siebie leżących?

0

robisz petle która po kolei dla kazdego indeksu tablicy liczy odległości i zapisuje to do innej tablicy: odległość i indeksy z tej wczesniejszej (? ale brzmi). Potem przeszukujesz powstałą tablice i znajdujesz najmniejszą odległość i masz wtedy indeksy pkt najblizej siebie lezących. Teraz to juz tylko znaleźć je w tej pierwszej tablicy

0

no zasadniczo musisz sprawdzic wszystkie kombinacje:/

ale moznaby zrobic cos takiego:

for i := 1 to 10000 do begin
  for j := 1 to 10000 do begin
    if (abs(tab[i,1]-tab[j,1]) < minOdleglosc) OR (abs(tab[i,2]-tab[j,2]) < minOdleglosc) then begin
      if i <> j then begin
        odl :=  pow(x1-x2,2)+pow(y1-y2,2);
        if odl < min then begin 
          min := odl
          minOdleglosc := sqrt(min);
          X1 := tab[i,1];
          Y1 := tab[i,2];
          X2 := tab[i,1];
          Y2 := tab[i,2];
        end;
      end;
    end;
  end;
end; 

spowoduje to pewne ograniczenie ilosci potegowan i pierwiastkowan
trzeba sobie teraz odpowiedziec na bardzo wazne pytanie

Co chcialbys robic w zyciu, i zaczac to robic! //żarcik:P

czy koszt sprawdzania tego warunku jest mniejszy od zaoszczedzonego kosztu potegowan i pierwiastkowan
(mi sie wydaje ze tak)

[!!!]
Pomysl przedstawiony przez SebaZ jest nie najlepszy gdyz wymaga tych samych (jesli nie wiekszych) obliczen co moj + koszt wyszukania minimalnej wartosci w tablicy + dodatkowej pamieci na nowa tablice o wymiarach 10000 x 10000!! [!!!]

0

if (abs(tab[i,1]-tab[j,1]) < min) and (abs(tab[i,2]-tab[j,2]) < min) then begin

Jonny jeśli widzę dobrze to robisz poważny matematyczny błąd.
zakąłdasz że odległość pomiędzy punktami bedzie najmniejsza, a dokładnie wyrażenie
a2+b2 wtedy gdy: a<amin i b<bmin co nie jest zgodne z prawdą.
Weżmu punkty (1,1000) i (1,1001) mamy więc warunek w którym odległości na osiach to 0 i 1000, czyli odległość to sqrt(010+10001000) =1000.
Bierzemy drugą parę (1,1) i (4,5) wówczas odległości na osiach to 3 i 4, czyli sqrt(33+44)=5
Wg. Twojego algorytmu nawet nie dojdzie do obliczeń dla drugiego punktu.

Co do rozwiązania problemu:
Nie musisz robić drugiej tablicy, wystarczy jak zapamiętasz najniższy wynik i miejsce odpowiednich punktów w tablicy. Pętlę robićz od elemntu pierwszego do ostatniego w tablicy dla pobrania pierwszego elementu pary, a wewnątrz niej pętlę od elementu pierwszego+1 do ostatniego w tablicy dla pobrania elementu drugiego. Zaczynasz od ustawienai odległości na ujemną i zaczynasz sprawdzanie czy pierwsza odległość jest wieksza (musi być przynajmniej zerem więc będzie), a następnei wpisujesz jej wynik i zapamiętujesz punkty. Bierzesz następną parę i porównujesz, zawsze z wartościąminimalną, jeśli bedzie mniejsza to ponownei zapisujesz, jak nie bierzesz następną i tak aż do skończenia par punktów.
Jonny ma rację, można to przyspieszyć:

  1. jeśli odległość wyniesie zero - to już mniejszej się nie da i przerywamy pętlę.
  2. warunkiem podobnym do tego Jonnego, ale jeśli obydwie odległości na osiach są większe od odpowiadających im dla odległości minimalnej, to możemy mieć pewność że odległość miedzy punktami będzie wieksza, ale tylko w tym przypadku.
0

if (abs(tab[i,1]-tab[j,1]) < min) and (abs(tab[i,2]-tab[j,2]) < min) then begin

Jonny jeśli widzę dobrze to robisz poważny matematyczny błąd.
zakąłdasz że odległość pomiędzy punktami bedzie najmniejsza, a dokładnie wyrażenie
a2+b2 wtedy gdy: a<amin i b<bmin co nie jest zgodne z prawdą.
Weżmu punkty (1,1000) i (1,1001) mamy więc warunek w którym odległości na osiach to 0 i 1000, czyli odległość to sqrt(010+10001000) =1000.
Bierzemy drugą parę (1,1) i (4,5) wówczas odległości na osiach to 3 i 4, czyli sqrt(33+44)=5
Wg. Twojego algorytmu nawet nie dojdzie do obliczeń dla drugiego punktu.

Co do rozwiązania problemu:
Nie musisz robić drugiej tablicy, wystarczy jak zapamiętasz najniższy wynik i miejsce odpowiednich punktów w tablicy. Pętlę robićz od elemntu pierwszego do ostatniego w tablicy dla pobrania pierwszego elementu pary, a wewnątrz niej pętlę od elementu pierwszego+1 do ostatniego w tablicy dla pobrania elementu drugiego. Zaczynasz od ustawienai odległości na ujemną i zaczynasz sprawdzanie czy pierwsza odległość jest wieksza (musi być przynajmniej zerem więc będzie), a następnei wpisujesz jej wynik i zapamiętujesz punkty. Bierzesz następną parę i porównujesz, zawsze z wartościąminimalną, jeśli bedzie mniejsza to ponownei zapisujesz, jak nie bierzesz następną i tak aż do skończenia par punktów.
Jonny ma rację, można to przyspieszyć:

  1. jeśli odległość wyniesie zero - to już mniejszej się nie da i przerywamy pętlę.
  2. warunkiem podobnym do tego Jonnego, ale jeśli obydwie odległości na osiach są większe od odpowiadających im dla odległości minimalnej, to możemy mieć pewność że odległość miedzy punktami będzie wieksza, ale tylko w tym przypadku.
0

Dzięki wszystkim za odpowiedzi czas zacząć działać coś z tym.

0
 wynik:= sqrt(sqr(tab[2,1] - tab[1,1]) + sqr(tab[2,2] - tab[1,2]));
  for i:=1 to 10000 do
  for j:=i+1 to 10000 do
    begin
    if (wynik > sqrt(sqr(tab[j,1] - tab[i,1]) + sqr(tab[j,2] - tab[i,2]))) then
    wynik:= sqrt(sqr(tab[2,1] - tab[1,1]) + sqr(tab[2,2] - tab[1,2]));
    end;
  writeln(wynik);

Doszedłem do takiego rozwiązania ale prgram nie działa ;-( Może wie ktoś dlaczego tak jest?

0

Bo w linijce przypisania nowego wyniku skopiowałeś linijkę poczatkową.

0

Poprawiłem tą linijkę i dalej występuje ten sam kłopot. Aplikacja po otwarciu zaraz się zamyka. Może operacje zajmują za dużo pamięci?

0

wprowadzilem drobne poprawki do mojego algorytmu
mianowicie:
zadziej liczy sie pierwiastek
i w warunku zamiast AND jest OR

w tym warunku, ktory Sir Daban zakwestionowal
chodzi o to aby roznica odleglosci na osiach miedzy punktami
byla mniejsza od wyznaczonej odleglosci minimalnej

poniewaz gdy mamy juz ustalone minimum dla
A=(0,0) B=(3,4) minOdleglosc = 5
nie ma sensu liczyc juz dla punktow
A=(0,0) B=(2,5) bo odleglosc na osi OY jest 5 czyil rowna minOdleglosc ale trzeba jeszcze dodac czesc z osi OX czyli wyjdzie 5,39....

Ogolnie bedzie to wygladalo tak ze sie sprawdza tylko te punkty B, ktore leza wewnatrza kwadratu opisanego na okregu o srodku w punkcie A i promieniu r=minOdleglosc

mysle ze moj algorytm jest dobry:D

0

zrob moze cos zeby czekal na koncu na nacisniecie dowolnego klawisza np

readln;

(sorki jesli juz to zrobiles)

0

Tak dla porządku: for i:=1 to n-1 do
for j:=i+1 to n do


Gdyby posortować tablicę (np. po X, wtedy pierwszy będzie ten pierwszy z lewej). 
Korzystając z pomysłu Johnego, można by wcześniej przerwać wewnętrzną pętlę.

Liczenie pierwiastków można pominąć, możemy przecież porównywać kwadraty odległości.
0

Dzięki za odpowiedź Johny_Morfina, wszystko działa jak należy :-) </delphi>

0

Johny, teraz zrozumiałem warunek i pomysł jest niezły, choć nadal mam watpliwości co do poczatku Twojego programu. Po pierwsze po co przeszukwiac wszystkie kombinajce, bo odległość pomiędzu punktami A i B jest równa odległości pomiedzy punktami B i A. Poza tym nie inicjujesz wartosci minimalnej na starcie programu.
Ja bym podzielił program na dwie częsci:

  1. Tą która po przeróbkach prezentujecie jako podstawową (ilość wykonań porównań w przyblizeniu (N-1)! )
  2. Warunki przyspieszajace i tutaj co tam kto zaimplementuje byle z głową:
  • przerwanei jeśli droga równa zero - mniejszej nie znajdziecie
  • warunek Johnnego: pominięcie jeśli choć jedna z długości na osiach jest większa od odleglosci minimalnej
  • mój warunek - pominięcie jeśli obydwie odleglosci na osiach są większe niż odpwiadające im wielkości dla odległości minimalnej
  • jak proponowano, w celu przyspieszenia obliczeń można zrezygnowac z liczenia pierwiastków zastępując suma kwadratów, a policzyć pierwiastek na końcu na wyniku
0

Johny, teraz zrozumiałem warunek i pomysł jest niezły, choć nadal mam watpliwości co do poczatku Twojego programu. Po pierwsze po co przeszukwiac wszystkie kombinajce, bo odległość pomiędzu punktami A i B jest równa odległości pomiedzy punktami B i A. Poza tym nie inicjujesz wartosci minimalnej na starcie programu.
Ja bym podzielił program na dwie częsci:

  1. Tą która po przeróbkach prezentujecie jako podstawową (ilość wykonań porównań w przyblizeniu (N-1)! )
  2. Warunki przyspieszajace i tutaj co tam kto zaimplementuje byle z głową:
  • przerwanei jeśli droga równa zero - mniejszej nie znajdziecie
  • warunek Johnnego: pominięcie jeśli choć jedna z długości na osiach jest większa od odleglosci minimalnej
  • mój warunek - pominięcie jeśli obydwie odleglosci na osiach są większe niż odpwiadające im wielkości dla odległości minimalnej
  • jak proponowano, w celu przyspieszenia obliczeń można zrezygnowac z liczenia pierwiastków zastępując suma kwadratów, a policzyć pierwiastek na końcu na wyniku
0

Co do rozwiązania problemu:
Nie musisz robić drugiej tablicy, wystarczy jak zapamiętasz najniższy wynik i miejsce odpowiednich punktów w tablicy.
fakt, to z rozpędu :) w koncu zawsze sie optymalizuje algorytmy :)
btw. co zajmie wiecej miejsca w pamięci:

  • tablica 3-poziomowa(?) - hehe chyba nie tak sie to okresla ale kazdy wie o co chodzi t[a,b,c] ;)
  • 3 zmienne zawierające współrzędne pkt oraz odległość
  • jedna zmienna, np. string gdzie wartości oddzielone sa jakoś od siebie a później wyciągane czymś w stylu explode() w php :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1