Đề tài Ứng dụng một số nguyên tắc sáng tạo để giải quyết vấn đề bài toán trong tin học và ứng dụng giải bài toán 8 số trên máy tính

....................................................................................... 1 CHƯƠNG 1: VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT .......................................................................................................... 4 1.1. Vấn đề khoa học ...................................................................................... 4 1.1.1. Khái niệm ............................................................................................. 4 1.1.2. Phân loại ............................................................................................... 4 1.1.3. Các tình huống vấn đề .......................................................................... 5 1.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế .... 7 1.2.1. Vepol .................................................................................................... 7 1.2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế . 8 1.2.3. Một số thủ thuật, nguyên tắc về phát minh, sáng tạo ............................. 9 CHƯƠNG 2: CÁC PHƯƠNG PHÁP NGHIÊN CỨU, GIẢI QUYẾT VẤN ĐỀ BÀI TOÁN TRONG TIN HỌC ............................................................. 21 2.1. Mục đích nghiên cứu giải quyết bài toán trong tin học .......................... 21 2.2. Các phương pháp thường dùng để giải quyết vấn đề bài toán trên máy tính ............................................................................................................... 21 2.2.1. Phương pháp trực tiếp......................................................................... 21 2.2.2. Phương pháp gián tiếp hoặc tìm kiếm lời giải ..................................... 24 2.2.3. Các phương pháp Heuristic................................................................. 25 2.2.4. Các phương pháp trí tuệ nhân tạo ....................................................... 25 CHƯƠNG 3: LÝ THIẾT TRÒ CHƠI 8 SỐ .................................................. 26 3.1. Tìm hiểu trò chơi 8 số ............................................................................ 26 3.1.1. Mục đích giải quyết bài toán 8 số trên máy tính .................................. 26 3.1.2. Mô tả .................................................................................................. 28 3.1.3. Xác định trạng thái đích ...................................................................... 29 3.2. Thuật toán tìm đáp án ............................................................................ 30 3.2.1. Giới thiệu về A* ................................................................................. 30 3.2.2. Chi tiết thuật toán A*.......................................................................... 32 3.3. Cài đặt giải thuật ................................................................................... 38 3.3.1. Cài đặt giải thuật................................................................................. 38 3.3.2. Hướng dẩn sử dụng ............................................................................ 38 TÀI LIỆU THAM KHẢO ............................................................................ 39 1 MỞ ĐẦU Tất cả chúng ta công nhận rằng một nước muốn giàu có hùng mạnh không những chúng ta có nhiều tài nguyên khoáng sản, có nhiều ruộng đất, tiền của… mà điều quan trọng là để đất nước ta phát triển ta phải có nhiều người tài giỏi để phát hiện ra cái hay cái mới nâng cao dần sự hoàn thiện để sự giàu có của con người và sự phồn vinh của xã hội. Như ta đã biết Việt Nam đang gia nhập với các nước trên thế giới. Nếu con ngưởi Việt Nam chỉ có cần cù mà không thông minh và nếu chúng ta đi theo lối mòn kế thừa những cái có sẵn thì chúng ta rất dễ bị lạc hậu. Tôi xin kể một câu chuyện như sau: Ngày xưa, có một anh thanh niên khỏe mạnh ít học nhưng có sức khỏe rất cường tráng. Một ngày nọ anh đi tìm việc làm và được một ông chủ khai thác gỗ nhận vào làm công việc khai thác gỗ. Anh thanh niên rất mừng rỡ. Anh được ông chủ phát cho một cái rìu. Hôm làm việc đầu tiên, anh thanh niên hăng hái vào rừng khai thác gỗ. Anh khai thác được 14 góc gỗ. Ông chủ rất hài lòng và khen anh ta. Anh thanh niên rất vui mừng và nghỉ thầm ngày mai sẽ cố gắng hơn nữa. Ngày làm việc thứ hai, anh thanh niên thức sớm hơn ngày đầu và làm việc rất vất vả đến chiều. Anh khai thác được 12 góc gỗ. Để động viên được tinh thần làm việc của anh ta ông chủ vẫn khen anh ta. Anh thanh niên thấy được lòng tốt của ông chủ và nguyện với lòng ngày mai sẽ cố gắng hơn ngày hôm trước: Ngày làm việc thứ ba, anh thanh niên thức sớm hơn ngày làm việc thứ hai và làm việc cả ngày và không hề nghỉ trưa. Kết quả hôm làm việc thứ ba anh đã cố gắng làm việc hơn hai ngày đầu nhưng kết quả chỉ được 11 góc gỗ. Anh thanh niên rất buồn và nói với ông chủ rằng: 2 Thưa ông tôi rất cố gắng hết sức nhưng kết quả ngày càng không tăng mà có xu hướng giảm. Ông chủ trả lời: anh là một người rất chăm chỉ làm việc nhưng anh không biết nâng cấp dụng cụ lao động. Ví dụ cái rìu anh ngày đầu nó rất bén nên anh khai thác được nhiều gỗ nhưng đến một ngày nào đó nó không còn bèn nữa, đó là nói đến thời gian gần, nếu nói đến một thời điểm xa hơn nó không còn phù hợp nữa mà phải thay bằng một dụng cụ khác. Ông chủ nói tiếp, ngoài việc nâng cấp dụng cụ lao động anh còn phải biết sáng tạo trong lao động, anh phải suy nghĩ làm thế nào để tốn ít sức lao động và công việc đạt được nhiều hiệu quả hơn. Từ câu chuyện của anh thanh niên ta rút ra được bài học là nghiên cứu sáng tạo ra cái mới là rất cần thiết cho mỗi con người chúng ta nói riêng và sự phát triển của xã hội nói chung. Theo Gaudin, chúng ta không thể bằng lòng với vốn kiến thức quá hạn hẹp thu nhận được trong những năm ngồi trên ghế nhà trường, mà phải học suốt đời, phải có đủ vốn kiến thức về phương pháp để tự mình học tập, nghiên cứu suốt đời. Có người đưa ra định nghĩa về cuộc đời như sau: “Cuộc đời là chuỗi đề cần giải quyết và chuỗi quyết định cần phải ra”. Thật vậy mỗi ngày chúng ta phải đối mặt biết bao vấn đề cần giải quyết. Câu hỏi đặt ra rằng chúng ta phải giải quyết như thế nào để có hiệu quả nhất. Một con người khôn ngoan sống lúc nào họ cũng muốn tiến dần đến sự hoàn thiện vì vậy họ luôn đầu tư, tìm tòi ra cái hay, cái mới. Ngày nay, nghiên cứu khoa học là một việc làm hết sức cần thiết đối với mỗi chúng ta và nó trở thành một hoạt động sôi nổi trên thế giới. Tham gia nghiên cứu khoa học được xem là cống hiến lớn của nhân loại cho khoa học và xã hội vì tất cả các cơ quan nhà nước luôn luôn đãi ngộ đối với những người đã cống hiến chất xám mình vào nghiên cứu khoa học. Để nghiên cứu 3 khoa học được thành con người phải có một tri thức nhất định và nhiều tâm quyến để cần nghiên cứu sáng tạo. Hiện nay, công nghệ thông tin là một ngành mũi nhọn, nó là chìa khóa để mở cửa cho tư duy và sáng tạo của con người. Qua bài thu hoạch này, em sẽ trình bày các suy nghĩ chủ quan của mình về các thủ thuật, nguyên tắc về phát minh sáng tạo trong nghiên cứu khoa học em cảm thấy ấn tượng nhất để có thể áp dụng vào trong đời sống hằng ngày và trong ngành môn tin học của mình và cách giải bài toán trên máy tính. Qua đây, em cũng xin được gửi lời cảm ơn sâu sắc đến GS.TSKH. Hoàng Văn Kiếm, người đã tận tâm truyền đạt những kiến thức nền tảng cơ bản cho chúng em về môn học “Phương pháp nhiên cứu khoa học trong tin học”. Bên cạnh đó cũng không thể không nhắc đến công lao trợ giúp không mệt mỏi của các chuyên gia cố vấn qua mạng thuộc Trung tâm phát triển CNTT – ĐH Quốc gia TP.HCM và toàn thể các bạn bè học viên trong lớp. 4 CHƯƠNG 1 VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT 1.1. Vấn đề khoa học 1.1.1. Khái niệm Vấn đề khoa học (scientific problem) cũng được gọi là vấn đề nghiên cứu (research problem) hoặc câu hỏi nghiên cứu là câu hỏi được đặt ra khi người nghiên cứu đứng trước mâu thuẫn giữa tính hạn chế của tri thức khoa học hiện có với yêu cầu phát triển tri thức đó ở trình độ cao hơn. 1.1.2. Phân loại Nghiên cứu khoa học luôn tồn tại hai vấn đề: - Vấn đề về bản chất sự vật đang tìm kiếm. - Vấn đề về phương pháp nghiên cứu để làm sáng tỏ về lý thuyết và thực tiễn nhưng vấn đề thuộc lớp thứ nhất. Cách giải quyết vấn đề khoa học như thế nào? Giải quyết vấn đề khoa học. Đây là mong muốn của những người muốn bước vào con đường khoa học. Như ta đã biết có rất nhiều ứng dụng vi mô từ phát minh sáng chế khoa học thành công trong cuộc sống. Một người muốn phát minh sáng tạo cần có 3 yếu tố cần thiết sau: - Kiến thức đủ để sáng tạo: Người phát minh sáng tạo cần có một kiến thức nhất định phù hợp với công trình nghiên cứu. Một người có kiến thức phổ thông đã biết sáng tạo khoa học nhưng mỗi người sáng tạo như thế nào? mức độ nào? là hoàn toàn khác nhau. - Môi trường đòi hỏi sáng tạo: Môi trường ảnh hưởng rất lớn đến đời sống của con người kể cả vấn đề sáng tạo của con người. Sống trong môi trường luôn đòi hỏi con người sáng tạo là môi trường luôn luôn đổi mới để hoàn thiện và phát triển. 5 - Khát vọng sáng tạo của con người: Có lẻ đây là vấn đề rất quan trọng để phát minh sáng tạo. Phát minh sáng tạo đòi hỏi con người phải có lòng ham mê, ốc sáng tạo và vượt khó, kiên trì bởi có rất nhiều nhà khoa học phát minh ra một cái mới họ phải thử đi thử lại rất nhiều có khi phải mất hàng chục năm. 1.1.3. Các tình huống vấn đề Có ba tình huống: Có vấn đề, không có vấn đề, giả vấn đề được cho trong hình dưới đây: Các phương pháp phát hiện vấn đề khoa học. Có 6 phương pháp: 1) Tìm những kẻ hở, phát hiện những vấn đề mới 2) Tìm những bất đồng 3) Nghĩ ngược lại quan niệm thông thường 4) Quan sát những vướng mắc trong thực tiễn 5) Lắng nghe lời kêu ca phàn nàn 6) Cảm hứng: những câu hỏi bất chợt xuất hiện khi quan sát sự kiện nào đó. Một tiếp cận không gian giải quyết vấn đề. Ý tưởng  Bài toán  Mô hình  Cách giải Bài toán P: Sau khi có ý tưởng, bài toán P được đặt ra nhằm giải quyết mục đích cuối cùng là gì? Trong cùng điểm nhìn, cùng một không gian, nếu ta P Bài toán P Điểm nhìn Không gian, vấn đề 6 thay đổi bài toán thì vấn đề cũng thay đổi nhưng chỉ thay đổi theo mục đích yêu cầu của bài toán. Ví dụ: Khi lập trình giải bài toán phương trình bậc 1 nếu cần chuyển sang giải phương trình bậc 2 thì bài toán lúc này có khác ta chỉ thay đổi mục đích yêu cầu từ bậc 1 sang bậc 2. Điểm nhìn: nơi có vị trí, tầm nhìn khách quan nhất, bao quát vấn đề để khi giải quỵết không còn sai sót hoặc sai sót ít có thể chấp nhận được. Nếu cùng một bài toán cùng một không gian nhưng điểm nhìn khác nhau thì vấn đề có thay đổi, nhưng cũng không thay đổi một cách tuyệt đối hoàn toàn. Cũng có những vấn đề được nhìn nhận tương tự nhau. Ví dụ: Do đâu rất nhiều tai nạn giao thông xảy ra ở nước ta. Cùng một vấn đề trên nếu ở hai điểm nhìn khác nhau sẽ trả lời khác nhau: - Nhìn từ phía xây dựng: Mặt đường chưa bằng phẳng, đường còn hẹp, còn nhiều công trình cầu đường cần nâng cấp. - Nhìn từ phía cảnh sát giao thông: Ý thức chấp hành luật giao thông của người tham gia giao thông còn kèm. Không gian vấn đề: Bài toán P đặt trong không gian vấn đề sao cho không quá phức tạp, nhưng cũng không thể đơn giản quá dẫn tới sai sót. Nếu cùng một bài toán, cùng một điểm nhìn, nhưng không gian khác nhau thì vấn đề sẽ có nhiều thay đổi hơn. Ví dụ: Cùng một phần mềm được ứng dụng ở một trường học lại khác ở một ngành nghề khác. Như vậy tính thay đổi của vấn đề từ thấp đến cao như sau: Bài toán (P)  Điểm nhìn  Không gian 7 1.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế 1.2.1. Vepol “Bất cứ hệ thống kỹ thuật nào ít nhất cũng phải có hai thành phần vật chất tác động tương hỗ và một loại trường hay năng lượng” Từ đó có một thuật ngữ về tam giác kỹ thuật gọi là tam giác Vepol. Vepol là mô hình hệ thống kỹ thuật. Vepol được quy ước đưa ra cốt chỉ để phản ánh một tính chất vật chất của hệ thống nhưng là chủ yếu nhất với bài toán đã cho. Ví dụ xét bài toán nâng cao tốc độ tàu phá băng thì băng đóng vai trò vật phẩm, tàu phá băng đóng vai trò cộng cụ và trường cơ lực đặt vào tàu để tác động tương hỗ với băng. Việc phân loại các chuẩn để giải quyết các bài toán sáng chế dựa vào phân tích Vepol. Mô hình Vepol gồm 3 yếu tố: một Trường T và trong T có hai vật chất V1, V2. V1 T V2 Tuy nhiên, một hệ thống ban đầu chưa hẳn đã có một chuẩn Vepol đủ 3 yếu tố trên, hoặc đã đủ thì có thể phát triển gì thêm trên Vepol đó. Có 5 phương pháp: - Dựng Vepol đầy đủ - Chuyển sang Fepol - Phá vỡ Vepol - Xích Vepol - Liên trường 8 1.2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế Có 40 nguyên lý: 1. Nguyên lý phân nhỏ 2. Nguyên lý “tách riêng” 3. Nguyên lý phẩm chất cục bộ 4. Nguyên lý phản đối xứng 5. Nguyên lý kết hợp 6. Nguyên lý vạn năng 7. Nguyên lý chứa trong 8. Nguyên lý phản trọng lượng 9. Nguyên lý gây ứng xuất sơ bộ 10. Nguyên lý thực hiện sơ bộ 11. Nguyên lý dự phòng 12. Nguyên lý đẳng thế 13. Nguyên lý đảo ngược 14. Nguyên lý cầu “tròn” hóa 15. Nguyên lý năng động 16. Nguyên lý tác động bộ phận và dư thừa 17. Nguyên lý bộ xung chiều khác 18. Nguyên lý tự dao động cơ học 19. Nguyên lý tác động theo chu kỳ 20. Nguyên lý tác động hữu hiệu 21. Nguyên lý vượt nhanh 22. Nguyên lý chuyển hại thành lợi 23. Nguyên lý quan hệ phản hồi 24. Nguyên lý sử dụng trung gian 25. Nguyên lý tự phục vụ 9 26. Nguyên lý sao chép 27. Nguyên lý rẽ thay cho đắt 28. Nguyên lý thay thế sơ đồ cơ học 29. Nguyên lý sử dụng các kết cấu thủy và khí 30. Nguyên lý sử dụng bao mềm dẻo và mềm mỏng 31. Nguyên lý sử dụng vật liệu nhiều lỗ 32. Nguyên lý đổi màu 33. Nguyên lý đồng nhất 34. Nguyên lý loại bỏ và tái sinh từng phần 35. Nguyên lý đổi các thông số hóa lý của đối tượng 36. Nguyên lý sử dụng chuyển pha 37. Nguyên lý sử dụng nở nhiệt 38. Nguyên lý sử dụng các chất oxy hóa 39. Nguyên lý sử dụng môi trường trơ 40. Nguyên lý sử dụng vật liệu tổng hợp Đưa một bài toán vào máy tính 1.2.3. Một số thủ thuật, nguyên tắc về phát minh, sáng tạo 1.2.3.1. Nguyên tắc phân nhỏ Nội dung: - Chia các đối tượng thành các phần độc lập. - Làm đối tượng thành các thành phần tháo ráp. P MT Algorithm Program 10 - Tăng mức độ phân nhỏ của đối tượng. Nhận xét: - Nguyên tắc phân nhỏ thường dùng các nguyên tắc “2_tách khỏi”, “3_phẩm chất cục bộ”, “5_kết hợp”, “6_vạn năng”… - Ứng dụng quen thuộc nhất chính là chia chương trình thành nhiều chức năng nhỏ, còn được gọi là “hàm” hay “thủ tục”. Ứng dụng nguyên tắc trên trong tin học: Trong lập trình nếu gặp những bài toán dài phức tạp người ta thường chia những chương trình nhỏ gọi là chương trình con. Chương trình con được dùng rộng rãi khi xây dựng các chương trình lớn nhằm làm cho chương trình dễ theo dõi, dễ sửa chữa, có thể phân mảnh chương trình cho nhiều người làm. Một đặc điểm nổi bật của chương trình con là nó có tính đệ quy nhờ thế mà nhiều bài toán được giải quyết dễ dàng. Ví dụ: Giải phương trình bậc hai: ax2+bx+c=0; với a,b,c được nhập vào từ bàn phím. Chúng ta sẽ sử dụng thủ tục để thực hiện công việc tính Delta và nghiệm nếu có. Trong thủ tục này chúng ta lưu ý: Các biến chúng ta sử dụng là biến toàn cục, nên công việc tính Delta và tính nghiệm sẽ được thực hiện trong chương trình con và kết quả sẽ được mang ra ngoài thủ tục để phục vụ cho công việc xét nghiệm. {Giai phuong trinh bac 2} Program GiaiPTB2; uses wincrt; var a,b,c,x1,x2,Delta:real; {Thu tuc tinh Delta va nghiem} Procedure PTB2; 11 var r:real; begin Delta := sqr(b)-4*a*c; if Delta >= 0 then Begin r := Sqrt(Delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); end; end; {Than chuong trinh chinh} Begin Writeln(‘Nhap 3 he so: a,b,c(Moi so cach nhau mot dau cach)’); readln(a,b,c); PTB2; if Delta < 0 then write(‘Phuong trinh vo nghiem’) else If Delta = 0 then Write(‘Phuong trinh co 1 nghiem: ‘, x1:10:2) else writeln(‘Phuong trinh co 2 nghiem: x1 = ‘, x1:10:2 ,’***** x2 = ‘, x2:10:2); readln; end. Trong môn Cấu trúc dữ liệu và giải thuật sắp xếp trộn (merge sort) Ý tưởng: Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp xếp dựa vào tư tưởng “chia để trị” (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. 12 Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư...) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một. Ví dụ: Ta có 12 13 45 32 100 34 65 10 Ta có ở trên là 8 phần tử cần được sắp xếp: Ý tưởng của merge sort là thay vì sắp xếp 8 phần tử (khó sắp) thì ta chia đôi dãy đó ra làm đôi (số phần tử nhỏ hơn --> sắp dễ hơn ) và sắp xếp các dãy con rồi ghép 2 dãy con lại (gọi là merge 2 dãy con). Vậy ta làm như sau: Chia đôi --> được hai dãy con mới là 12 13 45 32 và 100 34 65 10 sắp 2 dãy con lại: 12 13 45 32 gọi là dãy A 100 34 65 10 gọi là dãy B. + Muốn sắp A ta cũng làm giống như trên: Chia đôi A, được 2 dãy mới là A11={12 13} A12={45 32} Chia đôi B được 2 dãy mới là B11={100 34} B12={65 10} + Sắp xếp A11, B11, A12, B12. + Muốn sắp xếp A11 thì ta cũng chia đôi đến khi sắp được ta có 2 dãy con là A21={12} A22={13}. Sắp 2 dãy con trên được (đơn giản vì chỉ có một phần tử) là A21={12} A22={13}. Sắp xong thì ta merge lại thành A11={12 13}. + Tương tự sắp xếp cho B11 , A12 , B12 ta cũng có: B11={34 100} B12={10 65} A12={32 45} + Sắp xếp xong, ta sẽ merge lại A11, A12 thành A={12 13 32 45} B11, B12 thành B={10 34 65 100} Sắp xong A, B, ta sẽ merge chúng lại thành dãy ban đầu: {10 12 13 32 34 45 65 100} 13 1.2.3.2. Nguyên tắc “tách riêng” Nội dung: Tách thành phần gây phiền phức ra khỏi đối tượng hoặc ngược lại. Tách lấy phần cần thiết. Nhận xét: Nguyên tắc này ta thấy rất nhiều trong thực tế. Tách riêng ra để chúng ta dễ xử lý. a) Khi xử lý tín hiệu số có thể ta sẽ: - Tách bỏ các nhiễu, phục hồi tín hiệu ban đầu. - Sóng mang tín hiệu: tách sóng để lấy tín hiệu cần thiết. b) Thử vàng bằng nhiệt hoặc kim loại để: - Thử bằng nhiệt (phun lửa): chất không phải vàng sẽ nóng chảy và lộ ra trước tiên. - Dùng hóa chất để trích vàng trong hỗn hợp vàng-bạc. Dùng phép điện giải để mạ các đối tượng. Ứng dụng nguyên tắc trên trong tin học: Trong môn cơ sở dữ liệu ta tìm phủ tối thiểu của một phụ thuộc hàm: Ý tưởng: Từ một tập phụ thuộc hàm ban đầu ta loại bỏ các phụ thuộc hàm dư thừa để tìm phủ tối thiểu. Ví dụ: Cho lược đồ quan hệ Q(A,B,C,D) và tập pth F={ABCD, BC,CD}. Tìm phủ tối thiểu? 1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. + Ta có: F={ABC,ABD,BC,CD}. 2. Bỏ các thuộc tính dư thừa ở vế trái. + BC, CD không xét vì vế trái chỉ có một thuộc tính. + Xét ABC: Nếu bỏ A thì B+=BCD không chứa A nên không thể bỏ A. Nếu bỏ B thì A+=A. Không bỏ được thuộc tính nào. 14 + Xét ABD: Nếu bỏ A thì B+=BCD không chứa A nên không thể bỏ A. Nếu bỏ B thì A+=A. Không bỏ được thuộc tính nào. 3. Loại khỏi F các thuộc tính hàm dư thừa: + Xét ABC: tính AB+=ABCD=Q nên loại bỏ ABC. + Xét ABD: tính AB+=ABCD=Q nên loại bỏ ABD. + BC: tính B+=B không thể bỏ. + CD: tính C+=C không thể bỏ. Phủ tối thiểu là Ftt={BC,CD}. 1.2.3.3. Nguyên tắc phẩm chất cục bộ Nội dung: - Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. - Các phần khác nhau của đối tượng phải có những chức năng khác nhau. - Mỗi phần của đối tượng phải ở trong những điều kiện thích hợp nhất đối với công việc. Nhận xét: - Các đối tượng đầu tiên thường có tính đồng nhất cao về vật liệu, cấu hình, chức năng, thời gian, không gian,… đối với các thành phần trong đối tượng. Khuynh hướng phát triển tiếp theo là: các phần có các phẩm chất, chức năng,… riêng của mình nhằm phục vụ tốt nhất chức năng chính hoặc mở rộng chức năng chính đó. - Nói chung nguyên tắc phẩm chất cục bộ phản ảnh khuynh hướng phát triển: từ đơn giản sang phức tạp, từ đơn điệu sang đa dạng. - Tinh thần “Phẩm chất cục bộ” có ý nghĩa lớn đối với nhận thức và xử lý thông tin: Không phải tin tức hay thông tin nào cũng có giá trị như nhau. 15 Không thể có một cách tiếp cận dùng chung cho mỗi loại đối tượng – “Chân lý là cụ thể”. Ứng dụng trong Tin học: - Trong lập trình, trong một đoạn chương trình cần phân biệt phẩm chất cục bộ: ở đâu là phần lỗi của chương trình, phần khác là những thao tác phụ. Ví dụ: In tất cả các số chia hết cho 9 trong phạm vi [1..10000], với hình thức in ra: Mỗi hàng có 10 số, mỗi trang có 20 hàng, tạm dừng chờ nhấn phím liên tiếp trang sau (nếu hơn trang). Như vậy nếu chương trình có lỗi thì lỗi của chương trình (phẩm chất cục bộ) là phần kiểm tra một số chia hết cho 9, chứ không phải là phần in ra. - Trong lập trình hướng đối tượng, chúng ta có các phương thức, mà mỗi phương thức có những tính năng khác nhau. 1.2.3.4. Nguyên tắc phản đối xứng Nội dung: Chuyển đối tượng có hình dạng đối xứng thành không đối xứng (nói chung, làm giảm bậc đối xứng). Nhận xét: - Giảm bậc đối xứng, ví dụ chuyển từ hình tròn sang hình Oval, hình vuông sang hình chữ nhật,... - Thủ thuật này rất có tác dụng trong việc khắc phục tính ì tâm lý, cho rằng các đối tượng phải có tính đối xứng. - Khi đối tượng chuyển sang dạng ít đối xứng hơn, có thể làm xuất hiện những tính chất mới lớn hơn. Ví dụ tận dụng hơn về nguồn tài nguyên, không gian,… - Nguyên tắc đối xứng, có thể nói là trường hợp riêng của 3 nguyên tắc phẩm chất cục bộ. Ứng dụng trong tin học: 16 Ví dụ: Kiểu biến số nguyên (byte, word, unsigned int) chỉ bao gồm các số nguyên dương, không có tính đối xứng (có cả âm lẫn dương, như dùng kiểu integer hay longint), nhưng trong thực tế rất nhiều lúc ta chỉ làm việc trên những số dương, rõ ràng khai báo kiểu này ta đã tiết kiệm được bộ nhớ và làm cho chương trình trong sáng và linh động hơn. 1.2.3.5. Nguyên tắc kết hợp Nội dung: - Kết hợp các đối tượng đồng nhất hoặc các đối tượng dành cho các đối tượng kế cận. - Kết hợp về mặt thời gian các hoạt động đồng nhất hoặc kế cận. Nhận xét: - “Kế cận“ở đây không nên chỉ hiểu là gần nhau về mặt vị trí hay chức năng, mà nên hiểu là có quan hệ với nhau, bổ sung cho nhau,… Do vậy có thể kết hợp các đối tượng “ngược nhau” (ví dụ: bút chì kết hợp với tẩy). - Đối tượng mới được tạo nên do sự kết hợp, thường có những tính chất, khả năng mà đối tượng riêng rẽ chưa từng có. Điều này có nguyên nhân sâu xa là lượng đổi thì chất cũng đổi và do tạo được sự thống nhất của các mặt đối lập. - Nguyên tắc kết hợp thường hay sử dụng với 1.Nguyên tắc phân nhỏ, 3.Nguyên tắc phẩm chất cục bộ… Minh họa ứng dụng nguyên tắc trên trong tin học: - Trong lập trình cổ điển (lập trình theo dạng cấu trúc), khi đó dữ liệu và chức năng là những thành phần riêng biệt. Khi chuyển sang lập trình hướng đối tượng thì dữ liệu và chức năng (phương thức, sự kiện) gộp chung trong một đối tượng, đây chính là khái niệm Class. - Các ngôn ngữ cấp cao thường cho phép kết hợp với mã nguồn Assembly. 17 - Hệ điều hành: Kết hợp thời gian rãnh của CPU, tận dụng thời gian để cho ra hệ điều hành đa nhiệm. - Máy vi tính cho phép chạy nhiều hệ điều hành trên cùng một máy (Multi boot, Máy ảo “Pc Virtual,VMware”). 1.2.3.6. Nguyên tắc vạn năng Nội dung: Đối tượng thực hiện một số chức năng khác nhau, do đó là không cần sự tham gia của đối tượng khác. Nhận xét: - Ngày nay con người cần hướng tới sự hoàn thiện, vì vậy họ luôn sáng tạo ra những công cụ càng tinh tế hơn. Trong thị trường cạnh tranh các nhà sản xuất luôn phát minh ra những sản phẩm đa chức năng để chạy theo thị hiếu của người tiêu dùng. - Hiện nay trên thị trường có loại máy đa năng có thể vừa xây sinh tố vừa ép được trái cây…. Ứng dụng nguyên tắc trên trong tin học: - Một phần mềm quản lý trong một Trường Đại học được đánh giá là tốt, nhất định phần mềm phải đáp ứng chức năng của người sử dụng như: + Quản lý hồ sơ sinh viên + Quản lý điểm sinh viên + Quản lý lịch dạy của giảng viên + Quản lý thu học phí Đến một thời điểm nào đó người sử dụng cần thêm chức năng gì thì yêu cầu phần mềm nâng cấp để đáp ứng nhu cầu của người tiêu dùng. Thời xưa một sinh viên muốn học anh văn và muốn đánh máy phải sử dụng cả hai thiết bị là máy đánh chữ, và máy nghe nhạc. Ngày nay, một sinh 18 viên sử dụng máy vi tính có thể làm nhiều công việc như: đánh máy, học anh văn, lập trình, chơi game giải trí,… - Trong lập trình chúng ta cảm thấy loại ngôn ngữ nào hỗ trợ nhiều thì chắc chắn rằng loại ngôn ngữ đó nhiều người dùng. Trong tin học con người lúc nào cũng áp dụng nguyên tắc này vì công nghệ phát triển theo từng ngày, nguyên tắc vạn năng là nguyên tắc con người càng hướng tới. 1.2.3.7. Nguyên lý rẻ thay cho đắt Nhận xét: Có nhiều nguyên nhân để ta phải thay thế đối tượng đắt tiền bởi đối tượng rẻ tiền. Bác Hồ có dạy rằng “Cần, kiệm, liêm, chính” là đức tính của mỗi con người chúng ta. Vì vậy mỗi người chúng ta cần tiết kiệm cả thời gian, tiền bạc,… Trong cuộc sống người ta cố gắng nghĩ ra những loại máy có công suất sản xuất cao như vậy trong một khoảng thời gian ngắn mà ta sản xuất ra nhiều sản phẩm. Ứng dụng nguyên tắc trong tin học: Về tiền bạc: - Hiện nay trên Internet có nhiều phần mềm mã nguồn mở hoặc Shareware hay phần mềm không mất tiền (freeware) chúng ta có thể download về chỉnh sửa vài chỗ là có thể sử dụng được, có một số chương trình diệt vi rút khỏi phải mất tiền mua mà vẫn sử dụng tốt. Mặc dù nó không mang tính vạn năng, còn nhiều hạn chế nhưng đáp ứng được nhu cầu không mất tiền nhưng cũng đáp ứng được công việc. - Tùy theo độ phức tạp của công việc mà ta bỏ tiền ra một cách chính đáng là mua hoặc không mua. Ví dụ: Chính sách tiết kiệm của một trường Đại học như sau: 19 Trong một trường Đại học có khoảng 500 máy vi tính nếu chúng ta bỏ một số tiền ra mua mỗi máy một chương trình diệt vi rút bản quyền thì ta phải tốn một số tiền không ít. Vì vậy Trường có giải pháp như sau: download phần mềm diệt vi rút miễn phí trên mạng cài đặt cho tất cả các máy và cài thêm phần mềm đóng băng. Các máy của trường vẫn đáp ứng tương đối giảng dạy thực hành của giảng viên. Về thời gian: - Để đánh giá một chương trình tốt hay không người ta còn dựa vào tốc độ của chạy. Vì vậy ngày nay người lập trình thường tối ưu hóa chương trình về thời gian và không gian. Mô hình tối ưu hóa chương trình Ví dụ: Ta có bài toán Cho đoạn chương trình cần xoay 1000 điểm của một đa giác một góc a. For i:=1 to 1000 do Begin x’i:=xicos(a) + yisin(a) y’i:=xisin(a) + yicos(a) 20 End Ta dễ dàng nhận thấy rằng đoạn chương trình trên thực hiện tính sin(a) 2000 lần và tính cos(a) 2000 lần. Một chi phí quá cao. Chúng ta có thể giảm đáng kể chi phí này bằng cách dùng hai biến phụ sina=sin(a) và cosa=cos(a). Khi đó rõ ràng là một lần tính sin và 1 lần tính cos. Đoạn chương trình được viết lại như sau: sina:=sin(a); cosa:=cos(a); For i:=1 to 1000 do Begin x’i:=xicosa + yisina y’i:=xisina + yicosa End. Từ bài toán trên ta nhận thấy rằng cùng cho ra kết quả giống nhau nhưng cách lập trình khác nhau. Người lập trình luôn tìm giải pháp nào được xem là tối ưu nhất. 21 CHƯƠNG 2: CÁC PHƯƠNG PHÁP NGHIÊN CỨU, GIẢI QUYẾT VẤN ĐỀ BÀI TOÁN TRONG TIN HỌC 2.1. Mục đích nghiên cứu giải quyết bài toán trong tin học Ta thấy rằng trong thực tế có nhiều vấn đề rất đơn giản nhưng khi thực hiện đòi hỏi một quá trình tính toán lặp đi lặp lại rất nhiều lần. Chính điều đó đã khiến cho người giải toán mau nhàn chán, mất tập trung và gây ra sai sót. Từ đó con người đã phát minh ra máy tính để thay thế con người. Dần dấn con người phát minh và khám phá nâng cấp máy tính. Vì vậy ngày nay máy tính rất hữu dụng trong đời sống chúng ta. So với con người, máy tính có một khả năng tuyệt vời là có thể tính toán khối lượng khổng lồ các phép tính với độ chính xác tuyệt đối, tốc độ cực nhanh và quan trọng là nó không hề biết mệt. Vấn đề đặt ra ở đây là, quá trình giải toán của máy tính như thế nào? Máy tính không hiểu được ngôn ngữ của con người. Nó chỉ hiểu những nhu cầu theo số nhị phân (binary) những con số chỉ gồm hai chữ số là số 0, 1 hay còn gọi là ngôn ngữ máy. Sau này có nhiều ngôn ngữ máy ra đời, con người viết yêu cầu và ra lệnh máy tính thực thi các yêu cầu của mình. 2.2. Các phương pháp thường dùng để giải quyết vấn đề bài toán trên máy tính 2.2.1. Phương pháp trực tiếp Đặc điểm cách giải quyết vấn đề này là: - Xác định trực tiếp được lời giải qua một thủ tục tính toán (công thức, hệ thức, định luật,…) hoặc qua các bước căn bản để có được lời giải. - Việc giải quyết vấn đề trên máy tính chỉ là thao tác lập trình hay là sự chuyển đổi lời giải từ ngôn ngữ bên ngoài sang các ngôn ngữ được sử dụng trong máy tính. 22 - Đi sâu tìm hiểu các phương pháp trực tiếp chính là đi sâu tìm hiểu các ngôn ngữ lập trình trong máy tính. Về cơ bản phương pháp lập trình có 3 loại: Loại 1: Được dùng để biểu diễn cho các bài toán có lời giải chính bằng một công thức toán học nào đó. Ví dụ cách giải bài toán phương trình bậc hai trên máy tính. Ngoài việc biết cách dùng ngôn ngữ lập trình ta phải có kiến thức giải phương trình bậc hai như thế nào? Biểu diễn lại cách tính giá trị của delta, nghiệm kép, nghiệm phân biệt,… Loại 2: Biểu diễn các công thức toán học có lời giải gần đúng (như các công thức gần đúng sin, cos, e, giải các phương trình siêu việt,…). Loại 3: Biểu diễn các lời giải tường minh bằng kỹ thuật đệ qui nghĩa là phân chia các bài toán ban đầu thành những bài toán nhỏ hơn. Ví dụ: Tính giai thừa của số n, tính trị thứ n của dãy Fibonacci. Các nguyên lý áp dụng trong phương pháp trực tiếp: - Nguyên lý 1: Chuyển đổi dữ liệu bài toán thành dữ liệu của chương trình, có nghĩa là “Dữ liệu của bài toán sẽ được biểu diễn lại dưới dạng các biến của chương trình thông qua các quy tắc xác định của ngôn ngữ lập trình cụ thể”. + Biến biểu diễn dữ liệu của chương trình. + Thay đổi giá trị của biến lệnh gán + Kiểu dữ liệu + Hằng số + Cấu trúc của một trương trình - Nguyên lý 2: Chuyển đổi quá trình tính toán của bài toán thành các cấu trúc của chương trình, có nghĩa là “Mọi quá trình tính toán đều có thể mô 23 tả và thực hiện dựa trên ba cấu trúc cơ bản: Cấu trúc tuần tự, cấu trúc rẽ nhánh và cấu trúc lặp”. + Cấu trúc tuần tự + Cấu trúc rẽ nhánh if(condition) Rẽ nhánh đơn if( ) Rẽ nhánh đôi if()…then… Rẽ nhiều nhánh: case Rẽ nhánh không có điều kiện LEBOL và GOTO + Cấu trúc lặp Lặp tuần tự Lặp không tuần tự. - Nguyên lý 3: Biểu diễn các tính toán chính xác, có nghĩa là “Chương trình tính toán theo các biểu thức chính xác không đồng nhất với quá trình tính toán chính xác về mặt hình thức”. - Nguyên lý 4: Biểu diễn các tính toán gần đúng bằng cấu trúc lặp, có nghĩa là “Mọi quá trình tính toán gần đúng đều dựa trên các cấu trúc lặp với tham số xác định”. - Nguyên lý 5: Phân chia bài toán ban đầu thành những bài toán nhỏ hơn, có nghĩa là “Mọi vấn đề - bài toán đều có thể giải quyết bằng cách phân chia thành những vấn đề - bài toán nhỏ hơn”. + Thủ tục hàm và hàm-phương pháp phân chia chương trình thành những chương trình con. + Biến cục bộ và biến toàn cục + Tham số dữ liệu đầu vào, đầu ra của hàm - Nguyên lý 6: Biểu diễn các tính toán không tường minh bằng đệ quy, có nghĩa là “Quá trình đệ quy trong máy tính không đơn giản như các biểu thức quy nạp trong toán học”. 24 2.2.2. Phương pháp gián tiếp hoặc tìm kiếm lời giải Phương pháp này được sử dụng khi chưa tìm ra lời giải chính xác của vần đề. - Đây cũng chính là cách tiếp cận chủ yếu của loài người từ xưa đến nay. - Đưa ra những giải pháp mang đặc trưng của máy tính, dựa vào sức mạnh tính toán của máy tính. Ví dụ: Muốn giải một phương trình bậc 7 ta phải làm sao? Ta chỉ có công thức giải phương trình bậc 1, bậc 2. 2.2.2.1. Phương pháp thử-sai Phương pháp này mới nghe có vẻ tầm thường nhưng vai trò của nó giải quyết vấn đề hoàn toàn không tầm thường. Thomas Eđison - nhà khoa học từ Mỹ nổi tiếng, cha đẻ của bóng đèn điện, đã hóm hỉnh phát biểu tìm cây kim trong một đóng rơm: “Trong khi chưa nghĩ ra cách hay thì cứ việc rút từng cọng rơm cho đến khi tìm được cây kim”. Phương pháp này dựa trên 3 nguyên lý: a. Nguyên lý duyệt toàn bộ hoặc quét cạn toàn bộ: Liệt kê tất cả các trường hợp xảy ra và xem xét chúng. Ví dụ: Liệt kê tất cả các số nguyên tố m đến n. b. Nguyên lý ngẫu nhiên: Dựa vào việc thử một số khả năng được chọn một cách ngẫu nhiên trong tập khả năng (thường rất lớn nếu áp dụng nguyên lý đồng bộ thường mất nhiều thời gian) khả năng tìm lời giải đúng hoặc gần đúng sẽ phụ thuộc vào chiến lược chọn ngẫu nhiên và một số điều kiện cụ thể. Ví dụ: Kiểm tra chất lượng trong quá trình sản xuất của một đoàn kiểm tra. Một lô hàng có 24 sàn. c. Nguyên lý mê cung Nguyên lý này được áp dụng khi chúng ta không biết chính xác “hình dạng” của lời giải mà phải xây dựng dần lời giải qua từng bước một giống 25 như tìm đường ra khỏi một mê cung. Rõ ràng, khi ở trong một mê cung, ta không thể biết trước được đâu là ngõ ra. Chính vì vậy, khi gặp một ngã rẽ, ta chỉ có cách “chọn đại” một con đường đi theo hướng đó, Nếu đi vào ngõ cụt, ta phải biết đánh dấu và loại bỏ con đường đã đi rồi sau đó quay trở lại ngã rẻ và chọn hướng đi khác. Các phương pháp giải dựa trên nguyên lý nguyên lý mê cung sẽ biến đổi bài toán ban đầu về một bài toán tương tự bài toán tìm đường đi trong mê cung. 2.2.3. Các phương pháp Heuristic Có nhiều bài toán mà việc giải quyết bằng phương pháp thử-sai sẽ dẫn đến một số lớn, thời gian có được kết quả cuối cùng là không chấp nhận được. Lúc này người ta sẽ xây dựng lời giải dựa theo các phương pháp gọi là thuật giải Heuristic. Thuật giải Heuristic có đặc điểm là đơn giản và gần gũi với cách suy nghĩ của con người, cho ra được những lời giải đúng trong đa số các trường hợp áp dụng. Các thuật giải Heuristic được xây dựng trên một số nguyên lý rất đơn giản như vét cạn thông minh, nguyên lý tối ưu cục bộ, nguyên lý hướng đích, nguyên lý sắp thứ tự,... Đó là giải thuật rất thú vị và có nhiều ứng dụng trong thực tiễn. 2.2.4. Các phương pháp trí tuệ nhân tạo Phương pháp thử-sai hoặc Heuristic, nói chung đều dựa trên một điểm cơ bản và dựa trên trí thông minh của chính con người để giải bài toán, máy tính chỉ đóng vai trò thực thi mà thôi. Còn các phương pháp trí tuệ nhân tạo dựa trên trí thông minh của máy tính. Trong những phương pháp này, người ta sẽ đưa vào máy tính thông minh nhân tạo giúp máy tính bắt chước một phần khả năng suy luận như con người. Từ đó, khi gặp một vấn đề, máy tính sẽ dựa trên những điều đó đã được “học” để tự đưa ra phương án giải quyết vấn đề. 26 CHƯƠNG 3 LÝ THIẾT TRÒ CHƠI 8 SỐ 3.1. Tìm hiểu trò chơi 8 số 3.1.1. Mục đích giải quyết bài toán 8 số trên máy tính Như ta đã biết bài toán 8 số là bài toán phổ biến được nhiều người biết đến, đặc biệt là những người thuộc ngành tin học. Bài toán tuy đơn giản nhưng đỏi hỏi người giải phải tư duy. Nếu chúng ta di chuyển từng bước bằng tay cho từng con số từ trạng thái bắt đầu đến trạng thái về đích đòi hỏi con người phải tốn một khoảng thời gian, còn nhanh hay chậm còn tùy thuộc vào trí tuệ và độ nhanh nhẹn của mỗi người. Dựa vào thuật giải A* và giải thuật Dijsktra để cài đặt vào máy tính. Lúc này máy tính thay thế con người giải quyết vấn đề là nhập vào trạng thái ban đầu và cho ra trạng thái đích giải bài toán một cách nhanh chóng. Ví dụ trò chơi: Chúng ta có bảng 3x3 ô và tám quân mang số hiệu từ 1 đến 8 được xếp vào tám ô, còn lại một ô trống, chẳng hạn như trong hình 3.1 bên trái. Trong trò chơi này, bạn có thể chuyển dịch các quân ở cạnh ô trống tới ô trống đó. Vấn đề của bạn là tìm ra một dãy các chuyển dịch để biến đổi cảnh huống ban đầu (hình 3.1 bên trái) thành một cảnh huống xác định nào đó, chẳng hạn cảnh huống trong hình 3.1 bên phải. Hình 3.1 Trạng thái ban đầu và trạng thái kết thúc của bài toán số Trong bài toán này, trạng thái ban đầu là ở bên trái hình 3.1, còn trạng thái kết thúc ở bên phải hình 3.1. 27 Tương ứng với các quy tắc chuyển dịch các quân, ta có bốn toán tử: up (đẩy quân lên trên), down (đẩy quân xuống dưới), left (đẩy quân sang trái), right (đẩy quân sang phải). Rõ ràng là, các toán tử này chỉ là các toán tử bộ phận; chẳng hạn, từ trạng thái ban đầu (hình 3.1 bên trái), ta chỉ có thể áp dụng các toán tử down, left, right. Cụ thể ta có thể cài đặt mỗi bảng 3x3 bằng một ma trận aij vuông cấp 3, trong đó aij  {0, 1, 2, 3, 4, 5, 6, 7, 8} và aij ≠ akl khi i ≠ k hoặc j ≠ l. Toán tử chuyển trạng thái xác định như sau  0 0i ja 0 :          0 0 ij 0 0 0 0 up ij i 1j 0 0 0 0 0 0 a nên j j i i i i 1 i 1 f a a nên i i j j i 1 0nêni i j j i 1                                 0 0 ij 0 0 0 0 down ij i 1j 0 0 0 0 0 0 a nên j j i i i i 1 i 3 f a a nên i i j j i 3 0nên i i j j i 3                                 0 0 ij 0 0 0 0 left ij i j 1 0 0 0 0 0 0 a nên i i j j j j 1 j 1 f a a nên i i j j j 1 0nêni i j j j 1                                 0 0 ij 0 0 0 0 right ij i j 1 0 0 0 0 0 0 a nên i i j j j j 1 j 3 f a a nên i i j j j 3 0nên i i j j j 3                        Trong các ví dụ trên việc tìm ra một biểu diễn thích hợp để mô tả các trạng thái của vấn đề là khá dễ dàng và tự nhiên. Song trong nhiều vấn đề việc tìm hiểu được biểu diễn thích hợp cho các trạng thái của vấn đề là hoàn toàn không đơn giản. Việc tìm ra dạng biểu diễn tốt cho các trạng thái đóng vai trò hết sức quan trọng trong quá trình giải quyết một vấn đề. Có thể nói rằng, nếu 28 ta tìm được dạng biểu diễn tốt cho các trạng thái của vấn đề, thì vấn đề hầu như đã được giải quyết. 3.1.2. Mô tả Một bảng 3x3 với các ô trong đó có số từ 18 và 1 ô trống, các ô được đặt ở các vị trí ngẫu nhiên, ô trống và ô số có thể đổi chỗ cho nhau, tìm cách di chuyển các ô sao cho các con số về đúng thứ tự, bài toán đặt ra ở đây là tìm phương án tối ưu sao cho số lần di chuyển là ít nhất. Trạng thái ban đầu Trạng thái đích Trạng thái đích có thể có 2 trường hợp có thể xảy ra: và Với mỗi trạng thái ban đầu, chỉ tìm được 1 trạng thái đích có thể đạt tới. Điều đầu tiên cần phải quan tâm để giải bài toán này là xác định trạng thái đích. Trạng thái đích được xác định dựa trên trạng thái ban đầu. 29 3.1.3. Xác định trạng thái đích Đầu tiên hãy thử tính có bao nhiêu số bé hơn 8 ở sau ô chứa giá trị 8. Kết quả nhận được là 6 (những ô màu vàng) Làm tương tự như vậy với ô có giá trị 6. Dễ thấy trong 3 ô (4,7,5) có 2 giá trị nhỏ 6 là 4,5. Làm như trên từ ô đầu tiên (2) tới ô cuối cùng (5) và cộng dồn các giá trị nhận được: N = 1+6+1+0+2+0+1+0=11 Nếu N là số lẻ thì chúng ta chỉ có thể có đáp án là trạng thái A, ngược lại là trạng thái B. 30 Trạng thái A Trạng thái B Chúng ta đã xác định được trạng thái đích cần đạt được, bây giờ chúng ta bắt đầu tìm kiếm giải thuật để tìm ra đích. Trên thực tế có nhiều giải thuật để tìm ra đích, ở đây tôi chỉ áp dụng thuật toán A*. 3.2. Thuật toán tìm đáp án 3.2.1. Giới thiệu về A* A* là một thuật toán Heuristic dựa trên thuật toán Dijsktra. Thế nên phải tìm hiểu kỹ thuật toán Dijsktra trước khi tìm hiểu thuật toán này. Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất trong một đồ thị có hướng không có cạnh mang trọng số âm. a. Bài toán Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị. Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi. Trọng số không âm của 31 các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ: với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C. b. Chứng minh Ý tưởng của chứng minh như sau: Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v. Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v. Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy. Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các cạnh không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ đường đi, và do đó có giá trị bé hơn d[v]. Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh. Trong khoa học máy tính, A* là một lựa chọn tốt nhất đồ thị tìm kiếm thuật toán mà tìm thấy đường dẫn chi phí ít nhất định ban đầu từ một nút tới một nút mục tiêu (trong một hoặc nhiều mục tiêu có thể). Nó sử dụng một khoảng cách, cộng với chi phí năng Heuristic (thường được ký hiệu là f (x)) để xác định thứ tự tìm kiếm thăm nút trong cây. Khoảng cách + giá Heuristic là một tổng của hai chức năng: - Đường dẫn - chi phí hoạt động, đó là chi phí từ nút bắt đầu đến nút hiện tại (thường được ký hiệu là g (x)). 32 - Và một “Admissible Heuristic ước lượng” khoảng cách đến mục tiêu (thường được ký hiệu là h (x)). H(x) là một phần của f (chức năng) x phải là một Admissible Heuristic; có nghĩa là, nó không được đánh giá cao khoảng cách đến mục tiêu. Vì thế cho một ứng dụng như định tuyến, h(x) có thể đại diện cho khoảng cách đường thẳng đến mục tiêu, vì đó là khoảng cách nhỏ nhất có thể giữa hai điểm. Nếu h đáp ứng các điều kiện bổ sung      h x d x, y h y  cho cạnh mỗi x, y của đồ thị (d nghĩa là chiều dài của cạnh đó) sau đó được gọi là h không thay đổi hay nhất quán. Trong trường hợp này A* có thể được thực hiện hiệu quả hơn - khoảng nói, nút không cần phải được xử lý nhiều hơn một lần (xem đóng đặt dưới đây) - và trong thực tế, A* tương đương với chạy thuật toán Dijkstra's với chi phí giảm: d'(x, y): = d(x,y) - h(x) + h(y) Thuật toán này được mô tả lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson, và Bertram Raphael Thuật toán này đã được khái quát hóa thành một thuật toán tìm kiếm Heuristic hai chiều. A* là sự lựa chọn phổ biến nhất, bởi vì nó khá linh hoạt và có thể được sử dụng trong nhiều hoàn cảnh. A* là đồ thị như các thuật toán tìm kiếm khác nhưng khác ở chỗ nó có khả năng có thể tìm kiếm một khu vực rộng lớn của bản đồ. Nó giống như thuật toán Dijkstra trong đó nó có thể được sử dụng để tìm một con đường ngắn nhất. Nó giống như tham lam nhất ở chỗ nó có thể sử dụng một Heuristic để hướng dẫn chính nó. 3.2.2. Chi tiết thuật toán A* Giả sử rằng có một người muốn đi từ điểm A tới điểm B. Giả định rằng một bức tường ngăn cách hai điểm. Điều này được minh họa bằng hình dưới 33 đây, với màu xanh lá cây là một điểm khởi đầu A, và màu đỏ là kết thúc điểm B và hình chữ nhật màu xanh là bức tường ở giữa (hình 3.2). Hình 3.2 Ở đây chúng tôi đã phân chia khu vực tìm kiếm thành 1 lưới ô vuông như hình vẽ để đơn giản hóa khu vực tìm kiếm, đây là bước đầu tiên. Phương pháp này đặc biệt làm giảm diện tích để tìm kiếm một mảng hai chiều đơn giản. Mỗi mục trong mảng đó đại diện cho một trong các hình vuông trên khu vực tìm kiếm, và tình trạng của nó được ghi lại như di chuyển hoặc đứng yên. Đường đi được tìm thấy khi xuất hiện các ô vuông liên tiếp đi từ A đến B. Các ô vuông trên đường đi gọi là các “nút”. Các nút có thể được đặt ở bất cứ đâu trên khu vực tìm kiếm. a. Bắt đầu tìm kiếm Khi chúng ta đã đơn giản hóa khu vực tìm kiếm và quản lý được các “nút”, bước tiếp theo cần làm là tìm kiếm đường đi ngắn nhất từ A đến B, bắt đầu từ A, kiểm tra các hình vuông liền kề và tìm kiếm cho đến khi tìm thấy B. Bắt đầu tìm kiếm như sau: 34 - Bắt đầu từ A, sau đó thêm vào một danh sách mở các hình vuông liền kề A. Về cơ bản đây là danh sách các ô vuông cần kiểm tra để tìm ra đường đi đến B. - Tất cả các hình vuông có thể truy cập hoặc di chuyển giáp với A, hình 3.1 hoặc các điểm không thuận lợi, thêm chúng vào danh sách mở. A là mốc quan trọng để theo dõi đường đi đến B. - Chọn 1 điểm vuông trong danh sách mở làm điểm bắt đầu tiếp theo và đưa vào “danh sách đóng” khi F là nhỏ nhất. Hình dưới đây minh họa cho công việc trên. Hình 3.3 Chìa khóa xác định hình vuông để tìm ra con đường ngắn nhất là phương trình sau đây: F G H  Trong đó: + G là chi phí di chuyển để di chuyển từ A đến điểm khởi đầu cho một hình vuông trên khu vực tìm kiếm. + H là chi phí ước tính để di chuyển, từ đó đưa ra điểm vuông trên khu vực tìm kiếm đến đích cuối cùng. Chúng ta thực sự không biết khoảng cách thực tế cho đến khi tìm thấy con đường đi đến B. Con đường được tìm thấy khi đi qua nhiều danh sách mở và hình vuông được chọn khi F là nhỏ nhất. 35 Trong ví dụ này, ta quy ước G=10 với di chuyển ngang, dọc và G=14 với di chuyển chéo (ta sử dụng 10 và 14 bởi vì khoảng cách thực tế để di chuyển theo đường chéo là căn bậc hai của 2, hay khoảng 1,414 lần chi phí di chuyển theo chiều ngang hoặc theo chiều dọc). H có thể được tính bằng nhiều cách. Ở đây chúng tôi chọn phương pháp Manhattan. Với phương pháp này có thể tính được tổng số hình vuông di chuyển theo chiều ngang, dọc để đến đích mà không tính đến các chướng ngại vật, sau đó nhân tổng đó với 10. Hình 3.4 Tiếp tục tìm kiếm Để tiếp tục tìm kiếm chúng ta chọn ra hình vuông có F nhỏ nhất trong danh sách mở. So với hình vuông đã chọn, ta làm như sau: - Đưa hình vuông được chọn từ danh sách mở vào danh sách đóng. - Kiểm tra tất cả các ô vuông kề bỏ qua những hình vuông có trong danh sách đóng hoặc không di chuyển (bức tường hình 3.2). Thêm hình vuông vào danh sách mở nếu như nó chưa có trong danh sách mở. - Nếu một hình vuông liền kề đã được vào danh sách mở, kiểm tra G cho hình vuông đó là thấp hơn. Nếu không, không làm bất cứ điều gì. Mặt khác, 36 nếu chi phí G của các đường dẫn mới là thấp hơn, thay đổi các vuông kề bên vuông lựa chọn. Cuối cùng, tính toán lại cả F và G điểm của hình vuông đó. Các bước trên được minh họa bằng hình vẽ dưới đây: Hình 3.5 Hình 3.6 37 Hình 3.7 Cuối cùng ta tìm ra được đường đi từ A→B theo thuật toán A* như hình 3.8. Hình 3.8 b. Tóm lược thuật toán A* Từ giải thích chi tiết bằng ví dụ trên ta tóm lược lại được phương pháp A* như sau: - Thêm hình vuông bắt đầu (hoặc nút) vào danh sách mở. 38 - Lặp lại như sau: + Chọn hình vuông F chi phí thấp nhất trong danh sách mở. + Chuyển nó vào danh sách đóng. - Đối với mỗi ô vuông 8 cạnh vuông này. - Nếu nó không di chuyển hoặc nếu nó nằm trong danh sách đóng cửa, bỏ qua nó. Nếu không làm như sau: + Nếu nó không có trong danh sách mở, thêm nó vào danh sách mở… Làm cho hiện tại khu vực tìm kiếm chính của hình vuông này bản ghi F, G, H và chi phí của nó. + Nếu đó là trong danh sách đã được mở, kiểm tra xem đường dẫn này để mà vuông là tốt hơn, bằng cách sử dụng G chi phí như là thước đo... Một G thấp hơn chi phí có nghĩa rằng đây là một con đường tốt hơn. Nếu vậy, thay đổi các vuông chính của khu vực tìm kiếm vào vuông hiện tại và tính toán lại các G và điểm F của khu vực tìm kiếm. - Dừng khi: + Thêm các mục tiêu vuông vào danh sách đóng cửa, trong đó đường dẫn trường hợp đã được tìm thấy. + Không tìm thấy những vuông mục tiêu và danh sách mở trống. Trong trường hợp này, không có đường dẫn. 3.3. Cài đặt giải thuật 3.3.1. Cài đặt giải thuật Lập trình C# trên visual studio 2010. 3.3.2. Hướng dẩn sử dụng Ứng dụng viết trên windows form nên tương đối dể sử dụng. 39 TÀI LIỆU THAM KHẢO 1. Mai Tiến Dũng, Bài giảng kỹ thuật lập trình. 2. Phan Dũng (1992), Làm thế nào để sáng tạo, Ủy ban khoa học và kỹ thuật Tp.Hồ Chí Minh. 3. Phan Dũng (1994), Sổ tay sáng tao: các thủ thuật (nguyên tắc cơ bản), Sở khoa học – công nghệ và môi trường. 4. Phan Dũng (1997), Phương pháp luận sáng tạo khoa học kỹ thuật (giáo trình sơ cấp), Sở khoa học – công nghệ và môi trường. 5. Nguyễn Hữu Duyệt, Bài giảng môn trí tuệ nhân tạo. 6. Vũ Cao Đàm (1996), Phương pháp luận nghiên cứu khoa học, Nhà xuất bản khoa học kỹ thuật. 7. Hoàng Kiếm – Thanh Thủy – Chi Mai (1990), Đôi cánh I Ca Rơ, Nhà xuất bản thống kê Hà Nội. 8. Hoàng Kiếm (2001), Giải một bài toán trên máy tính như thế nào, tập 1 và 2, Nhà xuất bản giáo dục. 9. Hoàng Kiếm, Bài giảng các môn nguyên lý lập trình nâng cao, các hệ cơ sở tri thức, phương pháp luận nghiên cứu khoa học. 10. Các website sau: