Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề bài toán cặp điểm gần nhất

BÀI TOÁN CẶP ĐIỂM GẦN NHẤT I. Mở đầu §a sè c¸c thuËt to¸n ®Òu tËp trung xö lÝ trªn v¨n b¶n (xö lÝ trªn x©u) vµ c¸c con sè, chóng ®-îc thiÕt kÕ vµ xö lÝ s½n trong phÇn lín c¸c bµi to¸n lËp tr×nh. §èi víi c¸c bµi to¸n h×nh häc th× ®ßi hái kh¸c h¼n, ng-êi lËp tr×nh ph¶i cã sù tÝnh to¸n tØ mØ c¸c c«ng thøc vÒ h×nh häc tr-íc khi ®i vµo lËp tr×nh. Khi lµm c¸c bµi tËp vÒ h×nh häc th-êng ph¶i ®ßi hái sù c«ng phu lËp tr×nh h¬n c¸c bµi tËp kh¸c, nhÊt lµ viÖc thiÕt lËp c¸c c«ng thøc th× bµi lËp tr×nh míi cã hiÖu qu¶. 1. §èi t-îng h×nh häc c¬ b¶n Trong c¸c bµi to¸n Tin häc thuéc lo¹i h×nh häc cã 3 ®èi t-îng c¬ b¶n lµ: §iÓm, §o¹n th¼ng vµ §a gi¸c. §iÓm: §-îc xÐt b»ng mét cÆp sè nguyªn lµ täa ®é cña ®iÓm ®ã trong hÖ trôc täa ®é Descartes th-êng dïng. §o¹n th¼ng: Lµ mét cÆp ®iÓm ®-îc nèi víi nhau mét phÇn cña ®-êng th¼ng. §a gi¸c: Lµ mét d·y c¸c ®iÓm víi hai ®iÓm liªn tiÕp ®-îc nèi bëi mét ®o¹n th¼ng, vµ ®iÓm ®Çu ®-îc nèi víi ®iÓm cuèi t¹o thµnh mét h×nh gÊp khóc khÐp kÝn. 2. D÷ liÖu l-u tr÷ c¸c ®èi t-îng h×nh häc c¬ b¶n Lµm viÖc víi c¸c ®èi t-îng h×nh häc chóng ta cÇn quyÕt ®Þnh thÓ hiÖn chóng nh- thÕ nµo? Th«ng th-êng ta dïng mét m¶ng ®Ó biÓu diÔn mét ®a gi¸c, dï r»ng mét sè tr-êng hîp kh¸c chóng ta cã thÓ dïng danh s¸ch liªn kÕt hay c¸c kiÓu kh¸c. §èi t-îng chóng ta th-êng xuyªn ph¶i lµm viÖc víi h×nh häc lµ täa ®é, do ®ã viÖc l-u tr÷ to¹ ®é cña c¸c ®iÓm lµ phæ biÕn trong c¸c bµi to¸n lËp tr×nh vÒ h×nh häc. II. Nội dung 1 1. Phát biểu bài toán Bài toán: Cho𝑁 điểm trên mặt mẳng tọa độ, tìm khoảng cách ngắn nhất giữa hai điểm bất kỳ. 2. Thuật toán Bài toán này ta có thể dễ dàng thực hiện thuật toán 𝑏𝑟𝑢𝑡𝑒𝑓𝑜𝑟𝑐𝑒, ta xét tất cả các cặp điểm và chọn cặp có khoảng cách ngắn nhất giữa chúng. Thuật toán có độ phức tạp 𝑂(𝑛2 ). Ta có một số thuật toán tốt hơn như sau: 2.1.Thuật toán chia để trị a. Ý tưởng thuật toán Thuật toán chia để trị giải quyết bài toán này thực hiện như sau:  Sắp xếp các điểm đã cho theo thứ tự từ trái sang phải. Chia tập điểm thành hai tập.  Thực hiện thao tác đệ quy, tìm cặp điểm gần nhất trong hai tập con, trả lại giá trị là khoảng cách ngắn nhất trong tập đó.  Gọi 𝛿 là khoảng cách ngắn nhất, trong hai khoảng cách ngắn nhất trong hai tập con. Ta chỉ quan tâm tới các cặp có khoảng cách nhỏ hơn 𝛿.  Xét trong “cửa sổ” độ rộng 2𝛿, sắp xếp tất cả các điểm trong cửa sổ đó 2 theo thứ tự tăng dần chiều tọa độ 𝑦.  Nhận xét: vì khoảng cách giữa mỗi cặp điểm bất kỳ trên hai tập không nhỏ hơn 𝛿 nên với mỗi một điểm trên “cửa sổ”, có không quá 3 điểm mỗi bên có khoảng cách 𝑡ọ𝑎 độ 𝑦 nhỏ hơn hoặc bằng 𝛿 so với điểm đó. Do vậy, với mỗi điểm, ta chỉ cần xét (ghép cặp) không quá 6 điểm để có thể tìm ra cặp điểm có khoảng cách Euclid nhỏ hơn 𝛿. b. Cài đặt Sử dụng đệ quy quay lui để cài đặt thuật toán. Với mỗi đoạn:  Nếu độ dài đoạn 𝑛 ≤ 3, ta tính toán bruteforce để tìm cặp điểm gần nhất.  Nếu độ dài 𝑛 ≥ 3 ta chia đôi tập, đệ quy quay lui để tính khoảng cách gần nhất trong hai tập con, chọn giá trị bé nhất trong hai khoảng cách.  Dùng mảng 𝑠𝑡𝑟𝑖𝑝 để trộn hai phía theo thứ tự tăng dần 𝑦, lọc lấy những phần tử có chênh lệch 𝑦 nhỏ hơn giá trị 𝑚𝑖𝑛 đang có. (𝑑). Chú ý sau khi thực hiện, ta thực hiện sắp xếp trộn hai phía của đoạn theo thứ tự tăng dần y luôn, độ phức tạp 𝑂(𝑛), không sử dụng thuật toán sắp xếp khác.  Với các phần tử trong cửa sổ, với mỗi điểm, xét các điểm lân cận (sau khi đã sắp xếp) có chênh lệch 𝑦 nhỏ hơn 𝑑. (số phần tử này ≤ 6) 3 Dưới đây là chương trình cài đặt tính cặp điểm gần nhấttheo thuật toán chia để trị: Input:  Dòng đầu tiên là số𝑁 – số lượng điểm(𝑛 ≤ 2.105 )  𝑁dòng tiếp theo, mỗi dòng chứa tọa độ một điểm theo thứ tự. Output: Khoảng cách nhỏ nhất cần tìm, chính xác 5 chữ số phần thập phân. CLOSESTPAIR.INP 3 1 1 2 2 2 1 CLOSESTPAIR.OUT 1.00000 Chương trình: #include #define sz(x) int(x.size()) #define MIN(x,y) if (x < y) x = y #define PB push_back #define mp make_pair #define Task "closestpair" #define maxn 200002 #define MOD 1000000007 #define remain(x) if (x > MOD) x -= MOD #define pii pair #define X first #define Y second using namespace std; pii a[maxn], strip[maxn]; double ans = 1e10; double Distance(pii P1, pii P2) { double XX = P1.X - P2.X; 4 double YY = P1.Y - P2.Y; return sqrt(XX*XX + YY*YY); } double bruteForce(pii P[], int n) { double kmin = FLT_MAX; for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) kmin = min(kmin, Distance(P[i], P[j])); return kmin; } bool compareY(pii p1, pii p2) { return (p1.Y < p2.Y || (p1.Y == p2.Y && p1.X < p2.X)); } double stripClosest(pii strip[], int n, double d) { double kmin = d; for (int i = 0; i < n; ++i) for (int j = i+1; j < n && (strip[j].Y - strip[i].Y) < kmin; j++) kmin = min(Distance(strip[i],strip[j]), kmin); return kmin; } double Calc(pii P[], int n) { if (n <= 3) { sort (P, P+n, compareY); return bruteForce(P, n); } int mid = n/2; pii midPoint = P[mid]; double dl = Calc(P, mid); double dr = Calc(P + mid, n-mid); double d = min(dl, dr); 5 int ccount = 0; merge(P, P+mid, P+mid, P+n, strip,compareY); for (int i = 0; i < n; i++) { P[i] = strip[i]; if (abs(strip[i].X - midPoint.X) < d) strip[ccount++] = strip[i]; } return min(d, stripClosest(strip, ccount, d)); } double Closest(pii a[], int n) { sort(a, a+n); return Calc(a,n); } int main() { ios_base::sync_with_stdio(0); freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y; printf("%0.5f", Closest(a,n)); return 0; } c. Đánh giá Việc tính trong cửa sổ 2𝛿 và sắp xếp trộn với một đoạn độ dài 𝑛 (không tính hai đoạn con) có độ phức tạp O(n). Số lần lặp thủ tục tính có lời gọi không quá log 2 𝑛 lần nên tổng độ phức tạp thuật toán là 𝑂(𝑛𝑙𝑔𝑛). 6 2.2.Thuật toán sweep line a. Ý tưởng thuật toán.  Sắp xếp tọa độ các điểm theo chiều 𝑥.  Xét từng điểm từ trái qua phải. Giả sử ta đang xét tới điểm 𝑝 và giá trị nhỏ nhất giữa hai điểm trong các điểm bên trái 𝑝là 𝑑. Rõ ràng ta chỉ giữ lại những điểm có khoảng cách tới tọa độ 𝑥 của 𝑝 là 𝛿 < 𝑑 (hình trái)  Với điểm 𝑝 ta chỉ cần xét những điểm có chênh lệch cả 𝑥 và 𝑦 so với 𝑝 không quá 𝑑. (hình bên phải). Dễ thấy, vì 𝑑 là khoảng cách ngắn nhất giữa 2 điểm trong tập điểm bên trái đã xét nên chắc chắn có không quá 4 điểm như vậy. b. Cài đặt Sử dụng thêm cấu trúc set để lưu trữ các phần tử trong “vệt quét” hay nói cách khác là các phần tử có tọa độ x có khoảng cách tới tọa độ x của p đang xét nhỏ hơn giá trị d hiện tại. Đồng thời dễ ràng thêm, xóa và tìm kiếm các phần tử trong phạm vi 𝑝. 𝑦 − 𝑑 → 𝑝. 𝑦 + 𝑑. 7 Dưới đây là chương trình cài đặt tính cặp điểm gần nhấttheo thuật toán sweepline: #include #define sz(x) int(x.size()) #define MIN(x,y) if (x < y) x = y #define PB push_back #define mp make_pair #define F first #define S second #define Task "closestpair" #define maxn 200002 #define MOD 1000000007 #define remain(x) if (x > MOD) x -= MOD #define pii pair #define Y first #define X second using namespace std; pii a[maxn]; set S; double Distance(pii P1, pii P2) { double XX = P1.X - P2.X; double YY = P1.Y - P2.Y; return sqrt(XX*XX + YY*YY); } bool compareX(pii p1, pii p2) { return (p1.X < p2.X || (p1.X == p2.X && p1.Y < p2.Y)); } double Closest(pii a[], int n) { sort(a, a+n, compareX); S.insert(a[0]); int left = 0; 8 double ans = 1e10; for (int i = 1; i < n; i++) { int py = a[i].Y; int px = a[i].X; while (a[left].X < px - ans) S.erase(a[left++]); for (set :: iterator it = S.lower_bound(mp(1.0*py-ans, 1.0*px-ans)); it != S.end() && it->Y < ans+py; it++) ans = min (ans, Distance(*it, a[i])); S.insert(a[i]); } return ans; } int main() { ios_base::sync_with_stdio(0); freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y; printf("%0.5f", Closest(a,n)); return 0; } c. Đánh giá Mỗi điểm được thêm vào và xóa đi trong Set đúng 1 lần (𝑙𝑔𝑛) nên thời gian xử lí thêm vào và xóa đi trên Set là 𝑂(𝑛 𝑙𝑔𝑛). Với mỗi điểm 𝑝 việc tìm vị trí bắt đầu có tọa độ trong phạm vi 𝑝. 𝑦 − 𝑑 (hàm lower-bound) mất chi phí thời gian 𝑙𝑔𝑛. Số điểm để thuộc hình chữ nhật có thể xét luôn không vượt quá 4. Do vậy, tổng độ phức tạp để thực hiện giải thuật là 𝑂(𝑛𝑙𝑔𝑛). 9 III.Kết luận Với bài toán cặp điểm gần nhất, cả hai thuật toán chia để trị và sweepline đã trình bày trên đều có độ phức tạp là 𝑂(𝑛𝑙𝑔𝑛). Việc cài đặt thuật toán sweepline được cài đặt đơn giản, ngắn gọn hơn (khi sử dụng ngôn ngữ C++). Tuy nhiên, về mặt thời gian, thuật toán chia để trị lại thực hiện hiệu quả hơn do việc xử lý Set trong C++ tốn nhiều thời gian hơn. Tài liệu tham khảo 1. Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction To Algorithms, Third Edition. 2. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry Algorithms and Appliacitons, Third Edition. 10