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.
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]
- Trong bước này, chúng ta chia bài toán ban đầu thành các bài toán con. Mỗi bài toán con nên là một phần của bài toán ban đầu. Nói chung, bước này sử dụng phương pháp đệ qui để chia nhỏ các bài toán cho đến khi không thể chia thêm nữa. Khi đó, các bài toán con được gọi là "atomic – nguyên tử", nhưng chúng vẫn biểu diễn một phần nào đó của bài toán ban đầu.
Tiến trình 2: Giải bài toán con [Conquer/Solve]
- Trong bước này, các bài toán con được giải.
Quảng cáo
Tiến trình 3: Kết hợp lời giải [Merge/Combine]
- Sau khi các bài toán con đã được giải, trong bước này chúng ta sẽ kết hợp chúng một cách đệ qui để tìm ra giải pháp cho bài toán ban đầu.
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à:
- Làm thế nào để chia tách bài toán một cách hợp lý thành các bài toán con, bởi vì nếu các bài toán con được giải quyết bằng các thuật toán khác nhau thì sẽ rất phức tạp.
- Việc kết hợp lời giải các bài toán con được thực hiện như thế nào.
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]:
- Giải thuật sắp xếp trộn [Merge Sort]
- Giải thuật sắp xếp nhanh [Quick Sort]
- Giải thuật tìm kiếm nhị phân [Binary Search]
- Nhân ma trận của Strassen
- ...
Đã 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 //www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền //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: //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