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

do góry

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?

Może k-means? Jakaś jego modyfikacja, skoro X musi być podzbiorem N.

w.

do góry

W dniu wtorek, 20 października 2015 09:52:57 UTC+2 użytkownik Wojciech Muła napisał:
> 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?
>
> Może k-means? Jakaś jego modyfikacja, skoro X musi być podzbiorem N.
>
> w.

X nie musi byc podzbiorem N, tylko maja wspólną przestrzeń.

AdamK

do góry

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

do góry