Tiểu luận giữa kì đề tài: Phương pháp quay lui

Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải thuyết 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ôngCó nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thờigian 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.
Nội dung trích xuất từ tài liệu:
Tiểu luận giữa kì đề tài: Phương pháp quay lui TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA : TOÁN – CƠ – TIN HỌC ---------------   --------------- TIỂU LUẬN GIỮA KÌ Môn học : Thiết kế và đánh giá thuật toán Phương pháp quay lui Đề Tài :Giáo viên hướng Nguyễn Thị Hồng Minhdẫn :Sinh viên thực hiên : Lê Thị Ngọc Ánh Nguyễn Hồng Chương Lê Thị Hiến Trần Thị Thu Hằng (4/9)Lớp : K54A2 Toán Tin Hà Nội : 4 / 2012 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 ranhữ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áiniệ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ảithuậ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 đốivớ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ềutrườ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ảilú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ằngthuậ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ấpnhậ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êuchuẩ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ủathuậ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ácbà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ùngchỉ 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ằngcá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ườnglà 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 quaylui“ 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òncó 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ỤCI . Tổng quan về pháp quay luiphương 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ế số bài toán cơ bảnmột 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 HamiltonIII. Một số lỗi mắc khi dùng phương pháp quay luiphải 1 . Lỗi hay mắc phải 2 . Chú ý !IV. Tổng kết 1 . Kết luận 2 . Phụ lụcI . Tổng quan về phương pháp quay lui1.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ằngphươ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ệnnay. Một trong những phương pháp liệt kê có tính phổ dụng cao đó là phươngpháp quaylui.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 … ) ...