Bài toán diff thuật toán chia để trị năm 2024
|
Phương pháp chia để trị (Divide and Conquer) là một phương pháp quan trọng trong việc thiết kế các giải thuật. Ý tưởng của phương pháp này khá đơn giản và rất dễ hiểu: Khi cần giải quyết một bài toán, ta sẽ tiến hành chia bài toán đó thành các bài toán con nhỏ hơn. Tiếp tục chia cho đến khi các bài toán nhỏ này không thể chia thêm nữa, khi đó ta sẽ giải quyết các bài toán nhỏ nhất này và cuối cùng kết hợp giải pháp của tất cả các bài toán nhỏ để tìm ra giải pháp của bài toán ban đầu. Show Nói chung, bạn có thể hiểu giải thuật chia để trị (Divide and Conquer) qua 3 tiến trình sau: Tiến trình 1: Chia nhỏ (Divide/Break)
Tiến trình 2: Giải bài toán con (Conquer/Solve)
Quảng cáo Tiến trình 3: Kết hợp lời giải (Merge/Combine)
Hạn chế của giải thuật chia để trị (Devide and Conquer)Giải thuật chia để trị tồn tại hai hạn chế, đó là:
Quảng cáo Ví dụ giải thuật chia để trịDưới đây là một số giải thuật được xây dựng dựa trên phương pháp chia để trị (Divide and Conquer):
Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS. Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube: Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi. Tìm minDistance trong strip[]. Bước này mới nhìn có vẽ tốn O(n^2) nhưng thực chất chỉ cần O(n), vì mỗi điểm ta chỉ cần tìm khoản cách với 5 đến 7 hàng xóm gần nhất của nó. Bước 7. So sánh d và minDistance để tìm lời giải cuối cùng. Thuật toán trên thể hiện bằng mã C++ như sau: // A divide and conquer program in C++ // to find the smallest distance from a // given set of points. include using namespace std; // A structure to represent a Point in 2D plane class Point { public: int x, y; }; /* Following two functions are needed for library function qsort(). Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */ // Needed to sort array of points // according to X coordinate int compareX(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->x - p2->x); } // Needed to sort array of points according to Y coordinate int compareY(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->y - p2->y); } // A utility function to find the // distance between two points float dist(Point p1, Point p2) { return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y) ); } // A Brute Force method to return the // smallest distance between two points // in P[] of size n float bruteForce(Point P[], int n) { float min = FLT_MAX; for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); return min; } // A utility function to find // minimum of two float values float min(float x, float y) { return (x < y)? x : y; } // A utility function to find the // distance between the closest points of // strip of given size. All points in // strip[] are sorted according to // y coordinate. They all have an upper // bound on minimum distance as d. // Note that this method seems to be // a O(n^2) method, but it's a O(n) // method as the inner loop runs at most 6 times float stripClosest(Point strip[], int size, float d) { float min = d; // Initialize the minimum distance as d qsort(strip, size, sizeof(Point), compareY); // Pick all points one by one and try the next points till the difference // between y coordinates is smaller than d. // This is a proven fact that this loop runs at most 6 times for (int i = 0; i < size; ++i) for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); return min; } // A recursive function to find the // smallest distance. The array P contains // all points sorted according to x coordinate float closestUtil(Point P[], int n) { // If there are 2 or 3 points, then use brute force if (n <= 3) return bruteForce(P, n); // Find the middle point int mid = n/2; Point midPoint = P[mid]; // Consider the vertical line passing // through the middle point calculate // the smallest distance dl on left // of middle point and dr on right side float dl = closestUtil(P, mid); float dr = closestUtil(P + mid, n - mid); // Find the smaller of two distances float d = min(dl, dr); // Build an array strip[] that contains // points close (closer than d) // to the line passing through the middle point Point strip[n]; int j = 0; for (int i = 0; i < n; i++) if (abs(P[i].x - midPoint.x) < d) strip[j] = P[i], j++; // Find the closest points in strip. // Return the minimum of d and closest // distance is strip[] return min(d, stripClosest(strip, j, d) ); } // The main function that finds the smallest distance // This method mainly uses closestUtil() float closest(Point P[], int n) { qsort(P, n, sizeof(Point), compareX); // Use recursive function closestUtil() // to find the smallest distance return closestUtil(P, n); } // Driver code int main() { Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; int n = sizeof(P) / sizeof(P[0]); cout << "The smallest distance is " << closest(P, n); return 0; } // Nguồn: This code is contributed by rathbhupendra dẫn từ GeeksforGeeks.com Độ phức tạp: Gọi thời gian thực hiện giải tuật là T(n).
Tổng: T(n) = 2T(n/2) + O(n) + O(nlogn) + O(n) \= 2T(n/2) + O(nlogn) \= T(n*logn*logn) Đề dễ hiểu bước biến đổi này, chúng ta hình dung độ phực tạp của bước sắp xếp mảng strip[], quá trình này lặp lại mỗi level khi ta gộp mảng trong quá trình chia để trị (logn bước) nên tổng thời giản là O(logn*nlogn) = O(n(logn)^2) |
