Runtime dari algoritma approximation optimal greedy optimal untuk masalah -clustering

16

Kita diberi satu set titik 2 dimensi dan bilangan bulat . Kita harus menemukan kumpulan lingkaran yang melingkupi semua poin sehingga jari-jari lingkaran terbesar sekecil mungkin. Dengan kata lain, kita harus menemukan himpunan dari titik pusat k sehingga fungsi biaya \ text {cost} (C) = \ max_i \ min_j D (p_i, c_j ) diminimalkan. Di sini, D menunjukkan jarak Euclidean antara titik input p_i dan titik pusat c_j . Setiap titik menempatkan dirinya ke pusat kelompok terdekat yang mengelompokkan simpul menjadi kk k n C = { c 1 , c 2 , ... , c k } k biaya ( 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 cluster yang berbeda.

Masalahnya dikenal sebagai masalah ( -crete ) k -clustering dan itu adalah NP -hard. Hal ini dapat ditunjukkan dengan pengurangan dari NP set {NP} -lengkap set masalah mendominasi bahwa jika ada algoritma ρ -approximation untuk masalah dengan ρ<2 lalu P=NP .

Algoritma 2 approximation optimal sangat sederhana dan intuitif. Yang pertama mengambil titik pP sewenang-wenang dan menempatkannya di set C pusat cluster. Kemudian seseorang memilih pusat gugus berikutnya sehingga sejauh mungkin dari semua pusat gugus lainnya. Jadi sementara |C|<k , kita berulang kali menemukan titik jP yang jarak D(j,C) dimaksimalkan dan menambahkannya ke C . Sekali |C|=k kita sudah selesai.

Tidak sulit untuk melihat bahwa algoritma serakah optimal berjalan dalam waktu O(nk) . Hal ini menimbulkan pertanyaan: kita dapat mencapai o(nk) waktu? Seberapa jauh lebih baik yang bisa kita lakukan?

Juho
sumber

Jawaban:

7

Masalahnya memang bisa dilihat secara geometris dengan cara yang kita ingin menutupi titik dengan bola , di mana jari-jari bola terbesar diminimalkan.Vk

O(nk) memang cukup sederhana untuk dicapai tetapi orang dapat melakukan lebih baik. Feder dan Greene, algoritma optimal untuk pengelompokan perkiraan, 1988 mencapai waktu berjalan menggunakan struktur data yang lebih pintar dan lebih jauh menunjukkan bahwa ini optimal dalam model pohon keputusan aljabar.Θ(nlogk)

Juho
sumber
1

Pertanyaan saya: Apakah ada cara saya dapat membuat strategi memetik serakah berjalan di waktu?o(|V|2)

Sepertinya Anda menggambarkannya. Jika saya membaca deskripsi Anda terlalu jauh, inilah yang saya mengerti. Memiliki struktur data asosiatif menghubungkan setiap elemen dengan jumlah jarak ke elemen S . Struktur data ini dapat diinisialisasi dengan biaya O ( | V | ) dengan jarak ke p dan inisialisasi ini dapat menghasilkan elemen berikutnya sebagai efek samping tanpa meningkatkan kompleksitas. Ini dapat diperbarui setelah pemilihan elemen baru dengan biaya O ( | V | ) , lagi-lagi menghasilkan elemen berikutnya sebagai efek samping. Ulangi untuk mendapatkan SVSO(|V|)pO(|V|)S. Kompleksitas yang dihasilkan adalah .O(k|V|)

Pemrogram
sumber
1
Tetapi perhatikan terikat pada : dalam kasus terburuk itu bisa sebesar | V | . Saya menduga ada struktur data yang mencapai batas yang lebih baik, tapi saya benar-benar tidak tahu. k|V|
Juho
Ups, dan bukan O dalam pertanyaan Anda. (Perhatikan bahwa dalam pertanyaan Anda, Anda kembali ke k 3 , jadi ini harus menjadi peningkatan). Apa yang saya usulkan tidak menggunakan fakta bahwa Anda bekerja di ruang Euclidian, saya pikir Anda harus menggunakannya untuk melakukan yang lebih baik, tetapi saat ini saya tidak mengerti caranya. oOk3
Pemrogram