Tempo de execução do algoritmo ideal

16

Nos é dado um conjunto de pontos bidimensionais e um número inteiro . Precisamos encontrar uma coleção de círculos que incluam todos os pontos, de modo que o raio do maior círculo seja o menor possível. Em outras palavras, devemos encontrar um conjunto de pontos centrais, de modo que a função de custo é minimizado. Aqui, denota a distância euclidiana entre um ponto de entrada p_i e um ponto central c_j . Cada ponto se atribui ao centro de cluster mais próximo, agrupando os vértices em kk k n C = { c 1 , c 2 , , c k } k custo ( C ) = max i min j D ( p i , c j ) D p i c j k|P|=nkknC={c1,c2,,ck}kcost(C)=maximinjD(pi,cj)Dpicjk aglomerados diferentes.

O problema é conhecido como o problema (discreto) de cluster k e é NP -hard. Pode ser mostrado com uma redução do problema do conjunto dominante NP que, se existir um algoritmo de aproximação ρ para o problema com ρ<2 então P=NP .

O algoritmo ideal 2 aproximação 2 é muito simples e intuitivo. Primeiro, escolhe-se um ponto pP arbitrariamente e o coloca no conjunto C dos centros de cluster. Em seguida, escolhe-se o próximo centro de cluster, o mais distante possível de todos os outros centros de cluster. Então enquanto |C|<k , que repetidamente encontrar um ponto de jP para os quais a distância D(j,C) seja maximizada e adicioná-lo a C . Uma vez |C|=k terminamos.

Não é difícil ver que o algoritmo guloso ideal é executado no tempo O(nk) . Isso levanta uma questão: podemos alcançar o(nk) ? Quanto melhor podemos fazer?

Juho
fonte

Respostas:

7

O problema pode ser visto geometricamente de uma maneira que gostaríamos de cobrir os pontos por bolas, onde o raio da bola maior é minimizado.Vk

O(nk) é realmente bastante simples de alcançar, mas é possível fazer melhor. Feder e Greene, algoritmos ótimos para cluster aproximado, 1988 atingem um tempo de execução de usando estruturas de dados mais inteligentes e mostram ainda que isso é ideal no modelo de árvore de decisão algébrica.Θ(nlogk)

Juho
fonte
1

Minha pergunta: Existe uma maneira de executar a estratégia de seleção gananciosa em ?o(|V|2)

Parece-me que você o descreveu. Caso eu tenha lido demais na sua descrição, aqui está o que eu entendi. Possui uma estrutura de dados associativo associando cada elemento de com a soma da distância de elementos de S . Essa estrutura de dados pode ser inicializada a um custo O ( | V | ) com a distância até pe essa inicialização pode produzir o próximo elemento como um efeito colateral sem aumentar a complexidade. Ele pode ser atualizado após a seleção de um novo elemento a um custo de O ( | V | ) , produzindo novamente o próximo elemento como efeito colateral. Repita para obter SVSO(|V|)pO(|V|)S. A complexidade resultante é .O(k|V|)

AProgrammer
fonte
1
Mas observe o limite em : no pior caso, pode ser tão grande quanto | V | . Eu suspeito que existem estruturas de dados que atingem limites ainda melhores, mas eu realmente não sei. k|V|
26412 Juho
Opa, e não O na sua pergunta. (Observe que na sua pergunta você voltou a k 3 , portanto isso deve ser uma melhoria). O que proponho não usa o fato de você estar trabalhando em um espaço euclidiano; acho que você precisará usá-lo para fazer melhor, mas atualmente não vejo como. oOk3
APROGRAMMER #