On Tuesday, October 20, 2015 at 8:20:23 AM UTC+2, Adam Klobukowski wrote:
> Szukam algorytmu na tak zdefiniowany problem:
>
> Mamy przestrzeń dyskretną, a w niej zbiór N punktów. W tej przestrzeni mamy wybrać
zbiór X punktów (wielkość zbioru X jest z góry założona, mniejsza od wielkości zbioru
N) w taki sposób, aby po przyporządkowaniu każdemu punktowi zbioru N jednego punktu
zbioru X, suma odległości pomiędzy tak przyporządkowanymi punktami była jak
najmniejsza.
>
> Zakładam że algorytm idealny będzie raczej zbyt wolny. Znacie jakieś dobre
przybliżenia tego typu problemu?
>
> AdamK

Ciekawe zadanie, by trzeba pomyśleć. Kilka rzeczy nie uściśliłeś, dlatego
najlepiej podać meta-kod najprostszego, naiwnego algorytmu. Nie wiadomo
np. czy gdy element trafia do X, to można do niego mierzyć odległość (bo
pozostaje nadal w N), czy z N wypada i nie można go ponownie użyć. Nie
wiem też czy do jednego elementu można mierzyć tylko raz odległość.

Na razie to co oczywiste:

1) Dla |X|=1 rozwiązaniem jest dowolny punkt z pary najbliższych
punktów w zbiorze N. Potem zachłannie można szukać drugiej pary.

2) Czas naiwnego algorytmu rośnie wykładniczo względem |X|.

3) Można zacząć od rozwiązania losowego lub zachłannego i zastosować
jakiś algorytm 1- lub 2-optymalny.


Pozdrawiam