Giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p5

Tham khảo tài liệu 'giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p5', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p5 h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y . bu bu Giải thuật Kĩ thuật thiết kế giải thuật to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k Chúng ta cố gắng tìm một cách sao cho khi định trị một nút thì không nhất thiết phải định trị cho tất cả các nút con cháu của nó. Trước hết ta có nhận xét như sau: 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). Giả sử Vp là một giá trị tạm của P, Vq là một giá trị tạm của Q và nếu ta có Vp ≥ Vq thì ta không cần xét các con chưa xét của Q nữa. Vì nếu có xét thì giá trị của Q cũng sẽ nhỏ hơn hoặc bằng Vq và do đó không ảnh hưởng gì đến Vp. Tương tự nếu P là nút MIN (tất nhiên Q là nút MAX) và Vp ≤ Vq thì ta cũng không cần xét đến các con chưa xét của Q nữa. Việc không xét tiếp các con chưa được xét của nút Q gọi là việc cắt tỉa Alpha-Beta các con của nút Q. Trên cơ sở nhận xét đó, ta nêu ra quy tắc định trị cho một nút không phải là nút lá trên cây như sau: Khởi đầu nút MAX có giá trị tạm là -∞ và nút MIN có ...