Thuật toán song song - Kỹ thuật thiết kế
Lựa chọn một kỹ thuật thiết kế thích hợp cho một thuật toán song song là nhiệm vụ khó khăn và quan trọng nhất. Hầu hết các vấn đề lập trình song song có thể có nhiều hơn một giải pháp. Trong chương này, chúng ta sẽ thảo luận về các kỹ thuật thiết kế sau đây cho các thuật toán song song -
- Phân chia và chinh phục
- Phương pháp tham lam
- Lập trình năng động
- Backtracking
- Chi nhánh & Giới hạn
- Lập trình tuyến tính
Phương pháp phân chia và chinh phục
Trong cách tiếp cận chia để trị, bài toán được chia thành nhiều bài toán nhỏ. Sau đó, các bài toán con được giải một cách đệ quy và kết hợp để có được lời giải của bài toán ban đầu.
Phương pháp phân chia và chinh phục bao gồm các bước sau ở mỗi cấp độ:
Divide - Bài toán ban đầu được chia thành các bài toán con.
Conquer - Các bài toán con được giải một cách đệ quy.
Combine - Các lời giải của các bài toán con được kết hợp với nhau để có được lời giải của bài toán ban đầu.
Phương pháp phân chia và chinh phục được áp dụng trong các thuật toán sau:
- Tìm kiếm nhị phân
- Sắp xếp nhanh chóng
- Hợp nhất sắp xếp
- Phép nhân số nguyên
- Đảo ngược ma trận
- Phép nhân ma trận
Phương pháp tham lam
Trong thuật toán tham lam của giải pháp tối ưu hóa, giải pháp tốt nhất được chọn bất cứ lúc nào. Một thuật toán tham lam rất dễ áp dụng cho các bài toán phức tạp. Nó quyết định bước nào sẽ đưa ra giải pháp chính xác nhất trong bước tiếp theo.
Thuật toán này được gọi là greedybởi vì khi giải pháp tối ưu cho thể hiện nhỏ hơn được cung cấp, thuật toán không xem xét tổng thể chương trình như một tổng thể. Một khi một giải pháp được xem xét, thuật toán tham lam không bao giờ xem xét lại cùng một giải pháp.
Một thuật toán tham lam hoạt động tạo ra một cách đệ quy một nhóm các đối tượng từ các phần thành phần nhỏ nhất có thể. Đệ quy là một thủ tục để giải quyết một vấn đề trong đó giải pháp cho một vấn đề cụ thể phụ thuộc vào giải pháp của ví dụ nhỏ hơn của vấn đề đó.
Lập trình năng động
Lập trình động là một kỹ thuật tối ưu hóa, chia vấn đề thành các vấn đề con nhỏ hơn và sau khi giải quyết từng vấn đề con, lập trình động kết hợp tất cả các giải pháp để có được giải pháp cuối cùng. Không giống như phương pháp chia và chinh phục, lập trình động sử dụng lại lời giải cho các bài toán con nhiều lần.
Thuật toán đệ quy cho Dòng Fibonacci là một ví dụ về lập trình động.
Thuật toán bẻ khóa
Backtracking là một kỹ thuật tối ưu hóa để giải quyết các vấn đề tổ hợp. Nó được áp dụng cho cả các bài toán lập trình và trong cuộc sống thực. Bài toán tám nữ hoàng, câu đố Sudoku và đi qua một mê cung là những ví dụ phổ biến trong đó thuật toán quay lui được sử dụng.
Trong backtracking, chúng tôi bắt đầu với một giải pháp khả thi, đáp ứng tất cả các điều kiện bắt buộc. Sau đó, chúng ta chuyển sang cấp độ tiếp theo và nếu cấp độ đó không tạo ra giải pháp thỏa đáng, chúng ta quay trở lại một cấp độ và bắt đầu với một tùy chọn mới.
Chi nhánh và ràng buộc
Thuật toán rẽ nhánh và ràng buộc là một kỹ thuật tối ưu hóa để có được giải pháp tối ưu cho vấn đề. Nó tìm kiếm giải pháp tốt nhất cho một vấn đề nhất định trong toàn bộ không gian của giải pháp. Các giới hạn trong hàm cần tối ưu hóa được hợp nhất với giá trị của giải pháp tốt nhất mới nhất. Nó cho phép thuật toán tìm thấy hoàn toàn các phần của không gian giải pháp.
Mục đích của tìm kiếm nhánh và tìm kiếm ràng buộc là duy trì đường dẫn chi phí thấp nhất đến mục tiêu. Khi một giải pháp được tìm thấy, nó có thể tiếp tục cải tiến giải pháp. Tìm kiếm nhánh và liên kết được thực hiện trong tìm kiếm giới hạn sâu và tìm kiếm theo chiều sâu trước tiên.
Lập trình tuyến tính
Lập trình tuyến tính mô tả nhiều loại công việc tối ưu hóa trong đó cả tiêu chí tối ưu hóa và các ràng buộc đều là các hàm tuyến tính. Đó là một kỹ thuật để có được kết quả tốt nhất như lợi nhuận tối đa, con đường ngắn nhất hoặc chi phí thấp nhất.
Trong lập trình này, chúng ta có một tập hợp các biến và chúng ta phải gán giá trị tuyệt đối cho chúng để thỏa mãn một tập phương trình tuyến tính và để tối đa hóa hoặc tối thiểu hóa một hàm mục tiêu tuyến tính đã cho.