zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Công nghệ thông tin

Đề tài xây dựng chương trình minh họa thuật toán A*

Chia sẻ: Ngo Hoang Liem | Ngày: | Loại File: DOCX | Số trang:35

Báo xấu

255
lượt xem 78
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

LỜI NÓI ĐẦU Mặc dù trong các thế kỉ 18, 19 và đầu thế kỉ 20, sự hình thức hóa trong khoa học và tính toán đã tạo điều kiện tiên quyết về mặt trí tuệ cho việc nghiên cứu Trí tuệ nhân tạo, nhưng phải cho đến thế kỉ 20 cùng với sự ra đời của máy tính số thì Trí tuệ nhân tạo mới trở thành một ngành khoa học có sức sống. Một thành phần không thể thiếu được của Trí tuệ nhân tạo là việc dùng các máy tính số như một phương tiện chọn lựa để...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề tài xây dựng chương trình minh họa thuật toán A*

Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa Đề tài xây dựng chương trình minh họa thuật toán A* Sinh viên thực hiện: Ngô Hoàng Liêm 1 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa MỤC LỤC MỤC LỤC ....................................................................................................................... 1 LỜI NÓI ĐẦU ................................................................................................................. 3 Phần I: LÝ THUYẾT CƠ SỞ .......................................................................................... 4 I – TRÍ TUỆ NHÂN TẠO LÀ GÌ.............................................................................................4 II – GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM.........................................................................4 III – CÁC CHIẾN LƯỢC TÌM KIẾM TỐI ƯU.........................................................................5 3.1 – Một số quy ước trong bài toán tìm đường đi............................................................................ 5 3.2 – Xây dựng hàm đánh giá ............................................................................................................. 6 IV – THUẬT TOÁN A* ..........................................................................................................6 4.1 – Thuật toán ................................................................................................................................... 6 4.2 – Một số nhận xét về thuật toán A* .............................................................................................. 7 4.3 – Ví dụ minh họa............................................................................................................................ 7 Phần II: XÂY DỰNG CHƯƠNG TRÌNH MINH HỌA .................................................... 10 I – GIỚI THIỆU SƠ LƯỢC VỀ NGÔN NGỮ LẬP TRÌNH VISUAL BASIC VÀ CÔNG CỤ LẬP TRÌNH MICROSOFT VISUAL BASIC .........................................................................10 II – TỔNG QUAN VỀ CHƯƠNG TRÌNH ............................................................................11 2.1 – Cấu trúc chương trình .............................................................................................................. 11 2.2 – Hoạt động.................................................................................................................................. 12 2.3 – Các lớp được sử dụng ............................................................................................................. 12 2.4 – Một số giao diện chương trình ................................................................................................ 13 III – CẤU TRÚC CHI TIẾT..................................................................................................15 3.1 – Định nghĩa các lớp ................................................................................................................... 15 3.2 – Các thủ tục vẽ ........................................................................................................................... 17 3.3 – Các th ủ tục và hàm hỗ trợ ....................................................................................................... 21 3.4 – mainForm – Form chính của chương trình............................................................................. 24 KẾT LUẬN.................................................................................................................... 33 Sinh viên thực hiện: Ngô Hoàng Liêm 2 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa LỜI NÓI ĐẦU Mặc dù trong các thế kỉ 18, 19 và đầu thế kỉ 20, sự hình thức hóa trong khoa học và tính toán đã tạo điều kiện tiên quyết về mặt trí tuệ cho việc nghiên cứu Trí tuệ nhân tạo, nhưng phải cho đến thế kỉ 20 cùng với sự ra đời của máy tính số thì Trí tuệ nhân tạo mới trở thành một ngành khoa học có sức sống. Một thành phần không thể thiếu được của Trí tuệ nhân tạo là việc dùng các máy tính số như một phương tiện chọn lựa để tạo ra và thử nghiệm các lý thuyết về trí tuệ. Hai mối quan tâm nền tảng nhất của các nhà nghiên cứu Trí tuệ nhân tạo là biểu diễn tri thức và tìm kiếm. Sự quan tâm thứ nhất chú ý đến vấn đề nắm bắt theo một ngôn ngữ tri thức đầy đủ mà hành vi thông minh đòi hỏi. Trong khi đó, tìm kiếm là kĩ thuật giải quyết vấn đề theo cách khảo sát có hệ thống một không gian trạng thái bài toán, tức là các giai đoạn tuần tự và có chọn lựa trong quá trình giải quyết vấn đề. Trong các chiến lược tìm kiếm, người ta biểu diễn quá trình giải quyết vấn đề như một quá trình tìm kiếm đường đi trên một đồ thị không gian trạng thái mà trong đó: mỗi trạng thái bài toán được xem như một nút của đồ thị hay c òn gọi là một trạng thái và các đường chuyển trạng thái khi áp dụng các phép toán hợp lệ vào một trạng thái nào đó sẽ chuyển bài toán từ trạng thái này sang trạng thái khác được gọi là các liên kết của đồ thị. Đây không phải chỉ là một trong những kĩ thuật hiệu quả mà tính quy tắc và chính xác của nó làm cho việc cài đặt trên máy tính ma ng tính trực tiếp. Trong bài tập lớn này, em tìm hiểu về Thuật toán tìm kiếm A* và sử dụng ngôn ngữ lập trình Visual Basic để xây dựng chương trình minh họa cho thuật toán. Dựa trên sự chỉ bảo tận tình của các thầy cô giáo và sự giúp đỡ của các bạn cùng lớp, dựa trên những kiến thức đã học, em đã hoàn thành đề tài này tuy nhiên vẫn còn nhiều sai sót, rất mong có sự đóng góp ý kiến của các thầy cô và các bạn để đề tài của em đ ược hoàn thiện h ơn. Em xin chân thành cảm ơn! Sinh viên thực hiện: Ngô Hoàng Liêm 3 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa Phần I: LÝ THUYẾT CƠ SỞ I – TRÍ TUỆ NHÂN TẠO LÀ GÌ Thuật ngữ trí tuệ nhân tạo được John McCarthy đưa ra trong hội thảo ở Dartmouth vào mùa hè năm 1956. Đây được xem là thời điểm ra đời thật sự của lĩnh vực nghiên cứu trí tuệ nhân tạo (TTNT). Trong các sách viết về TTNT các năm gần đây, các tác giả đã đưa ra nhiều định nghĩa về TTNT, nhưng nhìn chung, ta có thể hiểu: “TTNT là sự thiết kế và nghiên c ứu các chương trình máy tính ứng xử một cách thông minh. Các chương trình này được xây dựng để thực hiện các hành vi mà khi thực hiện ở người và động vật chúng ta xem là thông minh” (“Dean, Allen and Aloimonos, 1995). Hiện nay nhiều nhà nghiên c ứu quan niệm rằng, TTNT là lĩnh vực nghiên cứu sự thiết kế các tác nhân thông minh (intelligent agent). Tác nhân thông minh là bất cứ cái gì tồn tại trong môi trường và hành động một cách thông minh. Mục tiêu khoa học của TTNT là hiểu được bản chất các hành vi thông minh. Mục tiêu thực tiễn, công nghệ của TTNT là xây dựng n ên các hệ thông minh, các máy thông minh. Một số ngành khoa học khác cũng nghiên cứu các năng lực được xem là thông minh của con người như: Triết học, Tâm lý học… Nhưng khác với các ngành khoa học trên, TTNT là một ngành của khoa học máy tính – nghiên c ứu xử lý thông tin bằng máy tính. Do đó, TTNT đặt ra mục tiêu nghiên cứu: làm thế nào để hiểu được các hành vi thông minh bằng thuật toán, rồi nghiên cứu các phương pháp cài đặt các chương trình có thể thực hiện đ ược các hành vi thông minh. Như vậy chúng ta cần xây dựng các mô hình tính toán (computational models) phục vụ cho việc giải thích, mô tả các hành vi thông minh bằng thuật toán, tiếp theo ta cần chỉ ra tính hiệu quả, tính khả thi của thuật toán thực hiện một nhiệm vụ và từ đó đưa ra các phương pháp cài đặt. II – GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM Vấn đề tìm kiếm, một cách tổng quát, có thể hiểu là tìm một đối tượng thỏa mãn một số đòi hỏi nào đó, trong một tập hợp rộng lớn các đối tượng. Trong các lĩnh vực nghiên Sinh viên thực hiện: Ngô Hoàng Liêm 4 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa cứu của trí tuệ nhân tạo, chúng ta thường xuyên phải đối đầu với vấn đề tìm kiếm. Đặc biệt trong lập kế hoạch và học máy, tìm kiếm đóng vai trò rất quan trọng. Trong khuôn khổ chương trình giảng dạy của nhà trường, chúng ta sẽ được tìm hiểu các kỹ thuật sau:  Các kỹ thuật tìm kiếm mù.  Các kỹ thuật tìm kiếm kinh nghiệ m (tìm kiế m heuristic).  Các kỹ thuật tìm kiếm tối ưu.  Các phương pháp tìm kiế m có đối thủ. III – CÁC CHIẾN LƯỢC TÌM KIẾM TỐI ƯU Vấn đề tìm kiếm tối ưu, một cách tổng quát, có thể phát biểu như sau: một đối tượng x trong không gian tìm kiếm được gán với một số đo giá trị của đối tượng đó f(x), mục tiêu của ta là tìm được đối tượng có giá trị f(x) lớn nhất (hoặc nhỏ nhất) trong không gian tìm kiếm. Hàm f(x) được gọi là hàm mục tiêu. Các chiến lược tìm kiếm bao gồm:  Các kỹ thuật tìm đường đi ngắn nhất trong không gian trạng thái: Thuật toán A*, thuật toán nhánh – và – cận.  Các kỹ thuậ t tìm kiếm đố i tượng tốt nhất: Tìm kiế m leo đồi, tìm kiếm Gradient, tìm kiế m mô phỏng luyện kim.  Tìm kiế m bắ t chước sự tiến hóa: Thuật toán di truyền. 3.1 – Một số quy ước trong bài toán tìm đường đi  Giá trị của cung (a,b) là độ dài đường nố i từ a đến b.  Độ dài đường đi từ trạng thái đầu đến trạng thái kế t thúc là tổng độ dài các cung trên đường đi.  Không gian tìm kiếm: T ất cả các đường đi từ trạng thái đầu đến trạng thái đích. Sinh viên thực hiện: Ngô Hoàng Liêm 5 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa 3.2 – Xây dựng hàm đánh giá Giả sử u là một trạng thái tới (đi từ trạng thái đầu đến u), xây d ựng các hàm:  g(u): đánh giá độ dài đường đi từ trạng thái đầu đến u.  h(u): đánh giá độ dài đường đi từ u đến trạng thái đích.  f(u) = g(u) + h(u): đánh giá đ ộ dài đường đi từ trạng thái đầu đến trạng thái đích mà đi qua u. IV – THUẬT TOÁN A* Thuật toán A* là thuật toán sử dụng kỹ thuật tìm kiếm tốt nhất đầu tiên với hàm đánh giá f(u). Tức là: trong các trạng thái chờ phát triển, chọn trạng thái có giá trị hàm đánh giá nhỏ nhất (hoặc lớn nhất) để phát triển tiếp. Đỉnh được phát triển có thể ở mức hiện tại hoặc các mức trên. 4.1 – Thuật toán 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu; 2. Loop do 2.1. If L rỗng then { thông báo thất bại; stop;} 2.2. Loại trạng thái u ở đầu danh sách L; 2.3. if u là trạng thái đích then { thông báo thành công; stop;} 2.4. for mỗi trạng thái v kề u do { g(v) ← g(u) + k(u,v); f(v) ← g(v) + h(v); Đặt v vào danh sách L; } 2.5. Sắp xếp L theo thứ tự tăng dần của hàm f sao cho trạng thái có Sinh viên thực hiện: Ngô Hoàng Liêm 6 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa giá trị của hàm f nhỏ nhất ở đầu danh sách; End loop; 4.2 – Một số nhận xét về thuật toán A* Chúng ta đưa ra một số nhận xét về thuật toán A* như sau: Người ta chứng minh được rằng, nếu hàm đánh giá h(u) là đánh giá thấp (trường hợp đặc biệt, h(u) = 0 với mọi trạng thái u ) thì thuật toán A* là thuật toán tối ưu, tức là nghiệm mà nó tìm ra là ngiệm tối ưu. Ngoài ra, nếu độ dài của các cung không nhỏ hơn một số dương δ nào đó thì thuật toán A* là thuật toán đầy đủ theo nghĩa rằng, nó luôn dừng và tìm ra cây nghiệm. Trong trư ờng hợp hàm đánh giá h (u) = 0 với mọi u , thuật toán A* chính là thuật toán tìm kiếm tốt nhất đầu tiên với hàm đánh giá g(u). Thuật toán A* đã đ ược chứng tỏ rằng là thuật toán hiệu quả nhất trong số các thuật toán đầy đủ và tối ưu cho vấn đề tìm kiếm đường đi ngắn nhất. 4.3 – Ví dụ minh họa Để thấy được thuật toán A* làm việc ra sao, ta xét đồ thị không gian trạng thái như hình vẽ. Trong đó trạng thái ban đầu là trạng thái A, trạng thái đích là B, các số ghi cạnh các cung là độ dài cung đó, các số cạnh các đỉnh là giá trị của hàm h. Đầu tiên, phát triển đỉnh A sinh ra các đỉnh con C, D, E và F. Tính giá trị hàm f tại các đỉnh này ta có: g(C) = 9 f(C) = 9 + 1 5 = 24 g(D) = 7 f(D) = 7 + 6 = 13 g(E) = 1 3 f(E) = 13 + 8 = 21 g(F) = 2 0 f(F) = 20 + 7 = 27 Sinh viên thực hiện: Ngô Hoàng Liêm 7 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa Như vậy đỉnh tốt nhất là D (vì f(D) = 1 3 là nhỏ nhất). phát triển đỉnh D, ta nhận được các đỉnh con H và E. ta đánh giá H và E (mới). g (H) = g(D) + độ dài cung (D, H) = 7 + 8 = 15 f(H) = 1 5 + 10 = 25 Đường đi tới E qua D có độ dài: g (E) = g(D) + độ dài cung (D,E) = 7 + 4 = 1 1 f(E) = g(E) + h (E) = 1 1 + 8 = 19 Trong số các đỉnh chờ phát triển thì đỉnh E với đánh giá f(E) = 19 là đ ỉnh tốt nhất. Phát triển đỉnh này, ta nhận đ ược các đỉnh con của nó là K và I. Chúng ta tiếp tục quá trình trên cho tới khi đỉnh được chọn để phát triển là đỉnh kết thúc B, độ dài đường đi n gắn nhất tới B là g (B) = 19. Để theo dõi quá trình làm việc của thuật toán, ta lập bảng phân tích gồm 4 cột:  Lần lặp: số lần lặp của thu ật toán  u: đ ỉnh phát triể n u  v: các đỉnh con của u  L: Danh sách L Sinh viên thực hiện: Ngô Hoàng Liêm 8 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa () Với quy ước: đỉnh ( ). Ta có bảng phân tích như sau A→D→E→I→B Đường đi ngắn nhất: Quá trình tìm kiếm trên được mô tả bởi cây tìm kiếm sau. Sinh viên thực hiện: Ngô Hoàng Liêm 9 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa Phần II: XÂY DỰNG CHƯƠNG TRÌNH MINH HỌA I – GIỚI THIỆU SƠ LƯỢC VỀ NGÔN NGỮ LẬP TRÌNH VISUAL BASIC VÀ CÔNG CỤ LẬP TRÌNH MICROSOFT VISUAL BASIC Visual Basic (viết tắt VB) là một ngôn ngữ lập trình hướng sự kiện (event-driven) và môi trường phát triển tích hợp (IDE) kết bó được phát triển đầu tiên bởi Alan Cooper dưới tên Dự án Ruby (Project Ruby), và sau đó được Microsoft mua và cải tiến nhiều. Visual Basic đã được thay thế bằng Visual Basic.NET. Phiên bản cũ của Visual Basic bắt nguồn phần lớn từ BASIC và để lập trình viên phát triển các giao diện người dùng đồ họa (GUI) theo mô hình phát triển ứng dụng nhanh (Rapid Application Development, RAD); truy cập các cơ sở dữ liệu dùng DAO (Data Access Objects), RDO (Remote Data Objects), hay ADO (ActiveX Data Objects); và lập các điều khiển và đối tượng ActiveX. Một lập trình viên có thể phát triển ứng dụng dùng các thành phần (component) có sẵn trong Visual Basic. Các chương trình bằng Visual Basic cũng có thể sử dụng Windows API, nhưng làm vậy thì phải sử dụng các khai báo hàm bên ngoài. Trong lĩnh vực lập trình thương mại, Visual Basic có một trong những nhóm khách hàng lớn nhất. Theo một số nguồn, vào năm 2003, 52% của những lập trình viên sử dụng Visual Basic, làm nó thành ngôn ngữ lập trình phổ biến nhất vào lúc đó. Tuy nhiên, cuộc nghiên cứu của Evans Data cho rằng 43% của các lập trình viên đó có ý định đổi qua một ngôn ngữ khác. Dù vậy, trong thực hành thí nghiệm thì VB vẫn được d ùng khá phổ biến vì sự gần gũi và dễ học dễ làm của nó. Hiện nay xu hướng lập trình đang chuyển dần sang .NET vì những ưu điểm và lợi thế tuyệt vời của nó. Microsoft Visual Basic. NET hay còn gọi là VB.NET được Microsoft phát triển từ cuối thập niên 1990 và ra phiên bản đầu vào năm 2002 (cùng với Visual C# và ASP.NET). Phiên bản mới nhất hiện nay là Visual Basic. NET 2010. Sinh viên thực hiện: Ngô Hoàng Liêm 10 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa II – TỔNG QUAN VỀ CHƯƠNG TRÌNH 2.1 – Cấu trúc chương trình Chương trình gồm có các thành phần như sau:  Form chính: mainForm.vb  Form tác giả : author.vb  Form hướng dẫn sử dụng: tutorial.vb  Form hiển thị bảng kết quả: process.vb  Module chứa các hàm và thủ tục hỗ trợ: functions.vb  Module chứa các hàm và thủ tục vẽ: draw.vb  Module chứa các hàm và thủ tục lưu, mở đồ thị: saveload.vb  Khai báo các lớp sử dụng trong chương trình: classes.vb Form giao diện chính của chương trình (mainForm.vb) bao gồm các control của Visual Basic, các sự kiện của control được lập trình bên trong code của mainForm.vb. Thuật toán A* và các thao tác nhập, xuất được thể hiện ở form này. Các bạn có thể mở p roject đi kèm với tập báo cáo này để biết thêm chi tiết. Form hướng dẫn sử dụng (tutorial.vb) hiển thị những h ướng dẫn cơ bản và một số chú ý khi sử dụng chương trình. Sinh viên thực hiện: Ngô Hoàng Liêm 11 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa Form tác giả (author.vb) bao gồm các thông tin về chương trình và tác giả. Code của form này chỉ lấy thông tin chương trình rồi đưa ra hiển thị (code được viết bên trong phần onload của form). Form hiển thị kết quả (process.vb) bao gồm hai control, một label ghi tiêu đề và một listView. Code của form này chỉ lấy kết quả tính toán đổ vào listView và hiển thị ra màn hình (viết trong phần onload của form). Chúng ta sẽ đi chi tiết hơn ở phần định nghĩa các hàm, thủ tục trong module và định nghĩa các class sử dụng trong chương trình ở phần sau. 2.2 – Hoạt động Các thủ tục và sự kiện trong form chính sẽ chứa các dòng lệnh nhập và xuất kết quả. Quá trình nhập và xuất được thực hiện thông qua các phương thức có sẵn của VB và các hàm, thủ tục được định nghĩa trong các module. Để phục vụ cho thuật toán A* - thuật toán chính của chương trình - thì các thành phần hỗ trợ cho nó cũng được định nghĩa đầy đủ trong các module. 2.3 – Các lớp được sử dụng Để làm việc có hiệu quả hơn và tận dụng các ưu điểm của lập trình hướng đối tượng, chương trình đã sử dụng phương pháp lập trình này. Một lớp các đỉnh được khai báo trong file classes.vb. Thực chất đây là file được thêm vào từ menu add new item, class. Các bạn mở file này ra sẽ thấy các định nghĩa cho các lớp. Có 3 lớp được sử dụng trong chương trình là lopDinh, Child và listItem trong đó:  lopDinh là lớp chính bao gồm các thuộc tính cần thiết của một đỉnh trong thuậ t toán A* (tọa độ , tên đỉnh, giá trị hàm đánh giá, các đỉnh con và khoảng cách tương ứng, các đỉnh cha, giá trị hàm f và g)  Child là lớp các con của một đỉnh, nó gồm các thuộc tính như cname (tên con) và cdistance(khoảng cách từ cha của nó đến nó)  listItem là lớp được s ử dụng để lưu kế t quả tính toán và đưa ra bảng kết quả. Lớp này gồm 4 thuộc tính tương ứng với bảng s ử dụng để thực hiện thuật Sinh viên thực hiện: Ngô Hoàng Liêm 12 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa toán A* (các thuộc tính gồm số lần lặp, đỉnh u, tập các đ ỉnh con v, và danh sách L). Chi tiết về lớp sẽ được chi tiết hóa ở phần sau. 2.4 – Một số giao diện chương trình Giao diện chính của ch ương trình Sinh viên thực hiện: Ngô Hoàng Liêm 13 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa Xử lý lỗi trong chương trình Sau khi tìm kiếm thành công Sinh viên thực hiện: Ngô Hoàng Liêm 14 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa Kết quả tìm kiếm III – CẤU TRÚC CHI TIẾT 3.1 – Định nghĩa các lớp Các lớp đ ược sử dụng trong chương trình đ ược định nghĩa đầy đủ trong file c lasses.vb 3.1.1 – Lớp các đỉnh – lớp chính của chương trình – lớp lopDinh Lớp đỉnh cũng như các lớp khác trong chương trình, không đ ịnh nghĩa thuộc tính trực tiếp (định nghĩa giống cú pháp as ) mà đ ịnh nghĩa các biến riêng để lưu giá trị và đ ịnh nghĩa các thuộc tính để thông qua các thuộc tính đó, lưu các giá trị cần thiết vào các biến riêng. Theo các tài liệu lập trình hướng đối tượng thì phương pháp này được khuyến khích sử dụng vì có nhiều ưu điểm h ơn và hạn chế được các nhược điểm của khai báo thuộc tính trực tiếp. Các thuộc tính của lopDinh bao gồm:  x: tọa đ ộ x của đỉnh, kiểu số nguyên (Short)  y: tọa đ ộ y c ủa đỉnh, kiểu số nguyên (Short)  name: tên đỉnh, kiểu Char  value: giá trị hàm đánh giá h, kiểu số nguyên (Short)  fval: giá trị hàm f, kiểu số n guyên (Short)  gval: giá trị hàm g, kiể u số nguyên (Short) Sinh viên thực hiện: Ngô Hoàng Liêm 15 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa  childs: các đỉnh con, thuộc tính này là tập hợp các đối tượng thuộc lớp Child sẽ được nói đến ngay sau phần này.  parents: có kiểu là string, lưu tên các đỉnh cha Riêng 2 thuộc tính childs và parents được định nghĩa trực tiếp. Mỗi thuộc tính được định nghĩa bằng phát biểu: Property ([tham biến nếu có]) As Kiểu có thể là kiểu dữ liệu nguyên thủ y hoặc các lớp đối tượng… Việc định nghĩa thuộc tính như trên giống cho tất cả các lớp được sử dụng trong chương trình. Hai thủ tục New và New(danh sách tham biến) dùng để khởi tạo giá trị mặc định cho các thuộc tính của lớp. Chi tiết về định nghĩa lớp, c ác bạn có thể tìm hiểu trên thư viện của Microsoft (http://msdn.microsoft.com). Sinh viên thực hiện: Ngô Hoàng Liêm 16 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa Các lớp nói chung, đa số đều được định nghĩa tuân theo tư tưởng lập trình hướng đối tượng. Nh ưng do tính phức tạp của chương trình chưa phải là cao, nên một số thuộc tính vẫn được định nghĩa một cách trực tiếp. 3.1.2 – Lớp các con - lớp Child Lớp này gồm có các thuộc tính sau:  cname: kiểu Char, lưu tên của đ ỉnh con  cdistance: kiểu Short, lưu giá trị là khoảng cách từ cha nó đến nó Một đ ỉnh thuộc lopDinh sẽ có một thuộc tính childs lưu tập hợp các con và khoảng cách tương ứng. Với một dinh thuộc lopDinh thì các con của nó sẽ là dinh.childs(i), với i là ch ỉ số tương ứng (vì childs là một danh sách các đối tượng thuộc lớp Child). 3.1.3 – lớp listItem Lớp này gồm các thuộc tính tương ứng với bảng quá trình tính toán:  lanlap: kiểu Short, lưu số lần lặp của thuật toán  u: kiểu String, lưu tên đỉnh u và các giá trị hàm f, g tương ứng  v: kiểu String, lưu tên các đỉnh v và các giá trị hàm f, g tương ứng  L: kiể u String, lưu danh sách L gồm tên các đ ỉnh và các giá trị hàm f, g tương ứng Lớp này được sử dụng để lưu các kết quả tính toán và đưa ra bảng tính toán (form process.vb). Các giá trị hàm f, g s ẽ đ ược chuyển sang xâu ký tự trước khi thêm vào thuộc tính u, v và L của đối tượng thuộc lớp này. 3.2 – Các thủ tục vẽ Các thủ tục vẽ được định nghĩa trong Module functions.vb. 3.2.1 – Vẽ một đỉnh của đồ thị Sử dụng các thủ tục và hàm có sẵn để vẽ. Tạo một đối tượng đồ họa trên panel vẽ (panel này có tên là pnlMain và thuộc form chính mainForm). Sử dụng thủ tục FillEllipse với chiều rộng bằng chiều ngang để vẽ một hình tròn không viền và sử dụng Sinh viên thực hiện: Ngô Hoàng Liêm 17 Lớp ĐHCQ K6B
Đề tài: Xây dựng chương trình minh họa thuật toán A* GVHD: Nông Th ị Hoa thủ tục DrawEllipse để vẽ viền cho nó. Tương tự, vẽ một elip khác bên trên elip cũ để thể hiện giá trị hàm đánh giá. Các lệnh rẽ nhánh If … Then đ ược dùng để căn chỉnh vị trí cho các ký tự có độ rộng đặc biệt. Thủ tục drawString dùng để vẽ một xâu ký tự lên màn hình ở vị trí được chỉ đ ịnh. Thủ tục này dùng để vẽ tên đ ỉnh và giá trị hàm đánh giá . Ở thủ tục vẽ mũi tên n ối hai đỉnh của đồ thị, nó cũng được sử dụng để vẽ giá trị khoảng cách giữa hai đỉnh. sFont, vFont là kiểu font với kích c ỡ và kiểu (đậm, nghiêng, thường, gạch chân…) cho các xâu ký tự tương ứng (tên đỉnh, giá trị hàm đánh giá), ta khai báo hai kiểu Font này để phục vụ cho lệnh drawString. Các tham biến truyền vào thủ tục này gồm có: Sinh viên thực hiện: Ngô Hoàng Liêm 18 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa  dinh: đối tượng thuộc lopDinh  p: đối tượng thuộc lớp System.Drawing.pen dùng để vẽ viền  b: đối tượng thuộc lớp System.Drawing.brush dùng để tô màu 3.2.2 – Thủ tục vẽ mũi tên nối hai đỉnh của đồ thị Trong thủ tục này, chúng ta sẽ sử dụng một chút kiến thức về toán học. Hình vẽ thể hiện cách nghĩ và phương pháp thực hiện của thủ tục này. Ở hình vẽ, r là bán kính của đường tròn. Từ các tọa độ của 2 đỉnh, ta tính được các dx = x2 – x1 và dy = d2 – d1, ta tính được độ dài đoạn thẳng nối 2 tâm của nó, và nh ờ đó tính được sinα và cosα. Theo phương trình đường tròn thì ta sẽ tìm được giao điểm của đoạn thẳng nối 2 tâm của 2 đỉnh với đ ường tròn tương ứng. x = x1 + r*sinα và y = y1 + r*cos α (x1,y1) rα Đỉnh 1 size y2- y1 (x2,y2) x2-x1 Đỉnh 2 Tùy vào hướng của đoạn thẳng (vị trí của đỉnh thứ 2 so với đỉnh thứ nhất) mà ta sẽ cộng hoặc trừ tương ứng. Sau khi tính được 2 tọa độ giao điểm, ta vẽ một đ ường thẳng nối 2 tọa độ này và vẽ một hình tam giác thể hiện cho mũi tên ở cuối đoạn thằng. Cách Sinh viên thực hiện: Ngô Hoàng Liêm 19 Lớp ĐHCQ K6B
Đề tài: Xây dựng ch ương trình minh h ọa thuật toán A* GVHD: Nông Thị Hoa tính tọa độ này còn được mở rộng để tìm các vị trí thích hợp để vẽ giá trị khoảng cách từ đỉnh cha tới đỉnh con. Các lệnh được sử dụng gồm drawLine để vẽ đoạn thẳng, drawString để vẽ xâu ký tự. Biến arrow dùng để tạo ra mộ t hình mũi tên ở cuối đoạn thẳng. Ở đây thì đối với đỉnh thứ 2, điểm cuối của đoạn thẳng sẽ cách giao điểm của đoạn thẳng đó kéo dài và đường tròn một khoảng = 4. Ta sẽ dùng khoảng trống này để vẽ phần nhọn của mũi tên. Các tham biến truyền vào của thủ tục này gồm có:  Đỉnh cha và đỉnh con: đố i tượng thuộc lớp lopDinh.  Khoảng cách tương ứng: kiể u số nguyên Short  db (dinh brush), dp (dinh pen): tương ứng thuộc lớp brush và lớp pen. Tham biến này dùng để xác đ ịnh giá trị màu cho viền và màu tô cho đỉnh.  lb (line brush), lp (line pen): tương ứng thuộc lớp brush và lớp pen. Tham biến này dùng để xác đ ịnh giá trị màu cho đoạn thẳng và màu mũi tên. 3.2.3 – Thủ tục vẽ toàn bộ đồ thị Thủ tục này dùng để vẽ toàn bộ đồ thị với màu ban đầu (ta coi màu trắng, viền xanh, đường nối màu xám là các màu ban đầu của đồ thị). Cách ngh ĩ của thủ tục này là:  Kiểm tra xem đồ thị có rỗng hay không. Nếu rỗng thì lệnh return được thực hiện.  Nếu đồ thị không rỗng, duyệt tất cả các đỉnh thuộc danh sách đỉnh, ứng với mỗi đỉnh, vẽ mũi tên nối đỉnh đó với các con của nó. Vị trí các đỉnh con trong danh sách được tìm qua thủ tục pSearch. Sinh viên thực hiện: Ngô Hoàng Liêm 20 Lớp ĐHCQ K6B

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA

165 tài liệu

2068 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.