MỘT SỐ THUẬT GIẢI TTNT
Thuật giải tô màu
Bài toán
Cho đồ thị đơn vô hướng G = (V,E). Hãy tô mỗi đỉnh của G bằng một màu sao cho: (1) hai đỉnh kề nhau có
màu khác nhau và (2) tổng số lượng màu cần sử dụng là ít nhất.
Lưu ý: đồ thị thường được cho dưới dạng hình vẽ hay ma trận kề.
Ứng dụng
Bài toán tô màu đồ thị được ứng dụng đề biểu diễn cho các bài toán thoả mãn ràng buộc (CSP) như lập lịch,
lập thời khoá biểu… (xem các bài tập đi kèm).
Để giải các bài toán trên, trước tiên ta cần xác định các định các yếu tố trong bài toán tương ứng với các yếu
tố của bài toán tô màu đồ thị bằng cách trả lời cách câu hỏi:
• Màu của đồ thị – Cần làm việc gì?: việc cần làm trong bài toán (vd xếp lịch) chính là hành động tô màu, do
đó màu của đồ thị chính là yếu tố cần xác định (được nêu trong đề bài).
• Đỉnh của đồ thị – Hành động cần làm tác động lên cái gì?: là thành phần được tác động lên
• Cung (cạnh) của đồ thị – Các đỉnh ràng buộc với nhau như thế nào?
Thuật giải: có hai thuật giải chính thường được áp dụng cho bài toán tô màu là thuật giải tô màu theo bậc và
tô màu tham lam (greedy).
Thuật toán tô màu trên đồ thị dựa vào số bậc
Lặp lại các bước sau cho đến khi bậc của tất cả các đỉnh bằng 0 và các đỉnh đã được tô màu:
Bước 1: Tô màu i cho đỉnh có bậc lớn nhất
Bước 2: Hạ bậc.
+ Bậc của đỉnh được tô màu i thì: Bậc = 0
+ Bậc của đỉnh có liên hệ với đỉnh được tô màu i thì: Bậc= Bậc -1
Bước 3: Cấm tô màu i cho các đỉnh vừa bị hạ bậc.
Ví dụ: Tô màu cho bản đồ các nước khu vực láng giềng với Việt Nam
Ma trận kề: ma trận vuông An (11 x 11) trong đó:
A[i,j] = 1 khi hai đỉnh i, j có cạnh nối và = 0 trong trường hợp ngược lại (A[i,i]=0)
Cách trình bày thuật giải:
Xác định bậc của các đỉnh
Đỉnh TQ VN LAO MIA THAI CAM PHI MAL BRU SING INDO
Bậc 3 3 5 3 4 3 0 4 1 1 1

Giả sử có một hội thảo khoa học với 9 chủ đề khác nhau ký hiệu là a, b, c, d, e, f, g, h, i. Mỗi chủ đề sẽ diễn
ra trong 1 buổi và các chủ đề sau không được diễn ra đồng thời: ae, bc, cd, ed, abd, ahi, bhi, dfi, dhi, fgh.
Hãy bố trí các chủ đề trên vào các buổi sao cho số buổi diễn ra là ít nhất.
Các tìm kiếm heuristic theo nguyên lý “tham lam”
Heuristic tham lam là heuristic thường được dùng để giải các bài toán “khó” (các bài toán không thể vét cạn),
ví dụ như bài toán sau:
Bài toán người du lịch (Traveling Saleman Problem - TSP):
Cho n thành phố trong đó hai thành phố bất kỳ đều có đường nối với nhau. Hãy xác định lộ trình cho người
du lịch, xuất phát từ thành phố thứ nhất, đi qua tất cả các thành phố còn lại, trở về thành phố xuất phát với
tổng đoạn đường là nhỏ nhất.
Thuật giải GTS1
Bước 1 [Khởi đầu]: TOUR = {}, COST = 0; v = 1.
Bước 2 [Thăm tất cả các thành phố]: Với k = 1 đến n, thực hiện bước 3.
Bước 3 [Chọn cạnh kế]:
o Chọn (v,w) là cạnh có chi phí nhỏ nhất tính từ v đến các đỉnh chưa sử dụng w.
o Gán TOUR = TOUR + {(v,w)}, COST = COST + C(v,w).
o Sử dụng đỉnh w cho bước kế tiếp: v = w.
Bước 4 [Chuyến đi hoàn thành]: Gán TOUR = TOUR + {(v,1)}
Bài tập 3: Giải bài toán người du lịch với 5 thành phố như hình 3, sử dụng thuật giải GTS1. Chu trình tìm được
có tốt nhất hay không?
Thuật giải GTS2
Nếu không bị ràng buộc bởi thành phố xuất phát, bài toán này có thể được giải tốt hơn bằng thuật giải GTS2:
xuất phát từ P (1<P<N) thành phố ban đầu, sử dụng GTS1 để tìm ra P chu trình cho người đưa thư và
chọn chu trình có tổng chi phí nhỏ nhất.
Bài tập 5 : Giải bài tập 4 với GTS2, xuất phát từ 3 thành phố tùy chọn.
Bài toán phân công công việc
Giả sử ta có:
o N máy: M1, M2, …, MN giống nhau.
o M công việc: V1, V2, …, VM độc lập với nhau. Công việc Vi cần thực hiện trong Ti giờ mới có thể hoàn
thành.

(B) Trời mưa cảm lạnh.∧ ⇒mắc mưa
(C) Mắc mưa
Ta sẽ chứng minh (D) “cảm lạnh” là mệnh đề đúng.
Bài toán được chuyển sang dạng chuẩn thành:
⇒ D, C ∨C ¬ ∨A ¬A, D
Chứng minh:
Tách dòng
A, C =¬1. A, > D
C, C =¬2. A,> D
3. A, D, C => D (được cm)
Chuyển vế:
1. A, C => D, A (được cm)
3. A, C => D, C