Thiết kế thuật toán vét cạn và tham lam

Nội dung của chương này trình bày hai chiến lược thiết kế thuật giải thông dụng là vét cạn và tham lam. Nội dung của chương, ngoài phần trình bày về các phương pháp còn có những ví dụ cụ thể, cả thuật giải và cài đặt, đểngười đọc có một cái nhìn chi tiết về việc từ thuật toán đến chương trình.


1. Vét cạn (Exhausted search)

Vét cạn, duyệt, quay lui… là một sốtên gọi tuy không đồng nghĩa nhưng cùng chỉmột phương pháp rất đơn giản trong tin học: tìm nghiệm của một bài toán bằng cách xem xét tất cảcác phương án có thể. Đối với con người phương pháp này thường là không khảthi vì sốphương án cần kiểm tra quá lớn. Tuy nhiên đối với máy tính, nhờtốc độxửlí nhanh, máy tính có thểgiải rất nhiều bài toán bằng phương pháp vét cạn.
Ưu điểm lớn nhất của phương pháp vét cạn là luôn đảm bảo tìm ra nghiệm chính xác. Ngoài ra phương pháp vét cạn còn có một số ưu điểm so với các phương pháp khác là đòi hỏi rất ít bộ nhớvà cài đặt đơn giản. Hạn chế duy nhất của phương pháp này là thời gian thực thi rất lớn, độ phức tạp thường ở bậc mũ. Do đó vét cạn thường chỉáp dụng tốt với các bài toán có kích thước nhỏ.

LINK DOWNLOAD

Nội dung của chương này trình bày hai chiến lược thiết kế thuật giải thông dụng là vét cạn và tham lam. Nội dung của chương, ngoài phần trình bày về các phương pháp còn có những ví dụ cụ thể, cả thuật giải và cài đặt, đểngười đọc có một cái nhìn chi tiết về việc từ thuật toán đến chương trình.


1. Vét cạn (Exhausted search)

Vét cạn, duyệt, quay lui… là một sốtên gọi tuy không đồng nghĩa nhưng cùng chỉmột phương pháp rất đơn giản trong tin học: tìm nghiệm của một bài toán bằng cách xem xét tất cảcác phương án có thể. Đối với con người phương pháp này thường là không khảthi vì sốphương án cần kiểm tra quá lớn. Tuy nhiên đối với máy tính, nhờtốc độxửlí nhanh, máy tính có thểgiải rất nhiều bài toán bằng phương pháp vét cạn.
Ưu điểm lớn nhất của phương pháp vét cạn là luôn đảm bảo tìm ra nghiệm chính xác. Ngoài ra phương pháp vét cạn còn có một số ưu điểm so với các phương pháp khác là đòi hỏi rất ít bộ nhớvà cài đặt đơn giản. Hạn chế duy nhất của phương pháp này là thời gian thực thi rất lớn, độ phức tạp thường ở bậc mũ. Do đó vét cạn thường chỉáp dụng tốt với các bài toán có kích thước nhỏ.

LINK DOWNLOAD

Chuyên mục: D. Luận văn D. Luận văn chuyên ngành Công nghệ thông tin (Information Technology) D. Luận văn kỹ thuật