Bài giảng Phân tích và thiết kế giải thuật

Phân tích thiết kế giải thuật

Phạm Nguyên Khang, Đỗ Thanh Nghị

Khoa CNTT – Đại học Cần Thơ

{pnkhang,dtnghi}@cit.ctu.edu.vn

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

3

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.

4

Từ bài toán đến chương trình

Thiết kế

Lập trình

Đánh giá

#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 phân tích

đánh giá giải thuật:

Ngôn ngữ lập trình:

Kỹ thuật thiết kế giải

thuật:

Chia để trị, quy hoạch

động, háu ăn, nhánh

cận, …

•

PASCAL, C/C++,

•

Độ phức tạp của

giải thuật

JAVA, …

•

Cải tiến GT

5

Kỹ thuật chia để trị (ý tưởng)

•

Yêu cầu:

–

Cần phải giải bài toán có kích thước n.

•

Phương pháp:

–

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

Tổng hợp lời giải con  lời giải của bài toán ban đầu.

–

•.

Chú ý:

–

Đố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

Kỹ thuật chia để trị (phân tích)

Bài toán con

Bài toán ban

Đầu vào: Đầu ra:

n, m, …

đầu

o

Đầu vào:

n1, m2,

…

Đầu vào:

n2, m2,

…

Đầu vào:

nk, mk,

…

Đầu ra:

ok

o1

o2

Tổng hợp kết quả:

Tính o từ o1, o2, …, ok

7

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, …

KQ1 = solve(n1); //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, …  KQ

return KQ;

}

8

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ị:

–

Chia dãy n số thành 2 dãy con

●

Trước khi chia phải phân hoạch

–

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

–

Tổng hợp kết quả:

●

Không cần tổng hợp

9

Ví dụ: Quick sort

10

Độ phức tạp của Quick sort

•

Xấu nhất

–

Dãy n số đã đúng thứ tự tăng dần

–

Phân hoạch bị lệch: phần tử chốt là phần tử nhỏ

nhất => cần n phép so sánh để biết nó là phần

tử đầu tiên

2

–

Độ phức tạp trong trường hợp này là: O(n )

•

Tốt nhất:

–

Phân hoạch cân bằng: phần tử chốt là phần tử

giữa dãy => C(n) = 2C(n/2) + n

Độ phức tạp trong trường hợp này là: O(nlogn)

–

Chứng minh độ phức tạp trung bình: O(nlogn)

11

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ị:

–

Chia dãy n số thành 2 dãy con

●

Không cần phân hoạch, cứ cắt dãy số ra làm 2

–

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

–

Tổng hợp kết quả:

●

Trộn kết quả (theo thứ tự) của 2 bài toán con

12

Ví dụ: Merge Sort

13

Độ phức tạp của Merge sort

•

Sắp xếp dãy n số

–

Số lần so sánh: C(n) = 2C(n/2) + n

Độ phức tạp là: O(nlogn)

–

Cần thêm n đơn vị bộ nhớ cho lưu trữ

14

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 == hoặc !=

Gợi ý:

–

Chia mảng thành 2 mảng con

15

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ụ: =, <, >) mà chọn

phần xử lý phù hợp

•

Chú ý:

–

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

16

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ếu 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

17

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.

●

Các bước phải có dạng giống nhau.

Ở 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

18

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

19

Vét cạn (ý tưởng)

•

Ý 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], …, C[n]

Ở 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

Gọi đệ quy để tìm thành phần i + 1

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

20

Bước i tìm thành phần

thứ i của lời giải C

Vét cạn (phân tích)

Lựa chọn 1

Lựa chọn k

Bước i:

Lựa chọn 2

Bước i+1 C[i] = 1

Bước i+1 C[i] = 2

Bước i+1 C[i] = k

Bài giảng Phân tích và thiết kế giải thuật - Phạm Nguyên Khang