TAILIEUCHUNG - Giáo trình giải thuật của Nguyễn Văn Linh part 11

• 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. Nếu nút n là nút lá thì trả về giá trị. | Giải thuật Kĩ thuật thiết kế giải thuật 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. Nếu nút n là nút lá thì trả về giá trị đã được gán cho nút lá. Ngược lại ta cho n một giá trị tạm value là -œ hoặc œ tùy thuộc n là nút MAX hay MIN và xét con của n. Sau khi một con của n có giá trị V thì đặt lại value max value V nếu n là nút MAX và value min value V nếu n là nút MIN. Khi tất cả các con của n đã được xét thì giá trị tạm value của n trở thành giá trị của nó. FUNCTION Search n NodeType mode ModeType real VAR C NodeType C là một nút con của nút n Value real 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 BEGIN IF is_leaf n THEN RETURN Payoff n ELSE BEGIN Khởi tạo giá trị tạm cho n IF mode MAX THEN 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 DO IF mode MAX THEN Value max Value Search C MIN ELSE Value min Value Search C MAX RETURN value END END Kĩ thuật cắt tỉa Alpha-Beta Alpha-Beta Pruning Trong giải thuật vét cạn ở trên ta thấy để định trị cho một nút nào đó ta phải định trị cho tất cả các nút con cháu của nó và muốn định trị cho nút gốc ta phải định trị cho tất cả các nút trên cây. Số lượng các nút trên cây trò chơi tuy hữu hạn nhưng không phải là ít. Chẳng hạn trong cây trò chơi ca rô nói trên nếu ta có bàn cờ bao gồm n ô thì có thể có tới n nút trên cây trong trường hợp trên là 9 . Đối với các loại cờ khác như cờ vua chẳng hạn thì số lượng các nút còn lớn hơn nhiều. Ta gọi là một sự bùng nổ tổ hợp các nút. .

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao