Bài giảng Cơ sở lập trình nâng cao - Chương 5: Phương pháp thiết kế thuật toán Nhánh cận - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – NHÁNH CẬN – 
Chương 5 
Nội dung 
Giới thiệu 
Bài toán tối ưu 
Phương pháp 
Sơ đồ cài đặt 
Các ví dụ 
Hình ảnh 
Giới thiệu 
Bài toán tối ưu: Trong nhiều bài toán thực tế yêu cầu chúng tìm nghiệm thỏa mãn những điều kiện nào đó và nghiệm này phải tốt nhất theo tiêu chí cụ thể nào đó. 
Phương pháp Nhánh cận là một dạng cải tiến của phương pháp quay lui dùng để giải quyết bài toán tối ưu 
Bài toán tối ưu 
Phát biểu bài toán: Giả sử bài toán yêu cầu tìm phương án X=(x 1 , x 2 , , x k , ) thỏa mãn những điền kiện nào đó và phương án này là tốt nhất theo tiêu chí cụ thể nào đó. 
Gọi f(X) là hàm đánh giá sự tốt nhất của phương án X (f là hàm mục tiêu hay hàm chi phí) 
Yêu cầu: Tìm X sao cho 
f(X) min (max) 
Bài toán tối ưu 
Nếu gọi X* là phương án tốt nhất (tối ưu) 
f* = f(X*) được gọi là giá trị tối ưu của bài toán 
Bài toán tối ưu 
Ví dụ 1 [Bài toán người du lịch – Traveling Salesman Problem – TSP]Cho n thành phố được đánh số từ 1 đến n và khoảng cách giữa thành phố i và thành phố j được cho bởi c ij (chú ý: c ij =c ji )Yêu cầu: Tìm một hành trình ngắn nhất cho phép viếng thăm n thành phố, mỗi thành phố viếng thăm đúng 1 lần và quay về thành phố ban đầu. 
Bài toán tối ưu 
Mô hình toán học: 
Một hành trình là 1 hoán vị X=(x(1), x(2), , x(n)) của n số {1, 2, , n} 
Hàm mục tiêu: 
Yêu cầu: 
Bài toán tối ưu 
Ví dụ 2 [Bài toán phân công – Job Assignment Problem – JAP]Có n công việc và n nhân viên. Gọi c ij là chi phí để trả cho nhân viên i khi làm công việc j. Yêu cầu: Tìm cách phân công n nhân viên làm n việc trên sao cho tổng chi phí là nhỏ nhất (một nhân viên chỉ làm 1 việc, một việc chỉ do 1 nhân viên làm). 
Bài toán tối ưu 
Mô hình toán học: 
Một cách phân công n nhân viên làm n việc là 1 hoán vị X=(x(1), x(2), , x(n)) của n số {1, 2, , n} 
Hàm mục tiêu: 
Yêu cầu: 
Bài toán tối ưu 
Ví dụ 3 [Bài toán cái túi – 0-1 Knapsack problem]Cho n loại đồ vật được đánh số từ 1 đến n, đồ vật thứ i có giá trị v i và trọng lượng w i . Cho trước cái túi có trọng lượng tối đa mà nó có thể mang là W. Yêu cầu: Tìm một số đồ vật để bỏ vào túi sao cho tổng trọng lượng các đồ vật bỏ vào túi không vượt quá W và tổng giá trị của các đồ vật là lớn nhất. 
Bài toán tối ưu 
Nhận xét: 
Hình thức thông thường nhất của bài toán là bài toán 0-1 knapsack, trong đó giới hạn số lượng x i của loại đồ vật i là 0 hay 1 
Bài toán tối ưu 
Mô hình toán học: 
Một phương án chọn đồ vật được biểu diễn bằng 1 vector nhị phân độ dài n: X=(x 1 , x 2 , , x n ). (x i {0, 1}) 
x i =1: Chọn đồ vật i 
x i =0: Không chọn đồ vật i 
Tổng giá trị của các đồ vật đã chọn 
Tổng trọng lượng của các đồ vật đã chọn 
Bài toán tối ưu 
f là hàm mục tiêu phải thỏa mãn điều kiện hàm g 
Yêu cầu: 
Phương pháp 
Phương pháp Nhánh cận (Branch and bound – B&B) 
Giả sử ta tìm được hàm g(x 1 , x 2 , , x k ) là hàm cận dưới của nghiệm có k thành phần	 g(x 1 , x 2 , , x k ) ≤ min{f(X)} 
Phương pháp 
Bước 1 [Khởi tạo]: Dùng 2 biến X t và F t để lưu lại nghiệm tốt nhất trong quá trình tìm nghiệm (F t = f(X t )) 
X t = () 
F t = + 
Bước 2 [Quay lui]: Dùng phương pháp quy lui để xét tất cả các nghiệm có thể có của bài toán 
Khi tìm được 1 nghiệm, ta so sánh f(X) với F t . Nếu F t > f(X) thì ta lưu nghiệm tốt hơn lại. 
X t = X 
F t = f(X) 
Phương pháp 
Bước 3 [Nhánh cận]: 
Trong quá trình xây dựng nghiệm, giả sử đã xây dựng được nghiệm gồm k thành phần X=(x 1 , x 2 , , x k ). 
Bây giờ ta dự định mở rộng nghiệm thành (x 1 , x 2 , , x k , x k+1 ) nhưng nếu ta biết rằng những nghiệm mở rộng (x 1 , x 2 , , x k , x k+1 , ) không thể tốt hơn F t (nghĩa là g(x 1 , x 2 , , x k , x k+1 , ) > F t ) thì ta không cần mở rộng (x 1 , x 2 , , x k ), chúng ta cắt đi những nghiệm (nhánh) không cần thiết. 
Phương pháp 
Nhận xét 
Phương pháp nhánh cận không quét qua toàn bộ các nghiệm có thể có của bài toán 
Khó khăn của phương pháp nhánh cận là làm thế nào đánh giá được các nghiệm mở rộng (cận). Nếu đánh giá tốt sẽ bỏ nhiều nghiệm không cần thiết phải xét (nhánh) 
Sơ đồ cài đặt 
void BranchAndBound1( int i){	 if (thỏa điều kiện bài toán F)	{	Tìm được một nghiệm	Cập nhật X t và F t	} 	 else 	 for (j D i )	{	x i = j;	 if (g(x 1 , x 2 , , x i ) < F t )	BranchAndBound1(i+1);	}} 
Sơ đồ 1 
Sơ đồ cài đặt 
void BranchAndBound2( int i){	 for (j D i )	{	x i = j; 	 if (thỏa điều kiện bài toán F)	{	Tìm được một nghiệm	Cập nhật Xt và Ft	} 	 else 	 if (g(x 1 , x 2 , , x i ) < F t )	BranchAndBound2(i+1);	}} 
Sơ đồ 2 
Ví dụ: 
Ví dụ [Bài toán người du lịch – Traveling Salesman Problem – TSP] 
Mô hình toán: 
Một hành trình là 1 hoán vị X=(x(1), x(2), , x(n)) của n số {1, 2, , n} 
Hàm mục tiêu 
Không mất tính tổng quát: Chúng ta có thể xuất phát từ thành phố số 1 
Ví dụ: 
Tìm cận dưới g(x 1 , x 2 , , x k ) 
Cách 1: g(x 1 , x 2 , , x k ) = f(x 1 , x 2 , , x k ) 
Thuật toán: 
Bước 1 [Khởi động]: F t =+ 
Bước 2 [Quay lui] 
Bước 3 [Nhánh cận]: Với mỗi bước thử x i chúng ta kiểm tra độ dài đường đi đến lúc đó có nhỏ hơn F t không. Nếu không nhỏ hơn thì chọn giá trị khác cho x i 
Ví dụ: 
cài đặt 
void TSP1( int i){} 
Ví dụ: 
Tìm cận dưới g(x 1 , x 2 , , x k ) 
Cách 2: 
Gọi c min = min {c ij } là độ dài của đoạn đường đi nhỏ nhất giữa các thành phố 
Giả sử đã đi qua k thành phố X=(x 1 , x 2 , , x k ). Độ dài đường đi qua k thành phố này là 
Cần phải đi qua (n-k) thành phố nữa, hay phải qua (n-k+1) đoạn đường, mỗi đoạn đường có khoảng cách không ít hơn c min . 
Cận dưới: g(x 1 , x 2 , , x k ) = T + (n-k+1)c min 
Ví dụ: 
Thuật toán: 
Bước 1 [Khởi động]: F t =+ 
Bước 2 [Quay lui] 
Bước 3 [Nhánh cận]: Với mỗi bước thử x i chúng ta kiểm tra T+(n-k+1)*c min có nhỏ hơn F t không. Nếu không nhỏ hơn thì chọn giá trị khác cho x i 
Ví dụ: 
cài đặt 
void TSP2( int i){} 
HẾT CHƯƠNG 5