Temukan jarak penjumlahan terkecil dengan elemen pasangan unik dari satu set ke elemen dari set lainnya

Sebagai input, saya memiliki dua set poin dalam R ^N , biasanya untuk N besar, misalnya N = 40. Andaikan kedua set memiliki elemen m:

S = s ₁ ... s _m

T = t ₁ ... t _m

Secara semantik kedua set sama, tetapi karena noise (dalam bentuk apa pun) pada titik R ^ N, elemen yang seharusnya secara semantik sama masih memiliki jarak lebih besar dari 0.

Apa yang ingin saya temukan adalah m tupel (s _i , t _j ) sedemikian rupa sehingga jumlah jarak (s _i , t _j ) diminimalkan dan sedemikian sehingga s _k dan t _k persis terjadi sekali dalam set tupel untuk k = 1 ... m Pada dasarnya (i, j) harus dipilih sebagai menara di papan catur yang tidak dapat saling menabrak sambil meminimalkan jarak yang dijumlahkan.

Dengan kata lain, saya ingin menemukan satu ke satu peta antara S dan T yang 'semacam peta identitas, tetapi kuat untuk noise'. Kami mengasumsikan bahwa ukuran jarak merupakan indikasi yang baik tentang bagaimana elemen yang sama berada.

Pada dasarnya saya perlu menemukan permutasi 1 ... N, dan karenanya saya pikir masalah ini adalah NP-hard atau NP-complete, karena 'rasanya' sangat mirip dengan TSP; namun saya belum dapat menulis ulang masalah TSP ke subset dari masalah saya di sini.

Apakah masalah ini secara realistis dapat dipecahkan untuk N besar? Apakah ada nama untuk masalah ini? Apa yang akan menjadi solusi yang layak? Apakah ada kriteria lain yang mungkin lebih baik daripada jarak yang dijumlahkan?

Saya memikirkan pendekatan serakah, misalkan D menjadi matriks jarak, d _ij = jarak (s _i , t _j ).

T = {}
while D is not empty:
    (i,j) = argmin-(i,j) dij
    append (i,j) to T
    set row i and column j to infinity.

Ini tidak menghasilkan solusi optimal, tetapi menemukan solusi. Apakah ini taruhan terbaik saya? Haruskah saya menggunakan anil simulasi, atau itu berlebihan?

PS: dari sudut pandang saya, ini hanya masalah kecil dalam masalah ML yang lebih besar, namun, saya sangat tertarik dengan latar belakang CS itu.

algorithms optimization Herbert
sumber

Tidak yakin, tapi mungkin utas ini dapat membantu Anda?

Saya sangat tertarik dengan masalah ini karena saya juga mengalami ketika merancang beberapa algoritma ML ...

daaxix

Saya tidak bisa melihat cara apa pun untuk menghindari penyelesaian masalah jumlah akar sebagai bagian dari masalah ini.

$\hspace{.75 in}$ (Saya juga tidak melihat argumen apa pun bahwa masalah ini sangat sulit untuk SoSR.)

$\;$

"Pada dasarnya saya perlu menemukan permutasi 1 ... N, dan karenanya saya pikir masalah ini adalah NP-hard atau NP-complete" - seperti menyortir, hm?

Raphael

@ Raphael: Poin bagus. Itu lebih merupakan firasat, yang seperti dinyatakan dalam OP saya tidak dapat menemukan argumen untuk. Karena itu pertanyaan "Apakah masalah ini secara realistis dapat dipecahkan untuk N besar?"

Herbert

Ini adalah masalah menemukan pencocokan maksimum dalam grafik bipartit tertimbang. Ada algoritma efisien yang menyelesaikan masalah ini dalam waktu polinomial.

Pada dasarnya, Anda memiliki grafik bipartit lengkap dengan $2m$ sudut. $S$ membentuk satu set simpul; $T$ membentuk set simpul lainnya. Untuk setiap $i,j$ , buat tepi dari $s_i$ untuk $t_j$ yang beratnya sama dengan $-d(s_i,t_j)$ , negasi jarak antara $s_i$ dan $t_j$ .

Sekarang, Anda ingin menemukan pasangan yang beratnya sebesar mungkin. Ini sesuai dengan satu set pasangan $(s_i,t_j)$ yang total jaraknya sekecil mungkin. Dari sana, Anda dapat menggunakan algoritma yang ada pada grafik ini untuk menemukan pencocokan berat maksimum.

DW
sumber

Temukan jarak penjumlahan terkecil dengan elemen pasangan unik dari satu set ke elemen dari set lainnya

Jawaban: