Bài 32. Các kĩ thuật thiết kế thuật toán
Cho tới giờ, bạn luôn được đưa sẵn thuật toán để học: tìm kiếm nhị phân, sắp xếp nổi bọt, đệ quy - người ta trình bày cách làm, bạn hiểu rồi cài đặt lại. Bài này lật ngược tình thế: khi gặp một bài toán mới mà chưa ai đưa sẵn lời giải, bạn phải tự thiết kế thuật toán. Không có công thức máy móc cho việc đó, nhưng có bốn lối nghĩ quen thuộc mà người lập trình dùng đi dùng lại - vét cạn, chia để trị, tham lam và quy hoạch động - cùng với giới hạn của từng lối nghĩ.
Bắt đầu bằng một hình dung
Hè năm ngoái bạn phụ bán ở một quầy tạp hoá nhỏ. Ngày đầu tiên, khách đưa tờ 100 nghìn cho món hàng 22 nghìn. Bạn đứng thần ra trước ngăn kéo tiền lẻ: 78 nghìn thì gồm những tờ nào? Bạn ghép thử một tổ hợp, thấy hụt, gạt đi, ghép tổ hợp khác. Khách chờ.
Đến cuối tuần thì tay bạn tự động: rút tờ 50, rồi 20, rồi 5, rồi 2, rồi 1. Luôn tờ lớn nhất còn dùng được. Không cần thử gì nữa.
Cũng tuần đó, bạn nhặt thêm hai thói quen. Bảng giá dán trên tường xếp theo vần, nên khi khách hỏi giá một món, bạn không dò từ dòng đầu mà mở thẳng vào khoảng giữa rồi thu hẹp dần. Và có vài món khách hỏi năm lần một ngày, bạn chép giá ra mẩu giấy dán ngay cạnh máy tính tiền - hỏi lần thứ hai là đọc luôn, khỏi tra lại.
Bốn thói quen ấy, không hẹn mà gặp, chính là bốn lối nghĩ mà người viết chương trình dùng hằng ngày.
Nội dung bài học
- 1) Vét cạn - thử hết mọi khả năng
- 2) Chia để trị - bẻ nhỏ rồi ghép lại
- 3) Tham lam - chọn cái lợi nhất trước mắt
- 4) Quy hoạch động - tính một lần, dùng lại nhiều lần
Tóm tắt lý thuyết cần nhớ
- Vét cạn thử mọi khả năng nên luôn cho đáp án đúng, nhưng thường tốn
O(n^2)trở lên - hãy dùng nó cho dữ liệu nhỏ và làm bản đối chứng để kiểm tra các cách nhanh hơn. - Chia để trị bẻ bài toán thành các bài con cùng dạng, giải bằng đệ quy rồi ghép kết quả; tìm kiếm nhị phân
O(log n)và sắp xếp trộnO(n log n)là hai đại diện quen thuộc. - Tham lam chọn phương án tốt nhất trước mắt ở mỗi bước nên rất nhanh và rất gọn, nhưng không bảo đảm tối ưu - thối tiền 6 với bộ mệnh giá 4, 3, 1 là ví dụ nó chọn hụt.
- Quy hoạch động lưu lại kết quả của các bài toán con bị tính lặp để khỏi tính lại; nhờ memoization, Fibonacci tụt từ
O(2^n)xuốngO(n), đổi lại tốn thêm bộ nhớ. - Không có kĩ thuật nào tốt nhất cho mọi bài - hãy nhìn cấu trúc bài toán: chia đôi được thì chia để trị, bài con lặp lại thì quy hoạch động, còn khi bí thì cứ vét cạn để có đáp án đúng cái đã.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| brute force | brút phoóc | vét cạn Cách giải thử hết mọi khả năng rồi giữ lại cái thoả mãn. |
| divide and conquer | đi-vai en con-cơ | chia để trị Bẻ bài toán lớn thành các bài con cùng dạng nhưng nhỏ hơn, giải từng bài con rồi ghép kết quả lại. |
| greedy | gri-đi | tham lam Ở mỗi bước cứ chọn phương án trông tốt nhất ngay lúc đó rồi đi tiếp, không quay lại. |
| dynamic programming | đai-na-mích prô-gram-ming | quy hoạch động Kĩ thuật dành cho bài toán mà các bài con bị tính đi tính lại: lưu kết quả từng bài con lại để lần sau lấy ra dùng ngay. |
| memoization | me-mô-ai-dây-sần | ghi nhớ kết quả đã tính Mẹo cất kết quả của một lời gọi hàm vào bộ nhớ đệm để lần sau gọi với cùng dữ liệu thì đọc thẳng ra, khỏi tính lại. |
| merge sort | mớt-giơ sót | sắp xếp trộn Thuật toán sắp xếp theo lối chia để trị: chia dãy làm đôi, sắp xếp từng nửa rồi trộn hai nửa đã có thứ tự lại với nhau. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 26 câu, chấm điểm tự động và giải thích từng câu sai.
- Vét cạn (brute force)
- Tham lam (greedy)
- Chia để trị (divide and conquer)
- Quy hoạch động (dynamic programming)
- Vét cạn
- Chia để trị
- Tham lam
- Quy hoạch động
- Chia bài toán thành hai nửa rồi giải riêng từng nửa
- Ở mỗi bước chọn phương án tốt nhất tại thời điểm đó
- Lưu lại kết quả của các bài toán con bị tính lặp để dùng lại
- Liệt kê mọi khả năng rồi chọn cái thoả mãn
- a)Vét cạn chắc chắn tìm ra đáp án đúng nếu ta chấp nhận chờ đủ lâu, vì nó không bỏ sót khả năng nào.Đúng
- b)Tìm kiếm nhị phân dùng được trên mọi dãy số, không cần dãy phải sắp xếp trước.Sai
- c)Chia để trị giải các bài toán con cùng dạng với bài toán ban đầu, nên thường được cài đặt bằng đệ quy.Đúng
- d)Cách vét cạn tìm cặp số có tổng bằng S bằng hai vòng lặp lồng nhau có độ phức tạp O(log n).Sai
- (a) Đúng: vét cạn duyệt hết mọi khả năng nên không thể bỏ sót đáp án; nhược điểm của nó là thời gian chứ không phải tính đúng.
- (b) Sai: tìm kiếm nhị phân bắt buộc dãy phải sắp xếp sẵn, vì nếu không thì việc so sánh với phần tử giữa không cho phép loại bỏ nửa nào cả.
- (c) Đúng: bài con cùng dạng với bài lớn nên gọi lại chính hàm đó là cách cài đặt tự nhiên nhất.
- (d) Sai: dãy n số có n(n-1)/2 cặp nên hai vòng lặp lồng nhau là O(n^2), không phải O(log n).
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 26 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.