Mencari Pasangan Mata Terhampir Menggunakan Divide-and-Conquer

Bahagian ini membentangkan algoritma yang cekap untuk mencari pasangan mata terdekat menggunakan divid-and-conquer. Memandangkan satu set mata, masalah pasangan terdekat ialah mencari dua mata yang paling hampir antara satu sama lain. Seperti yang ditunjukkan dalam Rajah di bawah, satu garisan dilukis untuk menyambung dua titik terdekat dalam animasi pasangan terdekat.

Kajian Kes: Mencari Pasangan Terdekat, membentangkan algoritma brute-force untuk mencari pasangan mata yang paling hampir. Algoritma mengira jarak antara semua pasangan mata dan mencari satu dengan jarak minimum. Jelas sekali, algoritma mengambil masa O(n^2). Bolehkah kita mereka bentuk algoritma yang lebih cekap?

Kami akan menggunakan pendekatan yang dipanggil divide-and-conquer untuk menyelesaikan masalah ini. Pendekatan membahagikan masalah kepada submasalah, menyelesaikan submasalah, kemudian menggabungkan penyelesaian submasalah untuk mendapatkan penyelesaian bagi keseluruhan masalah. Tidak seperti pendekatan pengaturcaraan dinamik, submasalah dalam pendekatan divide-and-conquer tidak bertindih. Submasalah adalah seperti masalah asal dengan saiz yang lebih kecil, jadi anda boleh menggunakan rekursi untuk menyelesaikan masalah. Malah, semua penyelesaian untuk masalah rekursif mengikut pendekatan divide-and-conquer.

Langkah di bawah menerangkan cara menyelesaikan masalah pasangan terdekat menggunakan pendekatan bahagi dan takluk.

• Langkah 1: Isih titik dalam susunan koordinat x yang semakin meningkat. Untuk titik-titik dengan koordinat-x yang sama, susun pada koordinat-y. Ini menghasilkan senarai S mata yang diisih.
• Langkah 2: Bahagikan S kepada dua subset, S1 dan S2, dengan saiz yang sama menggunakan titik tengah dalam senarai yang diisih. Biarkan titik tengah berada dalam S1. Cari pasangan terdekat secara rekursif dalam S1 dan S2. Biarkan d1 dan d2 masing-masing menunjukkan jarak pasangan terdekat dalam dua subset.
• Langkah 3: Cari pasangan terdekat antara titik dalam S1 dan titik dalam S2 dan nyatakan jaraknya sebagai d3. Pasangan terdekat ialah yang mempunyai jarak min(d1, d2, d3).

Isih pilihan mengambil masa O(n^2). Langkah 1 boleh dilakukan dalam masa O(n log n). Langkah 3 boleh dilakukan dalam masa O(n). Biarkan d = min(d1, d2). Kita sedia maklum bahawa jarak pasangan terdekat tidak boleh lebih besar daripada d. Untuk satu titik dalam S1 dan satu titik dalam S2 untuk membentuk pasangan terdekat dalam S, titik kiri mestilah dalam jalurL dan titik kanan dalam jalur, seperti yang digambarkan dalam Rajah di bawah ( a).

Untuk titik p dalam jalurL, anda hanya perlu mempertimbangkan titik kanan dalam segi empat tepat d X 2d, seperti ditunjukkan di bawah (b). Mana-mana titik kanan di luar segi empat tepat tidak boleh membentuk pasangan terdekat dengan p. Memandangkan jarak pasangan terdekat dalam S2 lebih besar daripada atau sama dengan d, boleh terdapat paling banyak enam
titik dalam segi empat tepat. Oleh itu, untuk setiap mata dalam stripL, paling banyak enam mata dalam stripR perlu dipertimbangkan.

Untuk setiap titik p dalam jalurL, bagaimana anda mencari titik dalam kawasan segi empat tepat d X 2d yang sepadan dalam jalurR? Ini boleh dilakukan dengan cekap jika titik dalam stripL dan stripR diisih dalam susunan y-koordinat yang semakin meningkat. Biarkan pointsOrderedOnY menjadi senarai mata yang diisih dalam susunan y-koordinat yang semakin meningkat. pointsOrderedOnY boleh diperolehi terlebih dahulu dalam algoritma. stripL dan stripR boleh diperolehi daripada pointsOrderedOnY dalam Langkah 3 seperti yang ditunjukkan dalam kod di bawah.

untuk setiap titik p dalam pointsOrderedOnY
jika (p dalam S1 dan pertengahan.x – p.x <= d)
tambah p pada jalurL;
lain jika (p dalam S2 dan p.x - pertengahan.x <= d)
tambah p pada stripR;

Biar titik dalam stripL dan stripR menjadi {p0, p1, ... , pk} dan {q0, q1, ... , qt}, seperti yang ditunjukkan dalam Rajah di atas (c). Pasangan paling hampir antara satu titik dalam stripL dan satu titik dalam stripR boleh didapati menggunakan algoritma yang diterangkan dalam kod di bawah.

d = min(d1, d2);
 r = 0; // r is the index of a point in stripR
 for (each point p in stripL) {
 // Skip the points in stripR below p.y - d
  while (r < stripR.length && q[r].y <= p.y - d)
  r++;

  let r1 = r;
  while (r1 < stripR.length && |q[r1].y – p.y| <= d) {
 // Check if (p, q[r1]) is a possible closest pair
 if (distance(p, q[r1]) < d) {
 d = distance(p, q[r1]);
 (p, q[r1]) is now the current closest pair;
 }

 r1 = r1 + 1;
 }
}

Mata dalam stripL dianggap daripada p0, p1, ... , pk dalam susunan ini. Untuk satu titik p dalam stripL, langkau titik dalam stripR yang berada di bawah p.y – d (baris 5–6). Apabila sesuatu mata dilangkau, ia tidak akan dipertimbangkan lagi. Gelung while (baris 9–17) menyemak sama ada (p, q[r1]) ialah pasangan terdekat yang mungkin. Terdapat sekurang-kurangnya enam pasangan q[r1] sedemikian, kerana jarak antara dua titik dalam stripR tidak boleh kurang daripada d. Jadi kerumitan untuk mencari pasangan terdekat dalam Langkah 3 ialah O(n).

Perhatikan bahawa Langkah 1 dalam langkah di atas dilakukan sekali sahaja untuk menyusun semula mata. Andaikan bahawa semua mata telah disusun semula. Biarkan T(n) menandakan kerumitan masa untuk algoritma ini. Oleh itu,

Oleh itu, pasangan mata terdekat boleh didapati dalam masa O(n log n).

Atas ialah kandungan terperinci Mencari Pasangan Mata Terhampir Menggunakan Divide-and-Conquer. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!