eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzukam algorytmuRe: Szukam algorytmu
  • Data: 2015-10-20 11:47:52
    Temat: Re: Szukam algorytmu
    Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie 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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: