Tiểu Luận Phương pháp quay lui

LỜI NÓI ĐẦU
Trong quá trình nghiên cứu giải quyết các vấn đề – bài toán, người ta đã đưa ra những nhận xét như sau:
Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không.
Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng.
Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được.
Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán: tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiên nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ.
Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở cửa cho chúng ta trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra.
Vét cạn, quay lui ,nhánh cận 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 thử sai.
Bài tiểu luận sau đây , sẽ cho chúng ta tìm hiểu rõ hơn về “ Thuật toán quay lui“ Vì kiến thức của chúng em còn nhiều hạn chế nên trong quá trình làm tiểu luận còn có sai sót. Mong cô và các bạn , góp ý. Để bài tiểu luận của chúng em hoàn chỉnh hơn .
Chúng em xin cảm ơn !
MỤC LỤC
I . Tổng quan về phương pháp quay lui
1 . Dấu hiệu nhận biết
2 . Ý tưởng
3 . Mô hình
4 . Lược đồ
5 . Chứng minh tính đúng
6 . Nhận xét
7 . So sánh với “ Vét cạn , Nhánh cận“


II . Phân tích thiết kế một số bài toán cơ bản
1. Liệt kê các dãy nhị phân có độ dài n
2. Phân tích số
3. Liệt kê các chỉnh hợp không lặp k phần tử
4. Người bán hàng
5. Bài toán Balo
6. Bài toán xếp Hậu
7. Chu trình Hamilton


III. Một số lỗi mắc phải khi dùng phương pháp quay lui
1 . Lỗi hay mắc phải
2 . Chú ý !


IV. Tổng kết
1 . Kết luận
2 . Phụ lục


I . Tổng quan về phương pháp quay lui


1.Dấu hiệu nhận biết bài toán có thể sử dụng phương pháp
Một bài toán liệt kê tổ hợp luôn cần phải đảm bảo hai nguyên tắc, đó là: không được bỏ sót một cấu hình và không được trùng lặp một cấu hình. Có thể nói rằng phương pháp liệt kê là cách cuối cùng để có thể giải được một số bài toán tổ hợp hiện nay. Một trong những phương pháp liệt kê có tính phổ dụng cao đó là phươngpháp quay lui.
Một số bài toàn liệt kê đơn giản :
ã Liệt kê các nước Asean ( Đ ÁN : Việt Nam , Lào , Thài Lan )
ã Liệt kê các số nhị phân 3 bit ( Đ ÁN : 000 , 001 , 010 , 100 , )
ã Liệt kê các số tự nhiên chia hết cho 5 ( Đ ÁN : 5,10,15,20,25 )
ã Vv
2 . Ý tưởng của phương pháp
“ Quay đầu là bờ “
Nét đặc trưng của phương pháp lui các bước hướng tới lời giải cuối cùng của bài toán hoàn toàn được làm thử .
Tại mỗi bước , nếu có một lựa chọn được chấp nhận thì ghi nhận lại lựa chọn này và tiến hành các bước thử tiếp theo. Còn ngược lại không có lựa chọn nào thích hợp thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về chu trình thử các lựa chọn còn lại .
Hành động này được gọi là quay lui, thuật toán thể hiện phương pháp này gọi là quay lui.
Điểm quan trọng của thuật toán là phải nghi nhớ mỗi bước đi qua để tránh trùng lặp khi quay lui . Dễ thấy là các thông tin này cần được lưu trữ vào một ngăn xếp , nên thuật toán thể hiện ý thiết kế một cách đệ quy.
3. Mô hình
Lời giải của bài toán thường biểu diễn một vec tơ gồm n phần tử = ( )
Phải thỏa mãn các điều kiện nào đó. Để chỉ ra lời giải x, ta phải xây dựng dần các thành phần lời giải .
Tại bước i :