Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình hướng dẫn phân tích kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p5

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. | Giải thuật Kĩ thuật thiết kế giải thuật Khởi đầu nút MAX có giá trị tạm là -TO và nút MIN có giá trị tạm là TO. 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 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 1. 2. của nút đó trở thành giá trị của nó. 3. 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 . 4. 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. Ví dụ 3-7 Vận dụng quy tắc trên để định trị cho nút A của cây trò chơi trong ví dụ 3-5. A là nút MAX vì A không phải là nút lá nên ta gán giá trị tạm là -TO xét B là con của A B là nút lá nên giá trị của nó là giá trị đã được gán 1 giá trị tạm của A bây giờ là max -TO 1 1. Xét con C của A C là nút MIN giá trị tạm lúc đầu của C là TO. Xét con E của C E là nút MAX giá trị tạm của E là -TO. Xét con I của E I là nút lá nên giá trị của nó là 0. Quay lui lại E giá trị tạm của E bây giờ là max -TO 0 0. Vì E chỉ có một con là I đã xét nên giá trị tạm 0 trở thành giá trị của E. Quay lui lại C giá trị tạm mới của C là min TO 0 0. A là nút MAX có giá trị tạm là 1 C là con của A có giá trị tạm là 0 1 0 nên .