Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 1, Phần 3: Thuật toán đê quy - Nguyễn Duy Hiệp
1/10/2011
REVIEW
Xác định mối quan hệ giữa các cặp hàm ꢀꢁꢂꢃ và ꢄꢁꢂꢃ sau
đây
aꢃ ꢀ ꢂ ꢅ ꢂꢆ.ꢇ ꢈ 3ꢁꢂ ꢉ 1ꢃ, ꢄ ꢂ ꢅ 6ꢂ
bꢃ ꢀ ꢂ ꢅ ꢂꢆ ꢈ 3 ꢂ ꢉ 1ꢃ, ꢄ ꢂ ꢅ ꢂꢊ
cꢃ ꢀ ꢂ ꢅ 2ꢂꢆ.ꢇ ꢈ ꢂ, ꢄ ꢂ ꢅ ꢂꢇ
THUẬT TOÁN ĐÊ QUY
Nội dung
Định nghĩa đệ quy
Đối tượng bao gồm chính nó
hoặc được định nghĩa dưới
dạng chính nó.
Định nghĩa đệ quy
Thuật toán đệ quy
VD. Định nghĩa một công thức hợp
lệ của các biến, số và các phép toán
ꢈ, ꢉ,∗,/, ^
ꢋ là công thức hợp lệ nếu ꢋ là
biến hoặc số
Nếu ꢀ, ꢄ là công thức hợp lệ thì
ꢁꢀ ꢈ ꢄꢃ, ꢁꢀ ꢉ ꢄꢃ, ꢁꢀ ∗ ꢄꢃ, ꢁꢀ/ꢄꢃ,
ꢁꢀ^ꢄꢃ cũng là công thức hợp lệ
Phân tích thuật toán đệ quy
Đệ quy có nhớ
Thuật toán quay lui (backtracking algorithm)
1
1/10/2011
Hàm được định nghĩa đệ quy
Định nghĩa đệ quy
Mọi định nghĩa đệ quy đều gồm 2 phần
Một trường hợp cơ sở (nhỏ nhất) có thể xử lý trực tiếp mà không
cần đệ quy, và
1
ꢂếꢍ ꢂ ꢅ 0
ꢂếꢍ ꢂ ꢏ 0
ꢂ! ꢅ ꢌ
ꢂ ꢎ ꢂ ꢉ 1 !
Một phương thức tổng quát mà biến đổi một trường hợp cụ thể về
các trường hợp nhỏ hơn. Do đó biến đổi các trường hợp cho đến
khi về trường hợp cơ sở.
1
ꢂếꢍ ꢂ ꢅ 1, 2
ꢐꢑꢒ ꢂ ꢅ ꢌ
ꢐꢑꢒ ꢂ ꢉ 1 ꢈ ꢐꢑꢒ ꢂ ꢉ 2 ꢂếꢍ ꢂ ꢏ 2
0
1
ꢂếꢍ ꢂ ꢅ 0
ꢂếꢍ ꢂ ꢅ 1
ꢓ ꢂ ꢅ ꢔ
2ꢓ ꢂ ꢉ 1 ꢈ ꢓ ꢂ ꢉ 2 ꢂếꢍ ꢂ ꢏ 1
Danh sách ban đầu
Thuật toán đệ quy
Thuật toán có chứa lời gọi đệ quy đến chính nó với đầu
vào kích thước nhỏ hơn.
Chia lần 1
Chia lần 2
VD. Sắp xếp trộn – MergeSort
MergeSort(int A[], int start, int end)
{
Chia lần 3
if(start<end)
{
Danh sách sau
khi chia
int mid = (start+end)/2;
MergeSort(A, start, mid);
MergeSort(A, mid+1, end);
Trộn lần 1
Merge(A,start,mid,end);
Trộn lần 2
Trộn lần 3
}
}
2
1/10/2011
Thuật toán đệ quy
Phân tích thuật toán đệ quy
Mô tả thời gian thực hiện của thuật toán đệ quy bằng
công thức đệ quy
Giải công thức đệ quy để tìm Θ hoặc Ο bằng:
Phương pháp thay thế
VD. MergeSort có
Ο 1
ꢂ
ꢂếꢍ ꢂ ꢅ 1
ꢂếꢍ ꢂ ꢏ 1
ꢕ ꢂ ꢅ ꢖ
2ꢕ
Phương pháp cây đệ quy
Dùng định lý thợ
ꢈ Ο ꢂ
2
Bỏ qua ꢕꢁꢂꢃ với các giá trị n nhỏ (coi là hằng). Ta có thể viết lại
ꢕꢁꢂꢃ là
ꢂ
ꢕ ꢂ ꢅ 2ꢕ
ꢈ Ο ꢂ
2
Phương pháp thay thế
Gồm 2 bước:
Đoán dạng của lời giải
Sử dụng quy nạp toán học để tìm ra các hằng và chứng minh
lời giải
Xác định cận trên của công thức đệ quy
ꢂ
ꢕ ꢂ ꢅ 2ꢕ
ꢈ ꢂ
ꢗ
Phương pháp thay thế
2
Đoán ꢕ ꢂ ꢅ Οꢁꢂlogꢂꢃ
Cần chứng minh ꢕꢁꢂꢃ ꢘ ꢙꢂlogꢂ với hằng số ꢂ ꢏ 0 được chọn
phù hợp
3
1/10/2011
Phương pháp thay thế
Phương pháp thay thế
Giả sử ꢕꢁꢂꢃ ꢘ ꢙꢂlogꢂ đúng với ꢚ⁄ꢆ tức là
ꢕꢁ ⁄ꢆ ꢃ ꢘ ꢙ ⁄ꢆ log ⁄ꢆ . Thay vào ꢕ ꢂ
Giả sử trường hợp cơ sở ꢕ 1 ꢅ 1 nhưng ꢙ1log1 ꢅ 0.
Kết quả quy nạp sai trong trường hợp cơ sở.
ꢚ
ꢚ
ꢚ
Ta có thể giải quyết vấn đề này khi sử dụng các ký hiệu
tiệm cận (Ο, Ω, Θ)
ꢕ ꢂ ꢅ ꢙꢂlogꢂ với ꢂ ꢛ ꢂꢜ
Chọn ꢂꢜ sao cho với mọi ꢂ ꢛ ꢂꢜ thì kết quả luôn đúng
VD với ꢂ ꢅ 2 thì ꢕ 2 ꢅ 2ꢕ 1 ꢈ 2 ꢅ 4 ꢝ ꢙ2log2 với
hằng số ꢙ ta chọn đủ lớn (VD ꢙ ꢅ 5).
ꢚ
ꢚ
ꢕ ꢂ ꢘ 2 ꢙ ⁄ꢆ log ⁄ꢆ ꢈ ꢂ
ꢘ ꢙꢂlog ꢚ⁄ꢆ ꢈ ꢂ ꢅ ꢙꢂlogꢂ ꢉ ꢙꢂlog2 ꢈ ꢂ
ꢘ ꢙꢂlogꢂ
Đúng với ꢙ ꢛ 1
Ta cần chỉ ra kết quả quy nạp này đúng trong mọi trường
hợp (đúng cả trong trường hợp cơ sở).
Vậy ꢕ ꢂ ꢅ Οꢁꢂlogꢂꢃ với ꢙ ꢅ 5 và ꢂ ꢛ 2
Phương pháp thay thế
Phương pháp thay thế
Đoán dạng lời giải tốt:
Thêm bớt 1 hằng số không làm thay đổi dạng kết quả
ꢕ ꢂ ꢅ 2ꢕ ꢚꢆ ꢈ 12 ꢈ 3ꢂ vẫn có dạng Οꢁꢂlogꢂꢃ
Tránh lỗi hay mắc
ꢂ
ꢕ ꢂ ꢘ 2 ꢙ
ꢈ ꢂ ꢘ ꢙꢂ ꢈ ꢂ ꢅ Οꢁꢂꢃ
ꢗ
2
Sai do ta không chứng minh ꢕꢁꢂꢃ ꢘ ꢙꢂ
Thay đổi biến
Ban đầu nới lỏng cận trên, dưới để chứng minh rồi sau đó
giảm dần.
ꢕ ꢂ ꢅ 2ꢕ ꢂ ꢈ logꢂ
đặt ꢞ ꢅ logꢂ ta có ꢕ 2ꢟ ꢅ 2ꢕ 2ꢠ ꢈ ꢞ
đặt ꢢ ꢞ ꢅ ꢕꢁ2ꢟꢃ ta có ꢢ ꢞ ꢅ 2ꢢ
⁄
ꢡ
ꢟ
VD. Với ꢕꢁꢂꢃ trong ví dụ ban đầu ta có thể chọn Ωꢁꢂꢃ và
Οꢁꢂꢆꢃ rồi sau đó giảm giới hạn trên, tăng giới hạn dưới cho
tới khi hội tụ về giá trị chính xác
⁄
ꢈ ꢞ ꢅ
ꢆ
Ο ꢞlogꢞ ꢅ Οꢁlogꢂ loglogꢂꢃ
4
1/10/2011
Một số tính chất của hàm mũ, loga, giai thừa
Ta có các công thức:
a
a = blog
;
logb a = 1/(loga b)
b
Do đó, trong ký hiệu tiệm cận cơ số của log là không quan trọng:
O(lg n) = O(ln n) = O(log n)
Ví dụ. Chứng minh rằng
Công thức Stirling:
ꢚ
ꢕ ꢂ ꢅ 2ꢕ
ꢈ 1 là Οꢁlogꢂꢃ
n
ꢆ
n
e
1
n! 2n
1
n
Giai thừa và hàm mũ:
2n < n! < nn với n > 5 ;
log n! = (n log n).
Vấn đề với phương pháp thay thế
Ví dụ 2 (tiếp)
T(n) = 1
T(n) = 4T(n/2) + n
n=1
n>1
T(n) = 1
T(n) = 4T(n/2) + n
n=1
n>1
Dự đoán (chặt hơn!):
T(n) cn2 n>n0
Sử dụng dự đoán chính xác hơn.
Chuyển qui nạp:
Giả sử T(k) ck2, k<n. Chứng minh T(n) cn2.
Trừ bớt đi một số hạng tăng chậm (là một kỹ thuật hay dùng).
T(n) = 4T(n/2) + n
4c(n/2)2 + n
Dự đoán:
T(n) cn2 - dn n>n0
= c
Không cn2 !
Giả sử T(k) ck2 - dn, k<n. Cần CM T(n) cn2 - dn.
5
1/10/2011
Ví dụ 2 (tiếp)
Ví dụ 2 (tiếp)
T(n) = 1
T(n) = 4T(n/2) + n
n=1
n>1
T(n) = 1
T(n) = 4T(n/2) + n
n=1
n>1
Dự đoán:
Dự đoán:
T(n) cn2 - dn n>n0
T(n) cn2 - dn n>n0
Giả sử T(k) ck2 - dn, k<n. CM T(n) cn2 - dn.
Khi n=1:
Giả sử T(k) ck2 - dn, k<n. CM T(n) cn2 - dn.
Chuyển qui nạp, n>1:
T(n) = 4T(n/2) + n
4(c(n/2)2 ‐ d(n/2)) + n
= cn2 ‐ 2dn + n
= cn2 ‐ dn ‐ (dn ‐ n)
cn2 ‐ d*n
(định nghĩa)
(qui nạp)
(biến đổi)
(biến đổi)
(Chọn d1)
T(n) = 1
Theo định nghĩa.
1 c‐d
Có thể chọn c, d thích hợp để có bất đẳng thức này
Ví dụ 2 (tiếp)
T(n) = 1
T(n) = 4T(n/2) + n
n=1
n>1
Đã chứng minh:
T(n) 2n2 – 1n n>0
Phương pháp cây đệ quy
Vậy, T(n) = O(n2).
6
1/10/2011
Phương pháp cây đệ quy
Phương pháp cây đệ quy
ꢚ
ꢊ
ꢆꢚ
ꢊ
Xét công thức đệ quy ꢕ ꢂ ꢅ ꢕ
ꢈ ꢕ
ꢈ Οꢁꢂꢃ
Cây đệ quy cho mergeSort
ꢣ 1
ꢂếꢍ ꢂ ꢅ 1
ꢂếꢍ ꢂ ꢏ 1
ꢕ ꢂ ꢅ ꢖ
2ꢕ
ꢚ
ꢈ ꢣ ꢂ
ꢆ
Phương pháp cây đệ quy
Phương pháp cây đệ quy
Dùng phương pháp thay thế để chứng minh lời giải công
thức đệ quy tìm được.
ꢚ
ꢊ
ꢆꢚ
ꢊ
VD. ꢕ ꢂ ꢅ ꢕ
ꢚ
ꢕ ꢂ ꢘ ꢕ
ꢊ
ꢈ ꢕ
ꢈ Ο ꢂ ꢅ Οꢁꢂlogꢂꢃ
Bài tập: Xác định một cận trên tốt cho công thức đệ quy
ꢆꢚ
ꢊ
ꢈ ꢕ
ꢈ ꢙꢂ
ꢚ
ꢕ ꢂ ꢅ 3ꢕ
ꢈ ꢂ
ꢘ ꢤ ꢚꢊ log ꢚꢊ ꢈ ꢤ ꢆꢚ log ꢆꢚ ꢈ ꢙꢂ
ꢆ
ꢊ
ꢊ
dùng phương pháp thế để xác nhận lại kết quả.
ꢤꢂ
ꢤꢂ
2ꢤꢂ
2ꢤꢂ
3
ꢅ
log ꢂ ꢉ
log 3 ꢈ
log 2ꢂ ꢉ
log 3 ꢈ ꢙꢂ
3
3
3
2ꢤꢂ
ꢅ ꢤꢂ log ꢂ ꢉ ꢤꢂ log 3 ꢈ
log 2 ꢈ ꢙꢂ
3
ꢘ ꢤꢂ log ꢂ
ꢥ
Với ꢤ ꢛ ꢦꢧꢨ ꢊꢩ (chú ý log 2 ꢅ 1)
ꢡ
ꢪ
7
1/10/2011
Dùng định lý thợ
Dùng để giải các công thức đệ quy dạng
ꢂ
ꢕ ꢂ ꢅ ꢫꢕ
ꢈ ꢀ ꢂ ,
ꢒ
ꢬꢭꢮꢂꢄ đó ꢫ ꢛ 1, ꢒ ꢏ 1, ꢀ ꢂ ꢯà ꢰàꢞ ꢬꢑệꢞ ꢙậꢂ ꢤươꢂꢄ
một cách hiệu quả.
Bài toán ban đầu được chia thành ꢱ bài toán con có kích
thước mỗi bài là ꢲ , chi phí để tổng hợp các bài toán con
là ꢴꢁꢲꢃ
⁄
ꢳ
Định lý thợ
Master theorem
VD. Thuật toán sắp xếp trộn
chia thành 2 bài toán con, kích thước ꢂ/2. Chi phí tổng hợp 2 bài
toán con là Οꢁꢂꢃ
Dùng định lý thợ
Dùng định lý thợ
Áp dụng định lý thợ:
Định lý thợ (Master Theorem)
ꢚ
ꢕ ꢂ ꢅ 9ꢕ
ꢈ ꢂ.
ꢫ ꢛ 1, ꢒ ꢏ 1 là các hằng số, ꢀꢁꢂꢃ là một hàm. ꢕꢁꢂꢃ định nghĩa đệ
quy trên các tham số không âm
ꢊ
ꢫ ꢅ 9, ꢒ ꢅ 3 ꢻà ꢀ ꢂ ꢅ ꢂ ta có ꢂꢦꢧꢨ ≡ ꢂꢦꢧꢨ ꢅ ꢂꢆ. Đây
ꢶ
ꢼ
ꢪ
ꢸ
ꢚ
ꢚ
ꢕ ꢂ ꢅ ꢫꢕ
⁄
ꢵ
ꢈ ꢀꢁꢂꢃ, trong đó ꢚ ꢵ có thể hiểu là
hoặc
⁄
ꢵ
là trường hợp 1 (với ꢹ ꢅ 1) do đó ꢕ ꢂ ꢅ Θꢁꢂꢆꢃ
⁄
ꢵ
⁄
ꢚ
ꢆꢚ
. Thì ꢕꢁꢂꢃ có thể bị giới hạn một cách tiệm cận như sau:
ꢕ ꢂ ꢅ ꢕ
ꢈ 1.
ꢊ
ꢫ ꢅ 1, ꢒ ꢅ 3/2 và ꢀ ꢂ ꢅ 1 ta có ꢂꢦꢧꢨ
ꢅ ꢂꢜ ꢅ 1. Đây là
ꢽ
ꢪ/ꢡ
Nếu ꢀ ꢂ ꢅ Οꢁꢂꢦꢧꢨ ꢶꢩꢷꢃ, với hằng ꢹ ꢏ 0 thì ꢕ ꢂ ꢅ Θꢁꢂꢦꢧꢨ ꢶꢃ
ꢸ
ꢸ
trường hợp 2, do đó ꢕ ꢂ ꢅ Θꢁlog ꢂꢃ
Nếu ꢀ ꢂ ꢅ Οꢁꢂꢦꢧꢨ ꢶꢃ thì ꢕ ꢂ ꢅ Θꢁꢂꢦꢧꢨ ꢶ log ꢂꢃ
ꢸ
ꢸ
ꢚ
ꢕ ꢂ ꢅ 3ꢕ
ꢈ ꢂ log ꢂ
ꢾ
Nếu ꢀ ꢂ ꢅ Ωꢁꢂꢦꢧꢨ ꢶꢺꢷꢃ, với hằng ꢹ ꢏ 0, và nếu
ꢸ
ꢫ ꢅ 3, ꢒ ꢅ 4 và ꢀ ꢂ ꢅ ꢂ log ꢂ ta có ꢂꢦꢧꢨ ≡ ꢂꢦꢧꢨ
ꢅ
ꢶ
ꢊ
ꢿ
ꢸ
ꢚ
ꢫꢀ
ꢝ ꢙꢀꢁꢂꢃ với hằng ꢙ ꢝ 1 và với mọi n đủ lớn thì
⁄
Οꢁꢂꢜ.ꣀꢼꢊꢃ, ꢀ ꢂ ꢅ Ωꢁꢂꢦꢧꢨ ꢊꢺꢷꢃ với ꢹ ꣁ 0.2, ꢫꢀ
ꢝ
ꢚ
ꢵ
ꢿ
⁄
ꢵ
ꢕ ꢂ ꢅ Θꢁꢀꢁꢂꢃꢃ
ꢚ
ꢾ
ꢙꢀ ꢂ ≡ 3ꢀ
ꢝ ꢙꢀꢁꢂ log ꢂꢃ với ꢙ ꢅ ꢊꢾ do vậy ꢕ ꢂ ꢅ
Θꢁꢂ log ꢂꢃ (TH3)
8
1/10/2011
Dùng định lý thợ
Chú ý: Không phải trường hợp nào cũng áp dụng được
định lý thợ !
ꢚ
VD. ꢕ ꢂ ꢅ 2ꢕ
ꢈ ꢂ log ꢂ
ꢆ
ꢫ ꢅ 2, ꢒ ꢅ 2 và ꢀ ꢂ ꢅ ꢂ log ꢂ
ꢶ
ꢆ
ꢂꢦꢧꢨ ≡ ꢂꢦꢧꢨ ꢅ ꢂ do đó có vẻ áp dụng trường hợp 3.
ꢡ
ꢸ
ꢚ
Đệ quy có nhớ
Tuy nhiên ꢀ ꢂ ꢅ ꢂ log ꢂ tiệm cận lớn hơn 2ꢀ
mọi hằng số ꢹ do đó không thể áp dụng được.
với
ꢆ
Đệ quy có nhớ
Trong thuật toán đệ quy, những bài toán con có thể được
giải đi giải lại nhiều lần!
VD. Tính số Fibonacci
1
ꢂếꢍ ꢂ ꢅ 0,1
ꢀ ꢂ ꢅ ꢌ
ꢀ ꢂ ꢉ 1 ꢈ ꢀ ꢂ ꢉ 2 ꢂếꢍ ꢂ ꢛ 2
Tính ꢀꢁ5ꢃ
Ghi nhận lời giải: dùng mảng
Khi gặp bài toán con cần giải: Kiểm tra xem bài toán con
đã được giải chưa:
Thuật toán quay lui
Back‐tracking algorithm
Nếu đã giải: lấy kết quả
Ngược lại, giải bài toán con và cập nhật lời giải vào bảng
9
1/10/2011
Thuật toán quay lui
Thuật toán quay lui
Bài toán 8 con hậu: “Hãy xếp 8 con hậu trên bàn cờ 8x8
sao cho chúng không thể ăn lẫn nhau”
Thuật toán xếp hậu: đặt lần lượt các quân hậu lên bàn cờ
(theo 1 cách nào đó) sao cho quân hậu đặt sau không ăn
được quân đã đặt trước đó.
Thuật toán quay lui
Thuật toán quay lui
solve_from (Current_config)
if Current_config đã chứa đủ 8 hậu
Dead end: trạng thái chưa kết thúc, nhưng ta không thể
đặt thêm được 1 quân hậu nào nữa.
print Current_config
Khi rơi vào trạng thái dead end ta phải tiến hành quay lui
(backtrack) lại lựa chọn gần nhất để thử một khả năng có
thể khác.
else
Với tập p các ô trên bàn cờ mà chưa bị ảnh hưởng bởi Current_config
{
Thêm 1 quân hậu vào p;
Cập nhật lại Current_config
solve_from(Current_config);
Loại bỏ quân hậu khỏi p của Current_config;
}
10
1/10/2011
Thuật toán quay lui
Bài toán 8 con hậu
Thuật toán quay lui – backtracking algorithm:
Thử tìm kiếm lời giải đầy đủ cho bài toán từ việc xây dựng
lời giải bộ phận, trong đó lời giải bộ phận phải luôn phù
hợp với yêu cầu bài toán.
Trong quá trình thực hiện, thuật toán mở rộng dần lời giải
bộ phận. Nếu việc mở rộng khiến lời giải bộ phận vi phạm
yêu cầu bài toán thì tiến hành quay lui, loại bỏ sửa đổi
gần nhất và thử một khả năng xây dựng lời giải bộ phận
có thể (hợp lệ) khác.
Nhận xét:
Mỗi cột phải có 1 con hậu
Con hậu 1 nằm trên cột 1
…
Con hậu j nằm trên cột j
…
Con hậu 8 nằm trên cột 8
Các con hậu phải không cùng hàng
Các con hậu phải không nằm trên đường chéo của nhau
Giải thuật
function Try (column) {
Kiểm tra An toàn
Thử lần lượt từng vị trí hàng
for (row = 1; row <= 8; row++) {
if ( [row, column] là an toàn) {
Đặt con hậu vào vị trí [row, column];
Nếu vị trí thử không bị
con hậu nào tấn công
mn == 8)
Con hậu thứ 8 là an toàn
In kết quả;
Đệ quy để với con hậu tiếp
else
Try (column + 1);
Xóa con hậu khỏi vị trí [row, column];
}
}
Xóa để tiếp tục thử vị trí
[row+1, column]
}
11
1/10/2011
12
12 trang
20640
Free
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 1, Phần 3: Thuật toán đê quy - Nguyễn Duy Hiệp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_phan_1_gioi_thieu_v.pdf
