Re: Szukam algorytmu - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › Szukam algorytmu › Re: Szukam algorytmu

X-Received: by 10.140.104.43 with SMTP id z40mr19458qge.15.1445327574487; Tue, 20 Oct
2015 00:52:54 -0700 (PDT)
X-Received: by 10.140.104.43 with SMTP id z40mr19458qge.15.1445327574487; Tue, 20 Oct
2015 00:52:54 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news.glorb.com!
kq10no23853099igb.0!news-out.google.com!j14ni264qge.0!nntp.google.com!c107no267
080qgd.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Tue, 20 Oct 2015 00:52:54 -0700 (PDT)
In-Reply-To: <a...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=195.66.98.6;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 195.66.98.6
References: <a...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <2...@g...com>
Subject: Re: Szukam algorytmu
From: Wojciech Muła <w...@g...com>
Injection-Date: Tue, 20 Oct 2015 07:52:54 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:208487
[ ukryj nagłówki ]
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.