On 01.07.2014 20:37, Borneq wrote:
> W dniu 2014-07-01 18:46, bartekltg pisze:
>> Problem rzeczywiście ma nazwę i jest jako tako rozpoznany.
>>
>> http://en.wikipedia.org/wiki/Maximum_independent_set
#Finding_maximum_independent_sets
>>
>>
>>
>> Na zachętę, problem NP-trudny;-)
>
> Dzięki za namiar!
> Oryginalny problem to przerzedzanie punków:
> Mam zbiór punktów, które są za gęste. Mam przerzedzić punkty - wybrać
> zbiór puntów reprezentantów i zbiór punktów pozostałych, tak aby
> reprezentanci nie byli bliżej od siebie niż jakaś odległość.


Trzeba było od razu, a nie się czaić:)

http://en.wikipedia.org/wiki/Independent_set_%28grap
h_theory%29#Independent_sets_in_geometric_intersecti
on_graphs

http://en.wikipedia.org/wiki/Maximum_disjoint_set

Zastępujesz punkty kolami o srednicy równej minimalnemu dystansowi.

Nadal NP-trudne.

> NP-trudny:
> Widocznie rozwiązywałem w sposób za bardzo zachłanny. Ale może nie jest
> taki ważny warunek, aby było jak najwięcej wierzchołków, wystarczy że
> maksymalny w sensie inkluzji, że wystarczy jeden dodać i nie będzie
> spełniony warunek.

Taki nazywa się maksymalnym (Maximal independent set)

Skoro odpowiada Ci rozwiązanie przybliżone, użyj heurystyk,
najlepiej dla oryginalnego, prostszego problemu.

> Na razie obliczam w czasie kwadratowym, może nienajlepsze rozwiązanie to
> tablica wektorów, w każdym z nich indeksy połączonych wierzchołków.
> Myślę że jeśli chodzi o przerzedzanie punktów to wystarczy ten
> zachłanny. Można by go teraz dostroić, bo w każdym kroku wybieram z
> kilku o tej samej liczbie krawędzi do odrzucenia. Odrzucać mam taki,
> który jak najmniej nadaje się na reprezentanta.

Najprostszy zachłanny będzie liniowy względem rozmiaru grafu (V+E).

pzdr
bartekltg