Bài giảng Cấu trúc dữ liệu và giải thuật - Kỹ thuật thiết kế giải thuật - Nguyễn Văn Linh

 kỹ thuật phải đi tới tất cả các điểm dừng rồi mới quay lui. “Cắt tỉa Alpha-Beta” và “Nhánh-Cận” là hai kỹ thuật cho phép chúng ta không cần thiết phải đi tới tất cả các điểm dừng, mà chỉ cần đi đến một số điểm nào đó và dựa vào một số suy luận để có thể quay lui sớm. Ðịnh trị cây biểu thức số họcCây biểu thức số học là một cây nhị phân, trong đó các nút lá biểu diễn cho các toán hạng, các nút trong biểu diễn cho các toán tử. Biểu thức 5 + 2 * 3 - 4 sẽ được biểu diễn bởi cây trong hình bên-+45*23Giải thuật quay lui (vét cạn) cho việc định trị cho cây BTSHfloat Eval(node n) {	if (n là lá)	return (trị của toán hạng trong n);	return (Toán tử trong n (Eval (Con trái của n), Eval (Con phải của n)));}Muốn định trị cho cây biểu thức T, ta gọi Eval(ROOT(T)). Cây trò chơi: mô tả Xét một trò chơi trong đó hai người thay phiên nhau đi nước của mình như cờ vua, cờ tướng, carô... Trò chơi có một trạng thái bắt đầu và mỗi nước đi sẽ biến đổi trạng thái hiện hành thành một trạng thái mới. Trò chơi sẽ kết thúc theo một quy định nào đó, theo đó thì cuộc chơi sẽ dẫn đến một trạng thái phản ánh có một người thắng cuộc hoặc một trạng thái mà cả hai đấu thủ không thể phát triển được nước đi của mình, ta gọi nó là trạng thái hòa cờ. Ta tìm cách phân tích xem từ một trạng thái nào đó sẽ dẫn đến đấu thủ nào sẽ thắng với điều kiện cả hai đấu thủ đều có trình độ như nhau.Biểu diễn trò chơi bằng cây trò chơiMột trò chơi có thể được biểu diễn bởi một cây trò chơi. Mỗi một nút của cây biểu diễn cho một trạng thái. Nút gốc biểu diễn cho trạng thái bắt đầu của cuộc chơi.Mỗi nút lá biểu diễn cho một trạng thái kết thúc của trò chơi (trạng thái thắng thua hoặc hòa). Nếu trạng thái x được biểu diễn bởi nút n thì các con của n biểu diễn cho tất cả các trạng thái kết quả của các nước đi có thể xuất phát từ trạng thái x. X-điAX-điO-điO-điXXXO0OXXXXO0OXXXXO0OXXXO0XOXOXXXO0OXXXXO0OOXOXXXO0XOBCDXOXXO0XOXXOXO0XOXOXXXO0XOXXXOXO0XOEFGHIJKX-điX-điAX-điMaxO-điMinO-điMinXXXO0OXXXXO0OXXXXO0OXXXO0XOXOXXXO0OXXXXO0OOXOXXXO0XOBCDXOXXO0XOXXOXO0XOXOXXXO0XOXXXOXO0XOEFGHIJK1-1X-điMax001Giải thuật vét cạn định trị cây trò chơi: giả thiết Ta có một hàm Payoff nhận vào một nút lá và cho ta giá trị của nút lá đó.Các hằng  và - tương ứng là các trị Payoff lớn nhất và nhỏ nhất.Khai báo kiểu ModeType = (MIN, MAX) để xác định định trị cho nút là MIN hay MAX.Một kiểu NodeType được khai báo một cách thích hợp để biểu diễn cho một nút trên cây phản ánh một trạng thái của cuộc chơi.Ta có một hàm is_leaf để xác định xem một nút có phải là nút lá hay không? Hàm max và min tương ứng lấy giá trị lớn nhất và giá trị nhỏ nhất của hai giá trị.Hàm Search nhận vào một nút n và kiểu mode của nút đó (MIN hay MAX) trả về giá trị của nút. Giải thuật vét cạn định trị cây trò chơi: cài đặt bằng C/C++float Search(NodeType n, ModeType mode) {	NodeType C; /*C là một nút con của nút n*/	float value;	/*Lúc đầu ta cho value một giá trị tạm,	sau khi đã xét hết tất cả các con của nút n thì value là giá trị của nút n*/	if (is_leaf(n))	return Payoff(n);	/*Khởi tạo giá trị tạm cho n*/	if (mode == MAX) value = -;	else value = ;	/*Xét tất cả các con của n,	mỗi lần xác định được giá trị của một nút con,	ta phải đặt lại giá trị tạm value.	Khi đã xét hết tất cả các con thì value là giá trị của n*/	for (với mỗi con C của n)	if (mode == MAX)	value = max(value, Search(C, MIN));	else	value = min(value, Search(C, MAX));	return value;} Kỹ thuật cắt tỉa Alpha-Beta (Alpha-Beta Pruning)Nếu P là một nút MAX và ta đang xét một nút con Q của nó (dĩ nhiên Q là nút MIN). Nếu Vp ≥ Vq cắt các con chưa xét của Q. Tương tự nếu P là nút MIN (tất nhiên Q là nút MAX) và Vp ≤ Vq thì cắt các con chưa xét của Q. Quy tắc định trị cho một nút không phải là nút lá như sau:Khởi đầu nút MAX có giá trị tạm là - và nút MIN có giá trị tạm là .Nếu tất cả các nút con của một nút đã được xét hoặc bị cắt tỉa thì giá trị tạm của nút đó trở thành giá trị của nó.Nếu một nút MAX n có giá trị tạm là V1 và một nút con của nó có giá trị là V2 thì đặt giá trị tạm mới của n là max(V1,V2). Nếu n là nút MIN thì đặt giá trị tạm mới của n là min(V1,V2).Vận dụng quy tắc cắt tỉa Alpha-Beta nói trên để hạn chế số lượng nút phải xét. X-điAX-điMaxO-điMinO-điMinXXXO0OXXXXO0OXXXXO0OXXXO0XOXOXXXO0OXXXXO0OOXOXXXO0XOBCDXOXXO0XOXXOXO0XOXOXXXO0XOXXXOXO0XOEFGHIJK1-1X-điMax001Cài đặt giải thuật cắt tỉa alpha – beta định trị cây trò chơifloat cat_tia(NodeType Q, ModeType mode, float Vp) {	NodeType C; /*C là một nút con của nút Q*/	float Vq;	/*Vq là giá trị tạm của Q, sau khi tất cả các con của nút Q đã xét hoặc bị cắt tỉa thì Vq là giá trị của nút Q*/	if (is_leaf(Q)) return Payoff(Q);	/* Khởi tạo giá trị tạm cho Q */	if (mode == MAX) Vq = -;	else Vq = ;	/*Xét các con của Q, mỗi lần xác định được giá trị của một nút con của Q, ta phải đặt lại giá trị tạm Vq và so sánh với Vp để có thể cắt tỉa hay không*/Xét C là con trái nhất của Q;while (C là con của Q) { if (mode == MAX) {	Vq = max(Vq, Cat_tia(C, MIN, Vq)); 	if (Vp= Vq) return Vq;	}return Vq;} Kỹ thuật nhánh cận Nhánh cận là kỹ thuật xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh.Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có, mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n. Kỹ thuật này gọi là phân nhánh.Vói mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị gần với giá của các phương án. Với bài toán tìm min ta sẽ xác định cận dưới còn với bài toán tìm max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án. Kỹ thuật nhánh cận: bài toán TSPCây tìm kiếm phương án là cây nhị phân trong đó: Nút gốc là nút biểu diễn cho cấu hình gồm tất cả các phương án.Con trái biểu diễn cho cấu hình gồm tất cả các phương án chứa một cạnh nào đó, con phải biểu diễn cho cấu hình gồm tất cả các phương án không chứa cạnh đó (các cạnh để xét phân nhánh được thành lập tuân theo một thứ tự nào đó, chẳng hạn thứ tự từ điển).Mỗi nút sẽ kế thừa các thuộc tính của tổ tiên của nó và có thêm một thuộc tính mới (chứa hay không chứa một cạnh nào đó).Nút lá biểu diễn cho một cấu hình chỉ bao gồm một phương án.Ðể quá trình phân nhánh mau chóng tới nút lá, tại mỗi nút ta cần có một quyết định bổ sung dựa trên nguyên tắc là mọi đỉnh trong chu trình đều có cấp 2 và không tạo ra một chu trình thiếu. Kỹ thuật nhánh cận: bài toán TSP – ví dụ:2864376543edcabKỹ thuật nhánh cận: bài toán TSP- Phân nhánh	Các cạnh theo thứ tự từ điển để xét là:ab, ac, ad, ae, bc, bd, be, cd, ce và de.Tất cả các phương ánBabacACDETính cận dưới cho nút gốc A Ðỉnh a chọn ad = 2, ab = 3Ðỉnh b chọn ba = 3, be = 3Ðỉnh c chọn ca = 4, cb = 4Ðỉnh d chọn da = 2, dc = 5Ðỉnh e chọn eb = 3, ed = 6	Tổng độ dài các cạnh được chọn là 35, cận dưới của nút gốc A là 35/2 = 17.52864376543edcabTính cận dưới cho nút D Ðỉnh a chọn ab = 3, ac = 4, do hai cạnh này buộc phải chọn. Ðỉnh b chọn ba = 3, be = 3Ðỉnh c chọn ca = 4, cb = 4Ðỉnh d chọn de = 6, dc = 5, do không được chọn da nên ta phải chọn de.Ðỉnh e chọn eb = 3, ed = 6	Tổng độ dài các cạnh được chọn là 41, cận dưới của nút D là 41/2 = 20.5 2864376543edcabÁp dụng kỹ thuật nhánh cận cho bài toán TSPXây dựng nút gốc, tính cận dưới cho nút gốc.Sau khi phân nhánh cho mỗi nút, ta tính cận dưới cho cả hai con.Nếu cận dưới của một nút con >= giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì ta không cần xây dựng các cây con cho nút này nữa (Ta gọi là cắt tỉa các cây con của nút đó). Nếu cả hai con đều có cận dưới nhỏ hơn giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì nút con nào có cận dưới nhỏ hơn sẽ được ưu tiên phân nhánh trước. Mỗi lần quay lui để xét nút con chưa được xét của một nút ta phải xem xét lại nút con đó để có thể cắt tỉa các cây của nó hay không vì có thể một phương án có giá nhỏ nhất tạm thời vừa được tìm thấy.Sau khi tất cả các con đã được phân nhánh hoặc bị cắt tỉa thì phương án có giá nhỏ nhất trong các phương án tìm được là phương án cần tìm.Trong quá trình xây dựng cây có thể ta đã xây dựng được một số nút lá, như ta biết mỗi nút lá biểu diễn cho một phương án. Giá nhỏ nhất trong số các giá của các phương án này được gọi là giá nhỏ nhất tạm thời. Ví dụKỹ thuật nhánh cận: BTcái ba lôDanh sách các đồ vật được sắp xếp theo thứ tự giảm của đơn giá Nút gốc biểu diễn cho trạng thái ban đầu của ba lô, ở đó ta chưa chọn một vật nào. Tổng giá trị được chọn TGT = 0. Cận trên của nút gốc CT = W * Ðơn giá lớn nhất.Nút gốc sẽ có các nút con tương ứng với các khả năng chọn đồ vật có đơn giá lớn nhất. Với mỗi nút con ta tính lại các thông số:TGT = TGT (của nút cha) + số đồ vật được chọn * giá trị mỗi vật.W = W (của nút cha) - số đồ vật được chọn * trọng lượng mỗi vật.CT = TGT + W * Ðơn giá của vật sẽ xét kế tiếp.Kỹ thuật nhánh cận: BTcái ba lôTrong các nút con, ta sẽ ưu tiên phân nhánh cho nút con nào có cận trên lớn hơn trước. Các con của nút này tương ứng với các khả năng chọn đồ vật có đơn giá lớn tiếp theo. Với mỗi nút ta lại phải xác định lại các thông số TGT, W, CT theo công thức đã nói trong bước 2.Lặp lại bước 3 với chú ý: đối với những nút có cận trên nhỏ hơn hoặc bằng giá lớn nhất tạm thời của một phương án đã được tìm thấy thì ta không cần phân nhánh cho nút đó nữa (cắt bỏ).Nếu tất cả các nút đều đã được phân nhánh hoặc bị cắt bỏ thì phương án có giá lớn nhất là phương án cần tìm. Kỹ thuật nhánh cận: BTcái ba lô - Ví dụ	Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng bên dưới:ĐVTLGTA1530B1025C22D46ĐVTLGTĐGB10252.5A15302.0D461.5C221.0TGT =0W=37,CT = 92.5ATGT=75W=7CT = 89TGT=50W=17CT = 84TGT=25W=27CT = 79TGT=0W=37CT = 74BCDETGT=75W=7CT=85.5ETGT=81W=3CT = 84GTGT=75W=7CT = 82HTGT=83W=1ITGT=81W=3JTGT=80W=2CT = 83KTGT=50W=17CT=75.25LCắt tỉaXB=3XB=2XB=1XB=0XA=0XA=1XA=0XD=1XD=0XC=1XC=0ĐVTLGTĐGB10252.5A15302.0D461.5C221.0