TAILIEUCHUNG - 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 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. Đị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 .

• 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