Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #27682 > unrolled thread

Szukam algorytmu

Started byAdam Klobukowski <adamklobukowski@gmail.com>
First post2015-10-19 23:20 -0700
Last post2015-10-20 02:47 -0700
Articles 4 — 3 participants

Back to article view | Back to pl.comp.programming

Contents

  Szukam algorytmu Adam Klobukowski <adamklobukowski@gmail.com> - 2015-10-19 23:20 -0700
    Re: Szukam algorytmu Wojciech Muła <wojtek.mula@gmail.com> - 2015-10-20 00:52 -0700
      Re: Szukam algorytmu Adam Klobukowski <adamklobukowski@gmail.com> - 2015-10-20 01:03 -0700
    Re: Szukam algorytmu "M.M." <mmarszik@gmail.com> - 2015-10-20 02:47 -0700

#27682 — Szukam algorytmu

FromAdam Klobukowski <adamklobukowski@gmail.com>
Date2015-10-19 23:20 -0700
SubjectSzukam algorytmu
Message-ID<aeb5bb31-ecfb-49f6-9eb4-8b9f5477c021@googlegroups.com>
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

[toc] | [next] | [standalone]

#27683

FromWojciech Muła <wojtek.mula@gmail.com>
Date2015-10-20 00:52 -0700
Message-ID<2c2bacd4-068c-4010-81aa-11a1844092d5@googlegroups.com>
In reply to#27682
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.

[toc] | [prev] | [next] | [standalone]

#27684

FromAdam Klobukowski <adamklobukowski@gmail.com>
Date2015-10-20 01:03 -0700
Message-ID<898ceeb8-f4c1-4261-9f9f-698e87f07744@googlegroups.com>
In reply to#27683
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

[toc] | [prev] | [next] | [standalone]

#27685

From"M.M." <mmarszik@gmail.com>
Date2015-10-20 02:47 -0700
Message-ID<8efc2c75-78d6-42e5-b3d2-30a849cbdb0c@googlegroups.com>
In reply to#27682
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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web