On 02.07.2014 07:19, Borneq wrote:
> W dniu 2014-07-02 00:30, bartekltg pisze:
>> http://en.wikipedia.org/wiki/Maximum_disjoint_set
>>
>> Zastępujesz punkty kolami o srednicy równej minimalnemu dystansowi.
>>
>> Nadal NP-trudne.
>
> A to coś zmienia? Ja zastępuję prostokąty różnych wielkości otaczające
> elipsoidalne kształty punktami w ich środku. A odległość traktuję
> binarnie - bliżej/nie bliżej

Przypadek ogólniejszy jest trudniejszy. NA dzień dobry w oryginalnym
masz heurystki oparte o gozkład geometryczny.

>
>> Najprostszy zachłanny będzie liniowy względem rozmiaru grafu (V+E).
>
> Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
> przeszkadza, ale w jaki sposób uzyskać czas liniowy?

Bierzesz wierzchołek, wszystkich sąsiadów wyrzucasz. Bierzesz
pierwszy wolny wierzchołek, wyrzucasz wszystkich jego sąsiadów.
Powtarzasz do wyczerpania nieprzetworzonych wierzchołków.

Jest maksymalny, po dodanie jakiegokolwiek wyrzuconego nie jest
możliwe, stykał się z jakimś pozostawionym.

Czas to liczba krawędzi + liczba wierzchołków.

> Pierwszą częścią jest w ogóle uzyskanie grafu - tu biorę odległość każdy
> z każdym, choć nie ma sensu brać odległości dwóch odległych punktów.

Jeśli rozmiar obszaru jest przyzwoicie większy od rozmiaru
kulki/kwadratu, użyj jakiejś modyfikacji algorytmu zamiatania.
będzie znacznie szybciej.


> Potem jest właściwy algorytm. Liczba krawędzi wychodząca z każdego
> wierzchołka jest mała w porównaniu z liczbą wierzchołków - mniejsza niż
> pierwiastek, raczej kilka. Ale algorytm który stosuję jest kwadratowy,
> ponieważ jedno szukanie maksymalnego wierzchołka jest liniowe -
> przelatuje przez wszystkie wierzchołki, choć wiele ma po tyle samo
> krawędzi.

Skoro musisz wyrzucać je w tej kolejności, użyj jakiejś struktury,
gdzie masz kolejność i możesz 'pogarszać priorytet'. W najgorszym
przypadku ze std::set (drzewo binarne).

pzdr
bartekltg