Memilih subset untuk memaksimalkan jarak minimum antara titik

Saya memiliki satu set titik , dan saya memiliki jarak antara setiap titik . Jarak-jarak ini adalah euclidean tetapi titik-titik tersebut sebenarnya dalam ruang fitur. $C$ $D(P_i,P_j)$

Dari poin saya ingin memilih subset dari poin. Sebut subset ini . Saya ingin memilih subset ini sehingga dapat memaksimalkan jarak minimum antara semua poin dalam baru set . $C$ $n$ $s$ $s$

max_{\begin{matrix} s \subset C \\ | s | = n \end{matrix}} (min_{\begin{matrix} i, j \in s \\ i \neq j \end{matrix}} D (P_{i}, P_{j}))

$\max_{\substack{s \subset C \\ |s| = n}} \left( \min_{\substack{i,j \in s \\ i \neq j} } D \left( P_i, P_j \right) \right)$

Saat ini saya menggunakan mendaki bukit untuk mengatasi masalah ini. Saya mengerti bahwa anil yang disimulasikan dapat memberikan solusi yang lebih baik.

Apakah ada solusi yang diketahui untuk masalah jenis ini? Atau bisakah masalah ini diformulasikan menjadi masalah lain yang mudah diselesaikan?

optimization pengguna1389800
sumber

Saya tertarik dengan masalah yang sama. Berdasarkan saya sampai hasil sekarang mencari, itu sebanding dengan masalah p-dispersi dalam masalah lokasi fasilitas yang ini adalah review kertas yang bagus.

XTZ

Apakah Anda tahu apa nama masalah ini?

Dandelion

Jawaban:

Versi masalah keputusan masalah optimasi ini adalah:

Diberi ambang batas , Anda ingin tahu apakah mungkin untuk menemukan subset dari poin sehingga setiap pasangan poin dalam subset tersebut setidaknya berjarak unit. $t$ $n$ $t$

Tentu saja, jika Anda dapat menyelesaikan masalah keputusan, kami dapat menyelesaikan masalah optimisasi Anda (dengan pencarian biner pada ambang ). $t$

Sekarang masalah keputusan ini adalah masalah menemukan sebuah set independen dalam grafik Euclidean, di mana poin memiliki keunggulan antara mereka jika mereka berada pada jarak terpisah. Salah satu pendekatan akan melihat algoritma perkiraan standar untuk set independen. $x,y$ $\le t$

Bahkan lebih baik, Anda dapat melihat algoritma untuk set independen dalam grafik persimpangan geometris . Pertimbangkan satu set disk, di mana masing-masing disk memiliki diameter dan berada di tengah salah satu titik dalam set . Sekarang kita dapat membentuk grafik perpotongan geometris, di mana ada satu titik untuk setiap disk dan sebuah tepi antara dua titik jika cakram yang bersesuaian saling berpotongan. Masalah menemukan set independen dalam grafik semacam ini telah dipelajari dan ada algoritma perkiraan untuk masalah ini yang bisa Anda coba gunakan. $t$ $C$

Jika Anda menginginkan optimal yang tepat daripada perkiraan, Anda bisa menggunakan "palu besar" standar, seperti solver SAT atau solver ILP. Ada cara mudah untuk merumuskan masalah set independen sebagai instance SAT, dan kemudian Anda bisa menerapkan solver SAT untuk menemukan apakah ada subset poin yang semua unit jauh dari satu sama lain. $n$ $\ge t$

DW
sumber