Laboratoriya ishi 13 Mavzu

for i = 1 to length(P) - 1
for j = i + 1 to length(P)
let p = P[i], q = P[j]
if dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair
Masala
1. Nuqtalarni x koordinatalariga ko'ra tartiblang.
2. Biz vertikal tekis chiziqning o'lchamiga teng bo'lgan ikkita kichik guruhga ko'plab nuqtalarni ajratamiz x=x_mid
3. Muammoni chap va o'ng tomonlarda qayta ko'rib chiqamiz. Bu chap minimal masofa d_Lmin va o'ng minimal masofaga d_Rmin olib keladi.
4. d_LRmin Biz nuqta juftlari orasida minimal masofani topamiz, ulardan bir nuqta vertikal chiziqning chap tomonida, ikkinchisi esa to'g'ri chiziqning o'ng tomonida yotadi.
5. Yakuniy javob orasida minimal qiymati d_Lmin bo'ladi, d_Rmin va d_LRmin

4 bosqichi chiziqli vaqt ichida amalga oshirilishi mumkin. Shunga qaramay, sodda yondashuv barcha juftlarni chap/o'ng, ya'ni kvadrat vaqt uchun masofani hisoblashni talab qiladi. Asosiy kuzatuv ko'plab nuqtalarning beparvolikning keyingi xususiyatiga asoslangan. Biz allaqachon bilamizki, eng yaqin nuqtalar juftligi bundan ko'ra ko'proq masofada emas dist=min(d_Lmin,d_Rmin. Shuning uchun, ajratilgan chiziqning chap tomonidagi har bir p nuqtasi uchun biz to'rtburchakda joylashgan nuqtalarga (dist, 2ist dist) masofani solishtirishimiz kerak) rasmda ko'rsatilgandek. Va bu to'rtburchak olti nuqtadan ko'p bo'lmasligi mumkin, ularning orasidagi masofa kamida d_Rmin. Shunday qilib, 4-bosqichda 6 n masofani hisoblash kifoya. Qadamlar soni uchun recurrent nisbati T(n)=2T(n/2)+O(n) ikkala recurrent uchun asosiy teoremasi yordamida hal qilinishi mumkin , deb yozilgan bo'lishi mumkin, va beradi, deb Conquer va Conquer O(n log n).
Eng yaqin nuqta juftligi Delon triangulyatsiyasidagi qovurg'ani aniqlaganligi va qora diagrammadagi ikkita ulashgan hujayraga mos kelishi sababli, ushbu ikki tuzilmadan biri berilgan bo'lsa, eng yaqin nuqta juftligi chiziqli vaqt ichida aniqlanishi mumkin. Delone triangulatsiyasini yoki qarg'aning diagrammasini hisoblash vaqtni O(n log n) oladi. Ushbu yondashuvlar D>2> o'lchamlari uchun samarali emas, ammo “ajratish va boshqarish” algoritmi O(n log n) har qanday doimiy o'lchov d qiymati uchun ish vaqti bilan umumlashtirilishi mumkin
Eng yaqin juftlikning dinamik vazifasi
Agar dinamik ob'ektlar bir qator berilgan bo'lsa, samarali yaqin ochko bir juft har safar ob'ekt joylashtirilgan yoki o'chirildi pereiglisleniya uchun algoritmlar va ma'lumotlar tuzilmalarni topish.