Bạn đang xem 20 trang mẫu của tài liệu "Sáng kiến kinh nghiệm Thuật toán quay lui và ứng dụng giải bài toán tối ưu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Phần 1: ĐẶT VẤN ĐỀ Kính thưa quý thầy cô giáo! Tiến sĩ triều Lê, Thân Nhân Trung đã nói “Hiền tài là nguyên khí của quốc gia, nguyên khí thịnh thì thế nước mạnh mà hưng thịnh, nguyên khí suy thì thế nước yếu mà thấp hèn”. Vì thế các bậc đế vương thánh minh luôn coi việc giáo dục nhân tài, kén chọn kẻ sĩ, vun trồng nguyên khí quốc gia làm công việc hàng đầu..., câu nói bất hủ của Thân Nhân Trung đã cho thấy từ thời xa xưa các thế hệ ông cha đã rất coi trọng nhân tài và coi những nhân tài là tương lai của đất nước. Với cương vị là một giáo viên chuyên ngành Tin học trực tiếp giảng dạy, tôi thấy được những nhiệm vụ quan trọng phải làm đầu tiên đó là làm thế nào để học sinh thích học và học giỏi môn Tin. Trong thời đại ngày nay, Tin học có vai trò và vị trí đặc biệt quan trọng trong khoa học kĩ thuật và đời sống, giúp con người tiếp thu một cách dễ dàng các môn khoa học khác có hiệu quả. Có thể nói phát hiện và bồi dưỡng HSG là một trong những hoạt động chuyên môn chính trong năm học của trường. Bản thân qua tham khảo các đề thi HSG của tỉnh và quốc gia đã thấy hầu hết các đề thi đều có các bài toán tối ưu. Để giải các bài toán tôi ưu thì có nhiều phương pháp giải, trong đó ứng dụng thuật toán quay lui để giải bài toán tối ưu cũng là một phương pháp được nhiều người sử dụng. Đó cũng chính là lý do để tôi viết đề tài “Thuật toán quay lui và ứng dụng giải bài toán tối ưu”. Tôi rất mong được sự góp ý của quý thầy cô để đề tài ngày càng được hoàn thiện hơn. Xin chân thành cảm ơn! Phần 2: NHỮNG BIỆN PHÁP GIẢI QUYẾT VẤN ĐỀ
- CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ: Cũng như trình bày ở trên bài toán tối ưu là một trong những bài toán thường gặp trong các kỳ thi học sinh giỏi. Công việc khó khăn ở đây là làm thế nào để các em có thể hiểu được thuật toán và có thể ứng dụng vào giải các bài toán liên quan. Xuất phát từ thực tiễn như vậy, tôi đã đưa ra một số bước giúp cho các em có thể hiểu được thuật toán và ứng dụng để giải các bài toán cùng loại: Ý tưởng của thuật toán. Thuật toán. Ứng dụng thuật toán giải các bài toán đơn giản. Ứng dụng thuật toán quay lui có đánh giá cận giải một số bài toán phức tạp. Ứng dụng thuật toán giải bài toán trong các đề thi học sinh giỏi. II. THỰC TRẠNG CỦA VẤN ĐỀ:
- Thực trạng về cấp quản lý
*] Ưu điểm:
- Đã quan tâm vào công tác phát triển mũi nhọn.
- Có sự phân công nhiệm vụ cho từng giáo viên trực tiếp giảng dạy, giám sát và kiểm tra quá trình thực hiện của giáo viên.
- Động viên tinh thần cũng như tạo mọi điều kiện thuận lợi nhất để giáo viên thực hiện nhiệm vụ. *] Hạn chế: Khi phân công nhiệm vụ thì chưa xác định một chiến lược lâu dài, đó là chỉ tập trung phát hiện và bỗi dưỡng học sinh lớp 11 mà không phát hiện và bồi dưỡng ngay từ khi các em đang học lớp 10.
- Thực trạng về giáo viên *] Ưu điểm:
- Được đào tạo về chuyên môn cơ bản, có sức khỏe, sức trẻ, có lòng nhiệt tình trong công việc. Luôn luôn học tập trau dồi tri thức, nhằm phục vụ tốt nhất cho sự nghiệp giáo dục.
- Trong quá trình giảng dạy, tuy gặp nhiều khó khăn nhưng phần lớn các thầy cô giáo đều đặt chữ “tâm” lên hàng đầu, đây là một trong những thuận lợi góp phần vào sự thành công của ngành giáo dục.
- Có sự đầu tư vào nghiên cứu khi được giao nhiệm vụ. *] Hạn chế: Một số giáo viên không có tâm huyết, chưa tập trung vào công tác chuyên môn nên kiến thức về ôn luyện học sinh giỏi còn hạn chế. Việc bồi dưỡng HSG chỉ tập trung cho số ít giáo viên trong tổ.
- Thực trạng về học sinh *] Ưu điểm:
- Các em HS ngoan, cần cù chịu khó, có ý thức vươn lên trong học tập.
- Có trách nhiệm với việc học tập, trong quá trình học tập hăng say phát biểu, đóng góp nên sự thành công của bài giảng. *] Hạn chế:
- Kiến thức cơ bản về lập trình còn rất nhiều hạn chế, chỉ có số ít em học sinh trên địa bàn thị trấn, mới được tiếp cận với lập trình ở chương trình lớp 8 – THCS.
- Đa số các em học tốt môn Tin học thì lại học tốt các môn khoa học tự nhiên [Toán, Lí, Hóa], nên đã theo tham gia bồi dưỡng ở các bộ môn đó.
- Tin học là môn mà không có trong các kỳ thi tốt nghiệp cũng như đại học hàng năm, nên các em cũng không mặn mà với việc tham gia học và bồi dưỡng HSG.
- Thực trạng về cơ sở vật chất
*] Ưu điểm:
- Có đủ cơ sở vật chất để phục vụ cho lớp học.
- Có các phương tiện phục vụ cho mục đích giảng dạy , VD: Bảng từ, máy chiếu, máy tính... *] Hạn chế:
- Thiếu tài liệu và sách tham khảo.
- Một số học sinh không có đủ kinh phí mua máy tính cá nhân phục vụ cho mục đích ôn tập tại nhà. III. CÁC BIỆN PHÁP ĐÃ TIẾN HÀNH ĐỂ GIẢI QUYẾT VẤN ĐỀ:
- Thuật toán quay lui: Giả thiết một cấu hình cần tìm được mô tả bởi một bộ phận gồm n thành phần a1, a2,...an. Giả sử tìm được i - 1 thành phần a1, a2, ai-1, ta tìm thành phần thứ i bằng cách duyệt tất cả các khả năng có thể của ai. Với mỗi khả năng j kiểm tra xem nó có chấp nhận được không. Xảy ra hai trường hợp:
- Chấp nhận được thì xác định ai theo j và kiểm tra xem i = n chưa, nếu i = n thì ta ghi nhận một cấu hình, còn nếu i fopt then Nhanh_can[i+1];
weight:=weight-a[i]x[i];
Cost:=cost-c[i]x[i];
End;
End;
Procedure Inkq;
Var i,j:integer;
Begin
Writeln[' KET QUA TINH TOAN *'];
Writeln['Tong gia tri cua cac do vat: ', fopt:4:0];
Writeln['Phuong an lay do:'];
For j:=1 to n do writeln['So luong do vat ',ind[j],' la: ',xopt[j]:4,' lan'];
Writeln[''];
Write['Nhan enter de tiep tuc']; readln; End; BEGIN Clrscr; Readfile; Khoitao; Nhanh_can[1]; Inkq; Readln; END. Giả sử ta có File dữ liệu là Caitui.txt trong ổ G có nội dung: 4 20 3 5 4 6 20 10 8 15 Thì sau khi chay xong chương trình ta có kết quả: Cho ten file du lieu: G:\caitui.txt Trong luong cai tui: 20 VEC TO GIA TRI DO VAT: 20 10 8 15 3 5 4 6
KET QUA TINH TOAN*Tong gia tri cua cac do vat: 120 Phuong an lay do: So luong do vat 1 la: 6 lan. So luong do vat 4 la: 0 lan. So luong do vat 3 la: 0 lan. So luong do vat 2 la: 0 lan.
Bài 2: Bài toán người du lịch Một người du lịch muốn đi tham quan n thành phố T1, T2,..., Tn. Xuất phát từ một thành phố nào đó người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, rồi quay lại thành phố xuất phát. Cij là chi phí đi từ thành phố Ti đến thành phố Tj [i,j=1,2,...,n], hãy tìm một hành trình [một cách đi thỏa mãn điều kiện đặt ra] với tổng chi phí nhỏ nhất. Cố định thành phố xuất phát là T1, bài toán người du lịch dẫn về bài toán: Với điều kiện [x2,x3,...,xn] là hoán vị của các số 2,3,...,n. Ký