- Phân tích Thiết kế Giải thuật Phạm Nguyên Khang BM.
- Khoa học máy tính Khoa CNTT – Đại học Cần Thơ
[email protected] 2 Nội dung • Mục tiêu • Từ bài toán đến chương trình • Các kỹ thuật thiết kế giải thuật ▫ Chia để trị ▫ Quay lui Vét cạn Nhánh cận ▫ Háu ăn/Tham ăn/Tham lam/… (Greedy.
- Quy hoạch động • Bài tập Mục tiêu • Biết các kỹ thuật thiết kế giải thuật: từ ý tưởng cho đến giải thuật chi tiết.
- Hiểu rõ nguyên lý của các kỹ thuật phân tích thiết kế giải thuật.
- Vận dụng kỹ thuật phân tích thiết kế để giải các bài toán thực tế: các bài toán dạng nào thì có thể áp dụng được kỹ thuật này.
- Từ bài toán đến chương trình Thiết kế Đánh giá Lập trình #include Bài toán … thực tế Giải thuật Giải thuật tốt Chương trình Kỹ thuật thiết kế giải Kỹ thuật phân tích Ngôn ngữ lập trình: thuật: đánh giá giải thuật: •PASCAL, C/C.
- Chia để trị, quy hoạch •Độ phức tạp của JAVA.
- động, háu ăn, nhánh giải thuật cận.
- •Cải tiến GT 5 Kỹ thuật chia để trị (ý tưởng.
- Cần phải giải bài toán có kích thước n.
- Ta chia bài toán ban đầu thành một số bài toán con đồng dạng với bài toán ban đầu có kích thước nhỏ hơn n.
- Giải các bài toán con được các lời giải con 3.
- Tổng hợp lời giải con lời giải của bài toán ban đầu.
- Đối với từng bài toán con, ta lại chia chúng thành các bài toán con nhỏ hơn nữa.
- Quá trình phân chia này sẽ dừng lại khi kích thước bài toán đủ nhỏ mà ta có thể giải dễ dàng Gọi là bài toán cơ sở.
- 6 Ví dụ: Quick sort • Giải thuật Quick Sort ▫ Sắp xếp dãy n số theo thứ tự tăng dần • Áp dụng kỹ thuật chia để trị: 1.
- Giải 2 bài toán con Sắp xếp dãy bên trái Sắp xếp dãy bên phải 3.
- Tổng hợp kết quả: Không cần tổng hợp 7 Ví dụ: Merge Sort • Giải thuật Merge Sort ▫ Sắp xếp dãy n số theo thứ tự tăng dần • Áp dụng kỹ thuật chia để trị: 1.
- Giải 2 bài toán con Sắp xếp dãy bên trái KQ1 Sắp xếp dãy bên phải KQ2 3.
- Tổng hợp kết quả: Trộn kết quả của 2 bài toán con 8 Kỹ thuật chia để trị (phân tích) Bài toán con Bài toán ban Đầu vào: Đầu ra: đầu n, m.
- ok 9 Kỹ thuật chia để trị (giải thuật) solve(n.
- if (n ñ nh ñ có th gi i ñư c) gi i bài toán KQ return KQ.
- else { Chia bài toán thành các bài toán con kích thư c n1, n2.
- //gi i bài toán con 1 KQ2 = solve(n2).
- //gi i bài toán con 2 … T ng h p các k t qu KQ1, KQ2.
- 10 Bài tập: Tìm phần tử trội • Cho mảng n phần tử • Phần tử trội: phần tử xuất hiện nhiều hơn n/2 lần • Tìm phần tử trội của 1 mảng n phần tử.
- Các phần tử chỉ có thể so sánh.
- Chia mảng thành 2 mảng con 11 Giảm để trị • Trường hợp đặc biệt của chia để trị • Áp dụng cho các bài toán tìm kiếm ▫ Tìm điểm chia cắt ▫ Tùy theo điều kiện (ví dụ.
- Quá trình chia cắt sẽ dừng khi không còn gì để chia ▫ Phải kiểm tra điều kiện trước khi chia cắt 12 Ví dụ • Tìm kiếm nhị phân trên một dãy đã sắp xếp ▫ Tìm phần tử có giá trị x trong mảng n phần tử.
- Phần tử đầu tiên có vị trí 1.
- Trả về vị trí tìm thấy, nếy không tìm thấy trả về 0 • Kỹ thuật giảm để trị ▫ Tìm phần tử giữa ▫ So sánh x với phần tử giữa ▫ Nếu bằng nhau Trả về vị trí giữa ▫ Nếu x nhỏ hơn Tìm nửa trái ▫ Nếu x lớn hơn Tìm nửa phải ▫ Trả về 0 13 Kỹ thuật quay lui (ý tưởng.
- Giải bài toán tối ưu ▫ Tìm một lời giải tối ưu trong số các lời giải ▫ Mỗi lời giải gồm thành n thành phần.
- Quá trình xây dựng một lời giải được xem như quá trình tìm n thành phần.
- Mỗi thành phần được tìm kiếm trong 1 bước.
- Ở mỗi bước, ta có thể dễ dàng chọn lựa một thành phần.
- Sau khi thực hiện đủ n bước ta được 1 lời giải 14 Kỹ thuật quay lui (phương pháp.
- Phương pháp ▫ Vét cạn (brute force) Tìm hết tất cả các lời giải Độ phức tạp thời gian lũy thừa ▫ Nhánh cận (branch and bound) Chỉ tìm những lời giải có lợi Cải tiến thời gian thực hiện 15 Vét cạn (ý tưởng.
- Gần giống chia để trị nhưng xây dựng lời giải từ dưới lên trong khi chia để trị là phân tích từ trên xuống • Một phương án/lời giải C.
- Gồm n thành phần C[1], C[2.
- Ở mỗi bước i, có một số lựa chọn cho thành phần i.
- Chọn một giá trị nào đó cho thành phần i 2.
- Gọi đệ quy để tìm thành phần i + 1 3.
- Hủy bỏ sự lựa chọn, quay lui lại bước 1 chọn giá trị khác cho thành phần i • Chú ý.
- Quá trình đệ quy kết thúc khi i > n ▫ Khi tìm được lời giải, so sánh với các lời trước đó để chọn lời giải tối ưu 16 Vét cạn (phân tích) Bước i tìm thành phần thứ i của lời giải C Lựa chọn 1 Bước i: Lựa chọn k Lựa chọn 2 Bước i+1 C[i.
- 18 Ví dụ: Bài toán cái ba lô • Có n món đồ, món đồ i có ▫ giá trị là v[i.
- Chọn các món đồ cho vào ba lô sao cho tổng giá trị lớn nhất và không vượt quá sức chứa của cái ba lô.
- 19 Bài toán cái ba lô (vét cạn.
- Giả sử ta đã có ở bước i z 1: V: tổng giá trị các món đồ đã được chọn G: tổng khối lượng các món đồ đã được chọn ▫ Chỉ có thể lựa chọn 0, 1, 2.
- hoặc n_max món đồ i Với n_max = (M < G)/g[i.
- Với mỗi lựa chọn j cho bước i Lựa chọn j cho bước i, cập nhật lại V, G (thêm vào) Gọi đệ quy cho bước i + 1 Hủy bỏ sự lựa chọn j, cập nhật lại V, G (bớt ra) 20 Bài toán cái ba lô (vét cạn) Lựa chọn 0 Lựa chọn k Lựa chọn 1 Chọn o Chọn k món đồ i Chọn 1 món món đồ i Bước i: đồ i Bước i+1 C[i.
- k 21 Bài toán cái ba lô (vét cạn) search (int i