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ść.

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.
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.