Giáo trình Cấu trúc dữ liệu và giải thuật - Trường Đại học Hàng Hải
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
Chương 1. Thuật toán và các khái niệm 4
1.1. Khái niệm thuật toán (giải thuật)
4
1.2. Cách biểu diễn thuật toán
1.3. Độ phức tạp thuật toán 7
4
1.3.1. Các tiêu chí đánh giá thuật toán
1.3.2. Các lớp thuật toán
1.4. Cấu trúc dữ liệu
1.5. Các chiến lược thiết kế thuật toán. 11
1.5.1. Chiến lược vét cạn (Brute force)
1.5.2. Chiến lược quay lui (Back tracking)
16
1.5.3. Chiến lược chia để trị (Divide and Conquer)
1.5.4. Chiến lược tham lam (Greedy) 14
11
26
1.5.5. Quy hoạch động (Dynamic Programming)
Chương 2. Tìm kiếm (Searching) 29
2.1. Bài toán tìm kiếm.
29
2.2. Tìm kiếm tuần tự (SEQUenTIAL search). 29
2.3. Tìm kiếm nhị phân (binary search) 29
2.4. Một số ví dụ
Chương 3. Sắp xếp. 29
3.1. Bài toán sắp xếp.
29
3.2. Các phương pháp sắp xếp cơ bản. 29
3.2.1. Sắp xếp chọn ( Selection Sort)
3.2.2. Sắp xếp chèn (insertion sort)
29
31
3.2.3. Sắp xếp nhị phân (binary insertion sort) 31
3.2.4. Sắp xếp nổi bọt (Bubble Sort) 33
3.3. Các thuật toán nâng cao 35
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
1
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
3.3.1. Quick_Sort 35
3.3.2. Sắp xếp bằng trộn (Merge Sort) 41
3.3.2.1. Thuật toán trộn
3.3.2.2. Sắp xếp trộn
41
41
3.3.3. Sắp xếp vun đống (heap Sort)
3.3.3.1. Khái niệm Heap. 44
41
3.3.3.2. Sắp xếp vung đống (Heap Sort) 46
.3.4. Một số ví dụ áp dụng
Chương 4. các cấu trúc dữ liệu cơ bản 58
4.1. Khái niệm cấu trúc dữ liệu 58
4.2. Kiểu dữ liệu mảng
4.3. Ngăn xếp (Stack)
4.3.1. Định nghĩa
60
4.3.2. Cài đặt ngăn xếp bằng mảng
4.3.3. Một số ứng dụng của ngăn xếp
4.4. Hàng đợi (Queue)
4.4.1. Định nghĩa
4.4.2. Cài đặt hàng đợi bằng mảng
4.4.3. Một số ứng dụng của hàng đợi
4.5. Danh sách liên kết (Linked List)
4.5.1. Định nghĩa
4.5.2. Cài đặt danh sách liên kết đơn bằng mảng
4.5.3. Cài đặt danh sách liên kết đơn bằng con trỏ
4.5.4. Một số ứng dụng của danh sách liên kết
4.5.5. Cài đặt ngăn xếp và hàng đợi sử dụng danh sách liên kết
4.5.6. Các loại danh sách liên kết khác
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
2
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
Chương 5. Cây (Tree)
5.1. Định nghĩa
5.2. Cây tìm kiếm nhị phân (Binary Search Tree)
5.2.1. Cây nhị phân
5.2.2. Các thao tác trên cây tìm kiếm nhị phân
5.2.2.1. Các phương pháp duyệt cây
5.2.2.2. Thêm một nút vào cây
5.2.2.3. Xóa một nút khỏi cây
5.2.2.4. Tìm kiếm
5.2.3. Cài đặt cây tìm kiếm nhị phân
5.2.3. Ứng dụng của cây tìm kiếm nhị phân
5.3. Cây cân bằng
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
3
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
CHƯƠNG 1. THUẬT TOÁN VÀ CÁC KHÁI NIỆM
Khái niệm thuật toán (giải thuật)
Khái niệm không hình thức (trực giác): thuật toán là một dãy hữu hạn các qui tắc
cho ra kết quả của một bài toán.
Khái niệm hình thức: thuật toán được hiểu như một máy Turing.
Đặc trưng của thuật toán: Thuật toán có một số đặc trưng sau
+ Tính dừng: Giải thuật phải kết thúc sau một số hữu hạn bước.
+ Tính xác định: Ở mỗi bước các thao tác phải rõ ràng, không gây nhập nhằng,
lẫn lộn. Nói cách khác, tại mỗi bước của thuật toán chi có một kết quả duy nhất.
+ Đại lượng vào (Input): Mỗi giải thuật có thể có một hoặc nhiều đại lượng vào
gọi là dữ liệu vào.
+ Đại lượng ra (Output): Sau khi giải thuật được thực hiện, tuỳ theo chức năng
mà giải thuật đảm nhiệm ta có thể thu được một số đại lượng ra xác định gọi là
dữ liệu ra.
+ Tính hiệu quả: Một bài toán có thể có nhiều giải thuật khác nhau. Một giải
thuật tốt phải đơn giản, dễ hiểu, tiết kiệm bộ nhớ và thời gian.
+ Tính phổ dụng: Giải thuật được xem là phổ dụng nếu nó có thể giải bất kì bài
toán nào trong một lớp các bài toán.
Nhận xét: Bốn tính chất đầu là các tính chất bắt buộc của thuật toán, hai tính
chất sau là hai tính chất không bắt buộc.
Cách biểu diễn thuật toán
Có nhiều cách để biểu diễn thuật toán, sau đây là một số cách chính hay dùng
trong thực tế.
+ Liệt kê từng bước: Ví dụ bài toán tìm UCLN của hai số nguyên a, b.
Bài toán: Cho hai số tự nhiên a, b. Hãy tìm ước số chung lớn nhất của chúng.
Input: Hai số tự nhiên a, b;
Output: Ước số chung lớn nhất của a, b.
Thuật toán:
Bước 1: Nếu a=b thì USCLN(a, b)=a (hoặc =b).
Bước 2: Nếu a > b thì tìm USCLN của a-b và b, quay lại bước 1;
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
4
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
Bước 3: Nếu a < b thì tìm USCLN của a và b-a, quay lại bước 1;
+ Diễn tả bằng lưu đồ: Công cụ giúp biểu diễn thuật toán một cách trực quan
gồm 4 khối cơ bản.
1
Begin
A
3
T
4
B
2
End
F
Khối 1: Khối Begin, bắt đầu thuật toán, chỉ có duy nhất một đường ra;
Khối 2: Khối End, kết thúc thuật toán, có thể có nhiều đường vào;
Khối 3: Thực hiện công việc A (có thể là một hoặc nhiều câu lệnh); gồm một
đường vào và một đường ra;
Khối 4: Rẽ nhánh, kiểm tra biểu thức logic B (biểu thức Boolean), nếu B đúng
thuật toán sẽ đi theo nhánh T (True), nếu B sai thuật toán sẽ đi theo nhánh F
(False).
+ Các cấu trúc điều khiển: Sử dụng một số chương trình điều khiển như tuần tự,
rẽ nhánh, lặp để biểu diễn. Các cấu trúc này có thể được viết dưới dạng một ngôn
ngữ bất kì (tự nhiên, lập trình).
Phân tích thuật toán.
Tính hiệu quả
Có hai tiêu chuẩn để lựa chọn:
+ Thuật toán đơn giản, dễ hiểu, dễ cài đặt.
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
5
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
+ Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên máy tính, đặc biệt là
thời gian thực hiện bài toán.
⇒ Tuỳ vào từng bài toán cụ thể mà xác định tính chất nào quan trọng hơn.
Tính chất sau được xem là tính hiệu quả của thuật toán. Bao gồm hai nhân tố cơ
bản:
a) Dung lượng không gian nhớ cần thiết để lưu trữ các dữ liệu vào, ra, trung gian.
b) Thời gian cần thiết để thực hiện thuật toán ( Thời gian chạy )
Chỉ quan tâm đến thời gian thực hiện của thuật toán ⇒ Thuật toán có hiệu quả là
thuật toán có thời gian chạy ít hơn các thuật toán khác.
Đánh giá thời gian thực hiện thuật toán
+ Thời gian chạy chương trình phụ thuộc vào các yếu tố
1) Các dữ liệu vào.
2) Chương trình dịch chuyển một chương trình sang mã máy
3) Tốc độ thực hiện các phép toán của máy tính được sử dụng để chạy chương
trình.
+ Khái niệm độ phức tạp dữ liệu vào dựa trên hai quan niệm
. Quan niệm 1 : Độ phức tạp của dữ liệu vào là số lượng dữ liệu vào của bài
toán.
Ví dụ : . Bài toán sắp xếp mảng thì dữ liệu vào có số lượng là số thành phần của
mảng
. Bài toán tìm số lớn nhất có dữ liệu vào là n+2
⇒ Đây là phương pháp dùng để đánh giá sơ bộ.
. Quan niệm 2 : Coi dung lượng nhớ để ghi toàn bộ dữ liệu vào ( Qui ra một đơn
vị cụ thể : bit ) là độ phức tạp dữ liệu
Ví dụ : Tìm số lớn nhất của mảng có n phần tử x1,x2,…,xn
Một số nguyên xi cần số bít để chứa nó là log2xi+1
n
log 2xi + n + log 2n + 1
∑
i=1
⇒ Tổng dữ liệu nhớ cần thiết là
Thời gian thực hiện thuật toán không chỉ phụ thuộc vào độ phức tạp của dữ
liệu mà còn phụ thuộc vào dữ liệu cá biệt
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
6
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
Ví dụ bài toán tìm max với dữ liệu khác nhau
Độ phức tạp thuật toán
+ Là tiêu chuẩn để đánh giá một thuật toán và quan tâm đến hai khái niệm:
Độ phức tạp trong trường hợp xấu nhất: Là chi phí được trả nhiều nhất có thể
trong mọi bộ dữ liệu có thể về tài nguyên (bộ nhớ và thời gian).
Độ phức tạp trung bình: Là chi phí trung bình phải trả trong mọi bộ dữ liệu có
thể.
⇒Chi phí trung bình khó xây dựng hơn trong trường hợp tồi nhất
⇒Chỉ quan tâm đến chi phí trong trường hợp tồi nhất
+Theo quan điểm 1 ta có công thức tính toán như sau:
- Về bộ nhớ LA(n) = Max lA(e) : || e|| ≤ n
Trong đó: A: Thuật toán A
|| e || Độ phức tạp dữ liệu vào
- Về thời gian TA(n) = Max tA(e) : || e|| ≤ n
+Theo quan điểm 2 có 2 mô hình toán
- Mô hình lý luận: Máy Turing
- Mô hình ứng dụng: Các máy tính cụ thể theo nguyên lý Von Newman
1) Máy Turing đề xuất năm 1930 là một dãy các chỉ thị, mệnh lệnh ⇒ cho ta kết
quả
Cấu tạo máy Turing gồm:
- 1 băng có nhiều ô nhớ, mỗi ô có thể chứa một kí tự
- 1 bộ điều khiển trạng thái
- 1 đầu đọc viết
. Tại một thời điểm t trạng thái là p, đầu đọc chỉ vào x: (p, x)
. Thời điểm t+1 bộ điều khiển chuyển sang trạng thái q, đầu đọc ghi hoặc đọc dữ
liệu từ một ô
- Đầu bộ nhớ là một ô nhớ để chứa một tín hiệu cơ sở
- Chi phí về bộ nhớ chính là số ô nhớ (cần sử dụng) được sử dụng trong quá trình
tính toán
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
7
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
- Đơn vị thời gian: Thời gian để chuyển một bước chuyển hình trạng
- Chi phí về thời gian: Là số bước chuyển hình trạng trong một quá trình tính
toán.
2) Máy tính theo nguyên lý Von Newman
+ Chương trình gồm 5 phần . Bộ nhớ
. Bộ nhớ số học và lôgic
. Bộ xử lí phép tính số học và lôgic
. Bộ điều khiển để chỉ huy thực hiện chương trình
. Bộ vào/ra
- Đơn vị nhớ: Chuỗi miền nhớ chứa dữ liệu
- Chi phí bộ nhớ: Số biến dùng trong chương trình
- Đơn vị thời gian: Thời gian để thực hiện 1 phép tính sơ cấp như +, -, *, /, and,
or, not.
- Chi phí về thời gian: Số phép tính sơ cấp đã làm trong chương trình
Định lý: Nếu thuật toán thực hiện trên mô hình lý thuyết có độ phức tạp về thời
gian là đa thức thì thuật toán trên mô hình ứng dụng tương ứng cũng có độ phức
tạp đa thức. Chiều ngược lại không có (Khi thêm điều kiện: Trên mô hình ứng
dụng là đa thức, độ phức tạp của dữ liệu vào là đa thức, các phép tính sử dụng là
sơ cấp (không có luỹ thừa) thì xảy ra chiều ngược lại).
Nói chung việc đánh giá thuật toán chỉ quan tâm đến đánh giá thời gian thực hiện
thuật toán.
♣Ký hiệu O (ô lớn) và đánh giá thời gian thực hiện thuật toán
- Khi đánh giá thời gian thực hiện bằng phương pháp toán học chúng ta sẽ bỏ qua
nhân tố phụ thuộc vào cách cài đặt, chỉ tập trung vào xác định độ lớn của thời
gian thực hiện T(n) – n: kích thước dữ liệu vào
- Ký hiệu O được sử dụng để mô tả độ lớn của hàm T(n). Giả sử n là số nguyên
không âm, T(n), f(n) là các hàm thực không âm. Ta viết T(n) = O(f(n)) nếu và
chỉ nếu tồn tại các hằng số dương c và n0 sao cho T(n) ≤c*f(n) ∀ n ≥ n0 nghĩa là
T(n) bị chặn trên bởi một hằng số nhân với f(n) với mọi giá trị n từ một thời điểm
nào đó
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
8
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
Nếu một thuật toán có thời gian thực hiện T(n) = O (f(n)) ta nói rằng thuật toán
có thời gian thực hiện cấp f(n).
Ví dụ:
Giả sử T(n) = 3*n∝+5*n + 4
Ta có 3*n∝+5*n + 4≤3*n∝+5* n∝+ 4 n∝=12 n∝ ∀ n≥1
( c = 12, n0 = 1)
Vậy T(n) = 0( n∝) hay thuật toán có thời gian thực hiện cấp n∝
- Nhận xét:
1) Nếu T(n) = θ ( n∝) và f(n) = 0(f1(n)) thì T(n) =θ(f1(n))
Chứng minh : Vì T(n) = θ (f1(n)) ⇒∃ c0, n0 để T(n) ≤c0*f(n) ∀ n ≥ n0 và
f(n) = θ (f1(n)) ⇒∃ c1, n1 để f(n) ≤c1*f1(n) ∀ n ≥ n1
⇒ T(n) ≤c0*c1*f1(n) ∀ n ≥ mã(n0 ,n1)
2) Mọi thuật toán có thời gian chạy là đa thức là một thuật toán tốt
3) Chia các thuật toán thành các lớp
- Lớp các thuật toán có thời gian chạy là đa thức. Tức là tồn tại 1 đa thức f(n) để
T(n) ≤ c* f(n) ∀ n ≥ n0 gọi là lớp P.
- Lớp các thuật toán có thời gian chạy là hàm mũ, gọi là NP
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
9
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
Thời
gian
tăng
Tên
θ(n)
Hằng
θ(1)
Một số qui tắc xác định độ phức tạp
thuật toán:
Logarit
Tuyến tính
θ(log2n)
θ(n)
- Qui tắc tổng: Giả sử T1(n) và
T1(n) là thời gian thực hiện của hai
đoạn chương trình P1 và P2 và
T1(n) = θ(f(n)) ; T2(n) =θ(g(n)). Khi
đó thời gian thực hiện P1 rồi đến P2
θ(n
nlogn
log2n)
là T1(n)+T2(n)
(f(n),g(n))).
=
θ
(max
Bình
θ(n2)
θ(n3)
θ(2n)
phương
- Qui tắc tích: Giả sử như trên. Khi
đó thời gian thực hiện P1 và P2 lồng
nhau là T1(n)*T2(n) = θ (f(n),g(n)).
Lập phương
Mũ→(2n,
nn, n!)
Ví dụ :
Câu lệnh gán x:=x+1 có thời gian thực hiện là θ(1)
Câu lệnh For i:=1 to n do x:=x+1 có thời gian thực hiện là θ(n.1) = θ(n)
* Chú ý: 1) Khi đánh giá thuật toán chỉ cần chú ý tới các phép toán tích cực, đó là
các phép toán thuộc giải thuật mà thời gian thực hiện nó không ít hơn thời gian
thực hiện các phép khác (có thể có nhiều).
ví dụ:
Tính:
n
+ x2 +...+ x
x
x = 1+
e
1! 2!
n!
Với x, n cho trước .
1) Read(x); S:=1;
2) For i:=1 to n do
Begin
P:=1
For j:=1 to i do P:=P*x/j;
S:=S+p;
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
10
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
End;
- Phép toán tích cực P:=P*x/j;
Thời gian thực hiện là 1 + 2 + .. . + n = n*(n+1)/2
⇒Thời gian T(n) = θ(n2)
Cách hai:
1) Read(x) ; S:=1; P:=1;
2) For i:=1 to n do
Begin
P:=P*x/i;
S:=S+P;
End;
Thời gian T(n) = θ(n) vì phép toán tích cực chỉ thực hiện n lần
2) Có những trường hợp thời gian thực hiện giải thuật còn phụ thuộc vào tình
trạng dữ liệu (ngoài phụ thuộc vào kích thước)
Ví dụ bài toán sắp xếp khi dữ liệu đã được sắp xếp và dữ liệu có thứ tự ngược lại.
Các chiến lược thiết kế thuật toán.
- Không có chiến lược hay phương pháp vạn năng nào có thể giúp thiết kế được
thuật toán giải quyết mội vấn đề. Nhưng người ta đã chỉ ra một số phương pháp
thiết kế cơ bản gọi là các chiến lược thiết kế thuật toán. Mỗi phương pháp này có
thể áp dụng để giải quyết một phạm vi khá rộng các bài toán.
Chia để trị.
- Ý tưởng: Chia bài toán cần giải thành các bài toán con. Các bài toán con lại
tiếp tục phân chia thành các bài toán con nhỏ hơn, cứ thế tiếp tục cho tới khi ta
nhận được các bài toán con đã có giải thuật hoặc là có thể dễ dàng đưa ra thuật
giải. Sau đó ta tìm cách kết hợp các nghiệm của các bài toán con để nhận được
nghiệm của bài toán con lớn hơn,.. . cứ như vậy cuối cùng nhận được bài toán
con cần giải.
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
11
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
- Thông thường các bài toán con nhận được trong quá trình phân tích là cùng
dạng với bài toán ban đầu, chỉ có cỡ của chúng là nhỏ hơn. Trong các trường
hợp như vậy thuật toán tìm được có thể biểu diễn tự nhiên bởi thủ tục đệ qui.
Lược đồ phương pháp đệ quy:
Procedure Divice Conquer (A, x); {Tìm nghiệm x của bài toán A}
Begin
If A đủ nhỏ Then Solve (A)
Else
begin
- Phân A thành các bài toán con A1, A2, …,Am;
- For i:=1 to m do Divice Conquer(Ai,,xi);
xi (i = 1,m)
- Kết hợp các nghiệm của các bài toán:
của bài toán
của Ai để được nghiệm x
end
End;
Trong đó Solve (A) là thuật giải bài toán A trong trường hợp A có cỡ chữ đủ nhỏ.
- Ứng dụng: - Thuật toán tìm kiếm nhị phân.
- Thuật toán tìm kiếm Quicksort
- Minh hoạ:
+ Phát biểu bài toán: Cho mảng A[1,n] tìm phần tử lớn nhất và nhỏ nhất của
mảng này
+ ý tưởng: Chia mảng A[1..n] thành hai mảng con A[1..k] và A[k+1..n] (k=n/2)
Nếu tìm được MAX và MIN của các mảng con A[1..k] và A[k+1..n] ta dễ dàng
xác định được MAX và MIN trên A[1..n]
Để tìm được MAX và MIN trên các mảng con ta tiếp tục chia đôi chúng. Quá
trình dừng lại khi ta nhận được các mảng con chỉ có một hoặc hai phần tử, khi đó
MAX và MIN được xác định một cách dễ dàng.
+ Thủ tục
Procedure MaxMin(i, j, fmax, fmin);
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
12
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
{Tìm Max, min trên mảng A[1..n], i, j ∈ [1..n], ban đầu gọi thủ tục i = 1, j = n}
Begin
If i = j then
begin
fmax:=a[i];
fmin:=a[i];
end
else
if j=i+1 then
if A[i] < A[j] then
begin
fmax:=a[j] ;
fmin:=a[i];
end
else
begin
fmax:=a[i] ;
fmin:=a[j];
end
else
begin
mid := (i+j) div 2 ;
MaxMin(i, mid, gmax, gmin);
MaxMin(mid-1, j, hmax, hmin);
if gmax < hmax then fmax := hmax
else fmax := gmax;
if gmin < hmin then fmin := gmin
else fmin := hmin;
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
13
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
end;
End;
Tham ăn:
Dùng để giải quyết các bài toán tối ưu. Nhiều vấn đề cần thiết giải quyết có thể
qui về vấn đề sau:
Cho trước một tập A các đối tượng nào đó đòi hỏi phải chọn một tập con S các
đối tượng thoả mãn một số điều kiện nào đó. Bất kì một tập con S nào đó của A
thoả mãn các yêu cầu đã đặt ra được gọi là nghiệm chấp nhận được của bài toán.
Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được của bài toán. Một hàm mục
tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó. Một nghiệm chấp
nhận được mà tại đó hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) được gọi là
nghiệm tối ưu.
Ý tưởng: Ta xây dựng tập S dần dồn từng bước. Khởi đầu S rỗng. Tại mỗi bước
ta sẽ chọn một phần tử tốt nhất trong các phần tử còn lại của A để đưa vào S.
Việc lựa chọn 1 phần tử như thế tại mỗi bước được hướng dẫn bởi hàm chọn.
Phần tử được chọn sẽ bị loại khỏi A. Nếu khi thêm phần tử được chọn vào S mà
S vẫn còn thoả mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm
vào phần tử được chọn.
- Lược đồ:
Procedure Greedy(A,S);
{A:Tập ứng cử viên, S là nghiệm}
Begin
S ← ∅ ;
While A <> ∅ do
begin
- x ← select (A) ;
- A ← A – {x};
- If S ∪ {x} chấp nhận được then S ← S ∪ {x}
end;
End;
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
14
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
- Select (A) là hàm chọn, cho phép chọn ra từ tập A một phần tử tốt nhất, nhiều
hứa hẹn nhất là thành viên của nghiệm.
- Ứng dụng: Thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh nguồn đến các
đỉnh còn lại trong đồ thị, thuật toán Prim tìm cây bao trùm trong đồ thị.
- Bài toán minh hoạ:
- Phát biểu bài toán : G = <X, U> là một đồ thị vô hướng. Hãy tìm cách sơn các
đỉnh của đồ thị G sao cho 2 đỉnh kề nhau sơn bởi 2 mầu khác nhau và số mầu là
ít nhất.
- Ý tưởng: Sử dụng 1 màu được sơn, chọn một đỉnh chưa sơn và sơn đỉnh đó.
Sau đó, mỗi đỉnh chưa sơn nếu nó không kề với các đỉnh được sơn bởi mầu đang
sử dụng thì ta sơn nó bởi mầu đó.
Khi không còn đỉnh nào có thể sơn được bởi mầu đó thì ta dùng mầu mới để sơn
và áp dụng cách như trên.
Tiếp tục cho tới khi sơn hết đồ thị.
- Thủ tục
+ Giả sử X là tập hợp các đỉnh của đồ thị
Gọi X0 là tập hợp các đỉnh chưa được sơn, X1 là tập hợp các đỉnh được sơn với
màu mới. Các màu được mã hoá bởi các số nguyên k = 1, 2, .. .
Giải thuật như sau:
Procedure Coloring;
Begin
k := 0;
X0 := X;
While X0 <> ∅ do
begin
- k:= k+1;
- Chọn x ∈ X0 và sơn bởi màu k;
- X1 = {x}
- For each u ∈ X0 do
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
15
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
If u không kề với mọi ω ∈ x1 then
begin
+ Sơn u bởi màu k
+ X1 := X1 ∪ {u};
end;
- X0 = X0 – X1;
end;
End;
*) Chú ý: Trong một số bài toán nếu xây dựng được hàm chọn thích hợp có thể
cho nghiệm tối ưu. Trong nhiều bài toán, thuật toán tham ăn chỉ cho nghiệm gần
11
9
17
19
10
7
1
2
8
18
5
6
13
12
14
12
15
16
4
đúng với nghiệm tối ưu.
Ví dụ: Hãy tô mầu đồ thị trên.
Chiến lược quay lui (Back tracking / try and error)
Là một trong những kỹ thuật quan trọng nhất. Nó có thể áp dụng để thiết kế thuật
toán tìm ra một nghiệm hay tất cả các nghiệm của bài toán.
- Trong nhiều vấn đề, việc tìm nghiệm có thể quy về việc tìm một véc tơ hữu hạn
(x1, x2, . . ., xn, . . .) nhưng độ dài vectơ có thể không xác định trước. Véctơ này
cần phải thoả mãn một số điều kiện nào đó tuỳ thuộc vào vấn đề cần giải quyết.
Các thành phần xi của vectơ được chọn ra từ một tập hữu hạn Ai (i = 1 .. n)
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
16
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
- Ý tưởng phương pháp quay lui: Xây dựng vectơ nghiệm dần từng bước, bắt đầu
từ vectơ không. Thành phần đầu tiên X1 được chọn từ tập Si = A. Khi đã chọn
được các thành phần x1, x2, . . . , xi-1 thì từ các điều kiện bài toán ta sẽ xác định
được tập Si các ứng cử viên có thể chọn làm thành phần xi.
- Tập Si là tập con của tập Ai và phụ thuộc vào các thành phần x1, x2, . . ., xi-1
đã chọn. Chọn một phần tử xi từ Si ta mở rộng nghiệm một phần (x1, x2, . . , xi-
1) đến nghiệm một phần (x1, x2,. . ., xi).
- Lặp lại quá trình trên để tiếp tục mở rộng nghiệm một phần (x1,x2,…,xi). Nếu
không thể chọn được thành phần xi+1 ( khi Si+1 = ∅) thì ta quay lui chọn phần
tử khác của Si làm xi. Nếu không còn phần tử nào để chọn làm xi thì ta quay lại
chọn một phần tử khác của Si-1 làm xi-1 và cứ thế tiếp tục.
- Trong quá trình mở rộng nghiệm ta phải kiểm tra nghiệm một phần có là
nghiệm của bài toán hay không. Nếu chỉ cần tìm một nghiệm thì khi gặp nghiệm
ta dừng lại. Còn tìm mọi nghiệm thì quá trình dừng lại khi mọi khả năng chọn
các thành phần của các vectơ đã được xét hay vét cạn (phân tích top-down, phân
tích bottom-up).
- Lược đồ:
Procedure Backtrack;
Begin
S1 = A1;
k:=1;
While k >0 do
begin
+ While Sk <> ∅ do
begin
- Chọn xk ∈ Sk ;
- Sk = Sk – { xk };
- if (x1, x2, . . . , xk) là nghiệm then viết ra nghiệm;{xử lý}
- k := k+1;
- xác định Sk;
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
17
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
end;
+ k:=k-1; {Quay lui}
end;
End;
- Khi áp dụng lược đồ tổng quát của phương pháp quay lui cho các bài toán cụ
thể, cần chú ý 3 điểm:
+ Tìm cách biểu diễn nghiệm của bài toán dưới dạng một dãy các đối tượngđược
chọn dần từng bước (x1, x2,. . ., xi, . . .)
+ Xác định các tập Si các ứng cử viên được chon làm thành phần thứ i của vec tơ
nghiệm. Chọn cách thích hợp để biểu diễn Si.
+ Tìm các điều kiện để một véctơ đã chọn là nghiệm của bài toán
Ứng dụng: Thuật toán tìm kiếm theo độ sâu trên cây không gian thông tin.
- Minh hoạ: Mã thăm bàn cờ, tám hậu.
Bài toán 1: Mã thăm bàn cờ (Knight tour)
Phát biểu:
Input : + Cho bàn cờ n*n ô
+ Vị trí xuất phát của con mã
+ Luật đi của con mã
Out put: Tìm đường đi để sau n2-1 lần con mã đi thăm kín bàn cờ
21
16
11
6
10
5
15
20
1
4
19
14
3
1
6
15
20
7
10
5
21
16
11
4
9
14
19
8
9
22
17
12
18
13
2
2
22
17
12
24
7
8
13
18
24
3
23
25
25
23
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
18
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
- Ý tưởng của giải thuật:
+ Vét cạn mọi nước đi có thể có của mã.
+ Quay lui (lần ngược thử & sai)
- Giải thuật:
Procedure thử nước đi tiếp;
Begin
+ Khởi động việc chọn nước đi;
+Repeat
- Chọn nước đi tiếp từ danh sách ứng cử
- if chấp nhận được then
begin
- Ghi nhớ nước đi
- If bàn cờ chưa kín then
begin
- Thử nước đi tiếp
- If không thành then xoá ghi nhớ trước
end;
end;
Until ( nước đi thành công) or (không còn danh sách ứng cử);
End;
+ Xây dựng cấu trúc dữ liệu
- Sử dụng ma trận h để biểu diễn bàn cờ
h[x,y] = 0 : ô (x,y) chưa được mã ghé thăm
h[x,y] = i : ô (x,y) được mã ghé thăm ở nước đi thứ i (i ≤ n2)
- q : true thành công
false thất bại
-(u,v) chấp nhận khi 1 ≤ u,v ≤ u ; h[u,v]=0 (ô (u,v) nằm trong bàn cờ và chưa
được mã đi).
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
19
Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật
- Giải thuật mịn bước một ( nhờ có biểu diễn dữ liệu ở bước một)
Procedure Try( i, x, y :integer; var q : boolean);
Var u,v : integer; q1 : boolean;
Begin
- Khởi động việc chọn nước đi; // Đặt quân mã ban đầu ở đâu.
- Repeat
+ Chọn nước đi (u, v) từ danh sách được ứng cử.
+ If (1 ≤ u,v ≤ u) and ( h[u,v]=0 ) then
begin
h[u,v] := i;
if (i<n2) then
begin
Try (i+1, u, v, q1) ;
If not q1 then h[u,v] = 0 ;
end
else q1 := true;
end;
until q1 or không còn nước đi trong danh sách ứng cử;
q :=q1;
End;
Chọn cấu trúc dữ liệu biểu diễn đường đi của quân mã:
a[1] := 2; b[1] := 1;
a[2] := 1; b[2] := 2;
a[3] := -1; b[3] := 2;
a[4] := -2; b[4] := 1;
a[5] := -2; b[5] := -1;
a[6] := -1; b[6] := -2;
a[7] := 1; b[7] := -2;
Bộ môn KHMT – Khoa CNTT – ĐHHH Việt Nam
20
Tải về để xem bản đầy đủ
90 trang
04/05/2022
6260
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Trường Đại học Hàng Hải", để 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:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_truong_dai_hoc_han.pdf
