Giáo trình Thuật toán - Giải thuật

ợc gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần có 
giá trị 1 và những thành phần khác có giá trị 0. 
Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất. 
Trở lại ví dụ của chúng ta, ở trạng thái ban đầu (chưa phân hoạch) chúng ta sẽ tính 
vector đặc trưng cho từng thuộc tính dẫn xuất để tìm ra thuộc tính dùng để phân 
hoạch. Đầu tiên là thuộc tính màu tóc. Thuộc tính màu tóc có 3 giá trị khác nhau 
(vàng, đỏ, nâu) nên sẽ có 3 vector đặc trưng tương ứng là : 
VTóc (vàng) = ( T(vàng, cháy nắng), T(vàng, không cháy nắng) ) 
Số người tóc vàng là : 4 
Số người tóc vàng và cháy nắng là : 2 
Số người tóc vàng và không cháy nắng là : 2 
Do đó 
VTóc(vàng) = (2/4 , 2/4) = (0.5, 0.5) 
Tương tự 
 91 
VTóc(nâu) = (0/3, 3/3) = (0,1) (vector đơn vị) 
Số người tóc nâu là : 3 
Số người tóc nâu và cháy nắng là : 0 
Số người tóc nâu và không cháy nắng là : 3 
VTóc(đỏ) = (1/1, 0/1) = (1,0) (vector đơn vị) 
Tổng số vector đơn vị của thuộc tính tóc vàng là 2 
Các thuộc tính khác được tính tương tự, kết quả như sau : 
VC.Cao(Cao) = (0/2,2/2) = (0,1) 
VC.Cao(T.B) = (2/3,1/3) 
VC.Cao(Thấp) = (1/3,2/3) 
VC.Nặng (Nhẹ) = (1/2,1/2) 
VC.Nặng (T.B) = (1/3,2/3) 
VC.Nặng (Nặng) = (1/3,2/3) 
VKem (Có) = (3/3,0/3) = (1,0) 
VKem (Không) = (3/5,2/5) 
Như vậy thuộc tính màu tóc có số vector đơn vị nhiều nhất nên sẽ được chọn để 
phân hoạch. 
Sau khi phân hoạch theo màu tóc xong, chỉ có phân hoạch theo tóc vàng (Pvàng) là 
còn chứa những người cháy nắng và không cháy nắng nên ta sẽ tiếp tục phân hoạch 
tập này. Ta sẽ thực hiện thao tác tính vector đặc trưng tương tự đối với các thuộc 
tính còn lại (chiều cao, cân nặng, dùng kem). Trong phân hoạch Pvàng, tập dữ liệu 
của chúng ta còn lại là : 
Tên Ch.Cao Cân 
Nặng 
Dùng 
kem? 
Kết quả 
Sarah T.Bình Nhẹ Không Cháy 
Dana Cao T.Bình Có Không 
 92 
Annie Thấp T.Bình Không Cháy 
Kartie Thấp Nhẹ Có Không 
VC.Cao(Cao) = (0/1,1/1) = (0,1) 
VC.Cao(T.B) = (1/1,0/1) = (1,0) 
VC.Cao(Thấp) = (1/2,1/2) 
VC.Nặng (Nhẹ) = (1/2,1/2) 
VC.Nặng (T.B) = (1/2,1/2) 
VC.Nặng (Nặng) = (0,0) 
VKem (Có) = (0/2,2/2) = (0,1) 
VKem (Không) = (2/2,0/2) = (1,0) 
2 thuộc tính dùmg kem và chiều cao đều có 2 vector đơn vị. Tuy nhiên, số phân 
hoạch của thuộc tính dùng kem là ít hơn nên ta chọn phân hoạch theo thuộc tính 
dùng kem. Cây định danh cuối cùng của chúng ta sẽ như sau : 
II.2.2. Độ đo hỗn loạn 
Thay vì phải xây dựng các vector đặc trưng như phương pháp của Quinlan, ứng với 
mỗi thuộc tính dẫn xuất ta chỉ cần tính ra độ đo hỗn loạn và lựa chọn thuộc tính nào 
có độ đo hỗn loại là thấp nhất. Công thức tính như sau : 
 93 
TA = 
trong đó : 
bt là tổng số phần tử có trong phân hoạch 
bj là tổng số phần tử có thuộc tính dẫn xuất A có giá trị j. 
bri : tổng số phần tử có thuộc tính dẫn xuất A có giá trị j và thuộc tính mục 
tiêu có giá trị i. 
II.3. Phát sinh tập luật 
Nguyên tắc phát sinh tập luật từ cây định danh khá đơn giản. Ứng với mỗi nút lá, ta 
chỉ việc đi từ đỉnh cho đến nút lá đó và phát sinh ra luật tương ứng. Cụ thể là từ cây 
định danh kết quả ở cuối phần II.2 ta có các luật sau (xét các nút lá từ trái sang 
phải) 
(Màu tóc vàng) và (có dùng kem)  không cháy nắng 
(Màu tóc vàng) và (không dùng kem)  cháy nắng 
(Màu tóc nâu)  không cháy nắng 
(Màu tóc đỏ)  cháy nắng 
Khá đơn giản phải không? Có lẽ không có gì phải nói gì thêm. Chúng ta hãy thực hiện 
bước cuối cùng là tối ưu tập luật. 
II.4. Tối ưu tập luật 
II.4.1. Loại bỏ mệnh đề thừa 
Khác so với các phương pháp loại bỏ mệnh đề thừa đã được trình bày trong phần 
biểu diễn tri thức (chỉ quan tâm đến logic hình thức), phương pháp loại bỏ mệnh đề 
thừa ở đây dựa vào dữ liệu. Với ví dụ và tập luật đã có ở phần trước, bạn hãy quan 
sát luật sau : 
(Màu tóc vàng) và (có dùng kem)  không cháy nắng 
Bây giờ ta hãy lập một bảng (gọi là bảng Contigency), bảng thống kê những người có 
dùng kem tương ứng với tóc màu vàng và bị cháy nắng hay không. Trong dữ liệu đã 
cho, có 3 người không dùng kem. 
 94 
 Không cháy 
nắng 
Cháy nắng 
Màu 
vàng 
2 0 
Màu 
khác 
1 0 
Theo bảng thống kê này thì rõ ràng là thuộc tính tóc vàng (trong luật trên) không 
đóng góp gì trong việc đưa ra kết luận cháy nắng hay không (cả 3 người dùng kem 
đều không cháy nắng) nên ta có thể loại bỏ thuộc tính tóc vàng ra khỏi tập luật. 
Sau khi loại bỏ mệnh đề thừa, tập mệnh đề của chúng ta trong ví dụ trên sẽ còn : 
(có dùng kem)  không cháy nắng 
(Màu tóc vàng) và (không dùng kem)  cháy nắng 
(Màu tóc nâu)  không cháy nắng 
(Màu tóc đỏ)  cháy nắng 
Như vậy quy tắc chung để có thể loại bỏ một mệnh đề là như thế nào? Rất đơn giản, 
giả sử luật của chúng ta có n mệnh đề : 
A1 và A2 và … và An  R 
Để kiểm tra xem có thể loại bỏ mệnh đề Ai hay không, bạn hãy lập ra một tập hợp P 
bao gồm các phần tử thỏa tất cả mệnh đề A1 , A2 , … Ai-, Ai+1, …, An (lưu ý : 
không cần xét là có thỏa Ai hay không, chỉ cần thỏa các mệnh đề còn lại là được) 
Sau đó, bạn hãy lập bảng Contigency như sau : 
 R  R 
Ai E F 
 
Ai 
G H 
Trong đó 
E là số phần tử trong P thỏa cả Ai và R. 
F là số phần tử trong P thỏa Ai và không thỏa R 
 95 
G là số phần tử trong P không thỏa Ai và thỏa R 
H là số phần tử trong P không thỏa Ai và không thỏa R 
Nếu tổng F+H = 0 thì có thể loại bỏ mệnh đề Ai ra khỏi luật. 
II.4.2. Xây dựng mệnh đề mặc định 
Có một vấn đề đặt ra là khi gặp phải một trường hợp mà tất cả các luật đều không 
thỏa thì phải làm như thế nào? Một cách hành động là đặt ra một luật mặc định đại 
loại như : 
Nếu không có luật nào thỏa  cháy nắng (1) 
Hoặc 
Nếu không có luật nào thỏa  không cháy nắng. (2) 
(chỉ có hai luật vì thuộc tính mục tiêu chỉ có thể nhận một trong hai giá trị là cháy 
nắng hay không cháy nắng) 
Giả sử ta đã chọn luật mặc định là (2) thì tập luật của chúng ta sẽ trở thành : 
(Màu tóc vàng) và (không dùng kem)  cháy nắng 
(Màu tóc đỏ)  cháy nắng 
Nếu không có luật nào thỏa  không cháy nắng. (2) 
Lưu ý rằng là chúng ta đã loại bỏ đi tất cả các luật dẫn đến kết luận không cháy nắng 
và thay nó bằng luật mặc định. Tại sao vậy? Bởi vì các luật này có cùng kết luận với 
luật mặc định. Rõ ràng là chỉ có thể có một trong hai khả năng là cháy nắng hay 
không. 
Vấn đề là chọn luật nào? Sau đây là một số quy tắc. 
1) Chọn luật mặc định sao cho nó có thể thay thế cho nhiều luật nhất. (trong 
ví dụ của ta thì nguyên tắc này không áp dụng được vì có 2 luật dẫn đến cháy 
nắng và 2 luật dẫn đến không cháy nắng) 
2) Chọn luật mặc định có kết luận phổ biến nhất. Trong ví dụ của chúng ta thì 
nên chọn luật (2) vì số trường hợp không cháy nắng là 5 còn không cháy 
nắng là 3. 
3) Chọn luật mặc định sao cho tổng số mệnh đề của các luật mà nó thay thế 
là nhiều nhất. Trong ví dụ của chúng ta thì luật được chọn sẽ là luật (1) vì 
tổng số mệnh đề của luật dẫn đến cháy nắng là 3 trong khi tổng số mệnh đề 
của luật dẫn đến không cháy nắng chỉ là 2. 
 96 
BÀI TẬP 
CHƯƠNG 1 
1) Viết chương trình giải bài toán hành trình người bán hàng rong bằng hai 
thuật giải GTS1 và GTS2 trong trường hợp có n địa điểm khác nhau. 
2) Viết chương trình giải bài toán phân công công việc bằng cách ứng dụng 
nguyên lý thứ tự. 
3) Ứng dụng nguyên lý thứ tự, hãy giải bài toán chia đồ vật sau. Có n vật với 
khối lượng lần lượt là M1, M2, … Mn. Hãy tìm cách chia n vật này thành hai 
nhóm sao cho chênh lệch khối lượng giữa hai nhóm này là nhỏ nhất. 
4) Viết chương trình giải bài toán mã đi tuần. 
5) Viết chương trình giải bài toán 8 hậu. 
6) Viết chương trình giải bài toán Ta-canh bằng thuật giải A*. 
7) Viết chương trình giải bài toán tháp Hà Nội bằng thuật giải A*. 
8)* Viết chương trình tìm kiếm đường đi ngắn nhất trong một bản đồ tổng 
quát. Bản đồ được biểu diễn bằng một mảng hai chiều A, trong đó A[x,y]=0 là 
có thể đi được và A[x,y]= 1 là vật cản. Cho phép người dùng click chuột trên 
màn hình để tạo bản đồ và xác định điểm xuất phát và kết thúc. Chi phí để đi 
từ một ô bất kỳ sang ô kế cận nó là 1. 
Mở rộng bài toán trong trường hợp chi phí để di chuyển từ ô (x,y) sang một 
bất kỳ kế (x,y) là A[x,y]. 
CHƯƠNG 2 
1. Viết chương trình minh họa các bước giải bài toán đong nước (sử dụng đồ họa 
càng tốt). 
2. Viết chương trình cài đặt hai thuật toán Vương Hạo và Robinson trong đó liệt 
kê các bước chứng minh một biểu thức logic. 
3. Viết chương trình giải bài toán tam giác tổng quát bằng mạng ngữ nghĩa (lưu 
ý sử dụng thuật toán ký pháp nghịch đảo Ba Lan) 
4. Hãy thử xây dựng một bộ luật phức tạp hơn trong ví dụ đã được trình bày 
dùng để chuẩn đoán hỏng hóc của máy tính. Viết chương trình ứng dụng bộ 
luật này trong việc chuẩn đoán hỏng hóc của máy tính (sử dùng thuật toán 
suy diễn lùi). 
5. Hãy cài đặt các frame đặc tả các đối tượng hình học bằng kỹ thuật hướng đối 
tượng trong ngôn ngữ lập trình mà bạn quen dùng. Hãy xây dựng một ngôn 
ngữ script đơn giản cho phép người dùng có thể sử dụng các frame này trong 
việc giải một số bài toán hình học đơn giản. 
CHƯƠNG 3 
1) Cho bảng số liệu sau 
 97 
Hãy xây dựng cây định danh và tìm luật để xác định một người là Châu Âu 
hay Châu Á bằng hai phương pháp vector đặc trưng của Quinlan và độ đo hỗn 
loạn. 
STT Dáng Cao Giới Châu 
1 To TB Nam Á 
2 Nhỏ Cao Nam Á 
3 Nhỏ TB Nam Âu 
4 To Cao Nam Âu 
5 Nhỏ TB Nữ Âu 
6 Nhỏ Cao Nam Âu 
7 Nhỏ Cao Nữ Âu 
8 To TB Nữ Âu 
2)* Viết chương trình cài đặt tổng quát thuật toán học dựa trên việc xây dựng 
cây định danh. Chương trình yêu cầu người dùng đưa vào danh sách các 
thuộc tính dẫn xuất, thuộc tính mục tiêu cùng với tất cả các giá trị của mỗi 
thuộc tính; yêu cầu người dùng cung cấp bảng số liệu quan sát. Chương trình 
sẽ liệt kê lên màn hình các luật mà nó tìm được từ bảng số liệu. Sau đó, yêu 
cầu người dùng nhập vào các trường hợp cần xác định, hệ thống sẽ đưa ra kết 
luận của trường hợp này. 
Lưu ý : Nên sử dụng một hệ quản trị CSDL để cài đặt chương trình này. 
GS.TSKH. Hoàng Kiếm 
Ths. Đinh Nguyễn Anh Dũng