Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình giải thuật của Nguyễn Văn Linh part 10

KĨ THUẬT QUAY LUI Kĩ thuật quay lui (backtracking) như tên gọi của nó, là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua. Tại mỗi bước phân tích chúng ta chưa giải quyết được vấn đề do còn thiếu cứ liệu nên cứ phải phân tích cho tới các điểm dừng, nơi chúng ta xác định được lời giải của chúng hoặc là xác định được là không thể (hoặc không nên) tiếp tục theo hướng này. Từ các điểm dừng này chúng ta quay ngược trở lại theo. | Giải thuật Kĩ thuật thiết kế giải thuật 3.5 KĨ THUẬT QUAY LUI Kĩ thuật quay lui backtracking như tên gọi của nó là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua. Tại mỗi bước phân tích chúng ta chưa giải quyết được vấn đề do còn thiếu cứ liệu nên cứ phải phân tích cho tới các điểm dừng nơi chúng ta xác định được lời giải của chúng hoặc là xác định được là không thể hoặc không nên tiếp tục theo hướng này. Từ các điểm dừng này chúng ta quay ngược trở lại theo con đường mà chúng ta đã đi qua để giải quyết các vấn đề còn tồn đọng và cuối cùng ta sẽ giải quyết được vấn đề ban đầu. Ở đây chúng ta sẽ xét 3 kĩ thuật quay lui vét cạn là 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. Các kĩ thuật này sẽ được trình bày thông qua một số bài toán cụ thể sau. 3.5.1 Định trị cây biểu thức số học Trong các ngôn ngữ lập trình đều có các biểu thức số học việc dịch các biểu thức này đòi hỏi phải đánh giá định trị chúng. Để làm được điều đó cần phải có một biểu diễn trung gian cho biểu thức. Một trong các biểu diễn trung gian cho biểu thức là cây biểu thức. Câ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ử. Ví dụ 3-3 Biểu thức 5 2 3 - 4 sẽ được biểu diễn bởi cây trong hình 38 Trị của một nút lá chính là trị của toán hạng mà nút đó biểu diễn. Trị của một nút trong có được bằng cách lấy toán tử mà nút đó biểu diễn áp dụng vào các con của nó. Trị của nút gốc chính là trị của biểu thức. Hình 3-7 Một cây biểu thức số học Như vậy để định trị cho nút gốc chúng ta phải định trị cho hai con của nó đối với mỗi con ta xem nó có phải là nút lá hay không nếu không phải ta lại phải xét hai con của nút đó. Quá trình cứ tiếp tục như vậy cho tới khi gặp các nút lá mà giá trị của .