-
X-Received: by 10.140.104.43 with SMTP id z40mr26795qge.15.1445334472303; Tue, 20 Oct
2015 02:47:52 -0700 (PDT)
X-Received: by 10.140.104.43 with SMTP id z40mr26795qge.15.1445334472303; Tue, 20 Oct
2015 02:47:52 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news.glorb.com!
m48no396670qgd.0!news-out.google.com!t36ni232qge.1!nntp.google.com!c107no291592
qgd.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Tue, 20 Oct 2015 02:47:52 -0700 (PDT)
In-Reply-To: <a...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.146.172;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 159.205.146.172
References: <a...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <8...@g...com>
Subject: Re: Szukam algorytmu
From: "M.M." <m...@g...com>
Injection-Date: Tue, 20 Oct 2015 09:47:52 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:208489
[ 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?
>
> 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
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-12 Metrologia
- 2024-05-12 app do udostepniania ekranu tel (obraz + audio) na ekran tv
- 2024-05-12 Smukły, długi ściągacz izolacji do kynaru
- 2024-05-12 Afera II LO w Nowym Sączu wypracowanie
- 2024-05-12 rezystor 3 omy 400W
- 2024-05-12 Dwukabinowy Citroen - dziwadło pod zabudowę spec
- 2024-05-12 Co oznacza Wi-Fi? - po prostu nic!
- 2024-05-11 Chess
- 2024-05-11 Chess
- 2024-05-11 Vitruvian Man - parts 7-11a
- 2024-05-11 Vitruvian Man - parts 7-11a
- 2024-05-11 Katowice => Administrator IT - Wirtualizacja i Konteneryzacja <=
- 2024-05-11 Poznań => Business Development Manager - obszar bezpieczeństwa IT <=
- 2024-05-11 Vitruvian Man - parts 1-6
- 2024-05-11 Vitruvian Man - parts 1-6