Một Số Thuật Toán Tìm đường đi Ngắn Nhất Và Xây Dựng ứng Dụng ...

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (51 trang)

Trang chủ

Công nghệ thông tin

Hệ thống thông tin

Một số thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng GAME PIKACHU

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.15 MB, 51 trang )

LỜI CẢM ƠNLời đầu tiên em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới cácthầy, cô giáo trường Đại học sư phạm Hà Nội 2, đặc biệt là các thầy, cô giáotrong khoa Công nghệ Thông tin đã truyền đạt cho em những kiến cần thiết vàbổ ích trong suốt quá trình học tập tại trường. Luận văn tốt nghiệp là cơ hội đểcho em có thể áp dụng, tổng kết lại những kiến thức mà mình đã học. Đồngthời rút ra được những kinh nghiệm thực tế và quý giá trong suốt quá trìnhthực hiện đề tài. Trong thời gian để hoàn thành khóa luận em đã nhận được sựhướng dẫn tận tình của cô Lưu Thị Bích Hương cùng với các thầy, cô giáo vàcác bạn lớp K35-Tin học đã giúp em hoàn thành tốt khóa luận này. Là sinhviên lần đầu nghiên cứu khoa học chắc chắn đề tài của em không tránh khỏinhững thiếu sót, vì vậy em rất mong sự đóng góp ý kiến của các thầy, cô giáovà các bạn để đề tài của em được hoàn thiện. Một lần nữa em xin chân thànhcảm ơn công lao dạy dỗ chỉ bảo của thầy, cô giáo. Kính chúc quý thầy, côgiáo mạnh khỏe, tiếp tục đạt được nhiều thắng lợi trong nghiên cứu khoa họcvà sự nghiệp trồng người.Em xin chân thành cảm ơn!Hà Nội, tháng 5 năm 2013Sinh viênLê Thị Hạnh1LỜI CAM ĐOANTên em là: LÊ THỊ HẠNHSinh viên lớp: K35 - Tin học, khoa Công nghệ Thông tin, trường Đạihọc sư phạm Hà Nội 2.Em xin cam đoan:1. Đề tài: "Một số thuật toán tìm đường đi ngắn nhất và xây dựngứng dụng game Pikachu" là sự nghiên cứu cua riêng em, dưới sự hướng dẫncủa cô giáo Th.S Lưu Thị Bích Hương.2. Khóa luận hoàn toàn không sao chép của các tác giả nào khác.Nếu sai em xin hoàn toàn chịu trách nhiệm.Hà Nội, tháng 5 năm 2013Sinh viên2MỤC LỤCMỞ ĐẦU ........................................................................................................... 1CHƯƠNG 1: CƠ SỞ LÝ THUYẾT ................................................................... 81.1. Giới thiệu về ngôn ngữ Visual C#. ......................................................... 101.2. Lịch sử phát triển của trí tuệ nhân tạo..................................................... 101.3. Tổng quan về khoa học trí tuệ nhân tạo. ................................................. 111.4. Các khái niệm cơ bản ............................................................................. 121.5. Vai trò của trí tuệ nhân tạo. .................................................................... 131.6. Các kỹ thuật trí tuệ nhân tạo ................................................................... 141.7. Một số vấn đề trí tuệ nhân tạo quan tâm. ................................................ 16CHƯƠNG 2: LÝ THUYẾT ĐỒ THỊ VÀ MỘT SỐ THUẬT TOÁN TÌMĐƯỜNG ĐI NGẮN NHẤT .............................................................................. 192.1. Lý thuyết đồ thị ......................................................................................... 192.1.1. Định nghĩa đồ thị................................................................................. 192.1.2. Định nghĩa đường đi, chu trình, đồ thị liên thông. ............................... 222.2. Một số khái niệm ....................................................................................... 242.2.1. Mở đầu ................................................................................................ 242.2.2. Giải quyết vấn đề bằng phương pháp tìm kiếm ................................... 252.2.3. Biểu diễn vấn đề trong không gian trạng thái ...................................... 262.2.4. Đường đi ngắn nhất xuất phát từ một đỉnh .......................................... 272.2.5. Tìm kiếm trên đồ thị và/hoặc............................................................... 282.3. Một số thuật toán tìm đường đi ngắn nhất ................................................. 282.3.1. Bài toán tìm đường đi ngắn nhất.......................................................... 282.3.2. Thuật toán tìm kiếm theo chiều sâu (Depth First Search - DFS) .......... 292.3.3. Thuật toán tìm kiếm theo chiều rộng (Breadth First Search)................ 322.3.4. Thuật toán tìm kiếm sâu dần ............................................................... 352.3.4. Thuật toán Dijkstra tìm đường đi ngắn nhất ........................................ 37CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG GAME PIKACHU .......................... 4133.1. Giới thiệu bài toán ..................................................................................... 413.2. Cấu trúc game Pikachu .............................................................................. 413.3. Cách xây dựng game Pikachu .................................................................... 433.3.1. Cơ sở lý thuyết .................................................................................... 433.3.2. Áp dụng thuật toán tìm kiếm theo chiều rộng ...................................... 443.4. Một số giao diện và kết quả chạy chương trình.......................................... 463.4.1. Giao diện chính của chương trình khi mới tạo ..................................... 463.4.2. Giao diện khi chạy Auto Play .............................................................. 473.4.3. Giao diện khi người chơi tự chơi ......................................................... 48KẾT LUẬN VÀ PHƯƠNG HƯỚNG PHÁT TRIỂN ....................................... 49TÀI LIỆU THAM KHẢO ................................................................................ 514MỞ ĐẦU1. Lý do và mục đích chọn đề tàiNgày nay, cùng với sự phát triển vượt bậc của khoa học kỹ thuật, đặcbiệt là sự phát triển Công nghệ Thông tin là một trong những lĩnh vực có nhiềuđóng góp thiết thực nhất trong cuộc sống. Máy tính điện tử đã và đang trởthành công cụ đắc lực không chỉ giảm nhẹ sức lao động là lao động trí tuệ màcòn trợ giúp cho con người những kiến thức mới trước đây khó hình dung. Mộttrong những ứng dụng của máy tính là lưu trữ dữ liệu giúp cho các nhà quản lýnắm bắt và xử lý tình huống thông tin một cách chính xác, kịp thời và an toàn.Trí tuệ nhân tạo trong lĩnh vực công nghệ thông tin là ngành khoa họcnghiên cứu những phương thức để máy tính có khả năng tư duy suy nghĩ nhưcon người. Ngoài ra trí tuệ nhân tạo còn là ngành nghiên cứu những phươngthức để giúp máy tính làm được những công việc mà tại thời điểm đó nó lànhững công việc mà con người chưa làm được hay không làm được. Mộttrong những nghiên cứu đó là đưa ra các giải thuật tìm đường đi ngắn nhất, tốiưu nhất phục vụ việc giải quyết các vấn đề của bài toán một cách nhanh nhấtcó thể.Là một sinh viên khoa Công nghệ Thông tin, trường Đại học sư phạmHà Nội 2, với mong muốn được nghiên cứu và tìm hiểu sâu hơn về vấn đềnày, bắt đầu làm quen với công việc nghiên cứu khoa học em đã chọn đề tài:“Một số thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng GamePikachu”. Đề tài được xây dựng trên ngôn ngữ lập trình C# trong bộMicrosoft Visual Studio 2008 với hệ quản trị cơ sở dữ liệu Microsoft SQLSever 2005.2. Đối tượng và phạm vi nghiên cứu2.1. Đối tượng nghiên cứuTìm hiểu một số thuật toán tìm đường đi ngắn nhất.52.2. Phạm vi nghiên cứu- Đề tài tập trung nghiên cứu một số thuật toán tìm đường đi ngắn nhấtnhư: Thuật toán tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều rộng,thuật toán tìm kiếm sâu dần, thuật toán Dijkstra.- Game Pikachu sử dụng thuật toán: Thuật toán tìm kiếm theo chiều rộng.3. Nhiệm vụ nghiên cứuTập trung tìm hiểu các vấn đề sau:- Tìm hiểu về trí tuệ nhân tạo.- Tìm hiểu về lý thuyết đồ thị.- Tìm hiểu bài toán tìm đường đi ngắn nhất.- Tìm hiểu một số thuật toán tìm đường đi ngắn nhất.- Tìm hiểu đường đi ngắn nhất xuất phát từ một đỉnh.- Tìm hiểu ngôn ngữ lập trình C#.- Xây dựng ứng dụng dựa trên ngôn ngữ lập trình C# để mô phỏng.4. Phương pháp nghiên cứu4.1. Phương pháp nghiên cứu lý luậnNghiên cứu qua việc đọc sách, báo và các tài liệu liên quan nhằm xâydựng cơ sở lý thuyết của đề tài và các biện pháp cần thiết để giải quyết cácvấn đề của đề tài.4.2. Phương pháp chuyên giaTham khảo ý kiến các chuyên gia Tin học để có thể thiết kế chươngtrình phù hợp với yêu cầu thực tiễn, đáp ứng được yêu cầu của người sử dụng.4.3. Phương pháp thực nghiệmThông qua quan sát thực tế, yêu cầu của cơ sở, những lý luận đượcnghiên cứu và kết quả đạt được qua những phương pháp trên, chương trình sẽđược đưa vào chạy thử để từ đó có những điều chỉnh phù hợp.65. Ý nghĩa khoa học và thực tiễn của đề tàiBài toán tìm đường đi ngắn nhất là bài toán quan trọng của lý thuyết đồthị, bài toán tìm được lời giải tối ưu nhất và giải quyết các vấn đề một cáchnhanh nhất.Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất có ý nghĩato lớn như: Bài toán chọn hành trình tiết kiệm nhất theo tiêu chuẩn khoảngcách, thời gian hoặc chi phí trên một mạng giao thông đường bộ. Bài toánchọn một phương pháp tiết kiệm nhất để đưa một hệ thống động lực từ trạngthái xuất phát đến một trạng thái đích. Bài toán lập lịch thi công các côngđoạn trong một công trình thi công lớn. Bài toán lựa chọn đường truyền tinvới chi phí nhỏ nhất trong mạng thông tin…6. Cấu trúc khóa luậnNgoài phần mở đầu, kết luận và phương hướng phát triển. Nội dungcủa khóa luận bao gồm 3 chương:Chương 1: Cơ sở lý thuyếtChương 2: Lý thuyết đồ thị và một số thuật toán tìm đường đi ngắn nhấtChương 3: Xây dựng ứng dụng game Pikachu7CHƯƠNG 1: CƠ SỞ LÝ THUYẾT1.1. Giới thiệu về ngôn ngữ Visual C#Ngôn ngữ C# khá đơn giản, chỉ khoảng 80 từ khóa và hơn mười mấykiểu dữ liệu được xây dựng sẵn. Tuy nhiên, ngôn ngữ C# có ý nghĩa cao khinó thực thi những khái niệm lập trình hiện đại. C# bao gồm tất cả những hỗtrợ cho cấu trúc, thành phần component, lập trình hướng đối tượng. Nhữngtính chất đó hiện diện trong một ngôn ngữ lập trình hiện đại. Và ngôn ngữC# hội đủ những điều kiện như vậy, hơn nữa nó được xây dựng trên nềntảng của hai ngôn ngữ mạnh nhất là C++ và Java.Ngôn ngữ C# được phát triển bởi đội ngũ kỹ sư của Microsoft, trongđó người dẫn đầu là Anders Hejlsberg và Scott Wiltamuth. Cả hai người nàyđều là những người nổi tiếng, trong đó Anders Hejlsberg được biết đến làtác giả của Turbo Pascal, một ngôn ngữ lập trình PC phổ biến. Và ông đứngđầu nhóm thiết kế Borland Delphi, một trong những thành công đầu tiên củaviệc xây dựng môi trường phát triển tích hợp (IDE) cho lập trình client/server.Phần cốt lõi hay của bất cứ ngôn ngữ lập trình hướng đối tượng là sự hỗtrợ của nó cho việc định nghĩa và làm việc với những lớp. Những lớp thìđịnh nghĩa những kiểu dữ liệu mới, cho phép người phát triển mở rộng ngônngữ để tạo mô hình tốt hơn để giải quyết vấn đề. Ngôn ngữ C# chứa nhữngtừ khóa cho việc khai báo những kiểu lớp đối tượng mới và những phươngthức hay thuộc tính của lớp, và cho việc thực thi đóng gói, kế thừa, và đa hình,ba thuộc tính cơ bản của bất cứ ngôn ngữ lập trình hướng đối tượng.Trong ngôn ngữ C# mọi thứ liên quan đến khai báo lớp đều đượctìm thấy trong phần khai báo của nó. Định nghĩa một lớp trong ngôn ngữC# không đòi hỏi phải chia ra tập tin header và tập tin nguồn giống nhưtrong ngôn ngữ C++. Hơn thế nữa, ngôn ngữ C# hỗ trợ kiểu XML, chophép chèn các tag XML để phát sinh tự động các document cho lớp.8C# cũng hỗ trợ giao diện interface, nó được xem như một cam kết với mộtlớp cho những dịch vụ mà giao diện quy định. Trong ngôn ngữ C#, một lớp chỉcó thể kế thừa từ duy nhất một lớp cha, tức là không cho đa kế thừa như trongngôn ngữ C++, tuy nhiên một lớp có thể thực thi nhiều giao diện. Khi một lớpthực thi một giao diện thì nó sẽ hứa là nó sẽ cung cấp chức năng thực thi giaodiện.Trong ngôn ngữ C#, những cấu trúc cũng được hỗ trợ, nhưng khái niệmvề ngữ nghĩa của nó thay đổi khác với C++. Trong C#, một cấu trúc được giớihạn, là kiểu dữ liệu nhỏ gọn, và khi tạo thể hiện thì nó yêu cầu ít hơn về hệđiều hành và bộ nhớ so với một lớp. Một cấu trúc thì không thể kế thừa từmột lớp hay được kế thừa nhưng một cấu trúc có thể thực thi một giao diện.Ngôn ngữ C# cung cấp những đặc tính hướng thành phần(component-oriented), như là những thuộc tính, những sự kiện. Lập trìnhhướng thành phần được hỗ trợ bởi CLR cho phép lưu trữ metadata với mãnguồn cho một lớp. Metadata mô tả cho một lớp, bao gồm những phươngthức và những thuộc tính của nó, cũng như những sự bảo mật cần thiết vànhững thuộc tính khác. Mã nguồn chứa đựng những logic cần thiết để thựchiện những chức năng của nó. Do vậy, một lớp được biên dịch như là mộtkhối self-contained, nên môi trường hosting biết được cách đọc metadata củamột lớp và mã nguồn cần thiết mà không cần những thông tin khác để sửdụng nó.Ngôn ngữ C# cũng hỗ trợ việc truy cập bộ nhớ trực tiếp sử dụng kiểucon trỏ của C++ và từ khóa cho dấu ngoặc [] trong toán tử. Các mã nguồnnày là không an toàn (unsafe). Và bộ giải phóng bộ nhớ tự động của CLRsẽ không thực hiện việc giải phóng những đối tượng được tham chiếu bằng sửdụng con trỏ cho đến khi chúng được giải phóng.91.2. Lịch sử phát triển của trí tuệ nhân tạoLịch sử của trí tuệ nhân tạo cho thấy ngành khoa học này có nhiều kếtquả đáng ghi nhận. Theo các mốc phát triển, người ta thấy trí tuệ nhân tạođược sinh ra từ những năm 50 với các sự kiện sau:- Turing được coi là người khai sinh ngành trí tuệ nhân tạo bởi pháthiện của ông về máy tính có thể lưu trữ chương trình và dữ liệu.- Tháng 8/1956 J. Mc Carthy, M. Minsky, A. Newell, Shannon. Simon,… đưa ra khái niệm “trí tuệ nhân tạo”.- Vào khoảng năm 1960 tại Đại học MIT (Massachussets Institure ofTechnology) ngôn ngữ LISP ra đời, phù hợp với các nhu cầu xử lý đặc trưngcủa trí tuệ nhân tạo - đó là ngôn ngữ lập trình đầu tiên dùng cho trí tuệ nhântạo.- Thuật ngữ trí tuệ nhân tạo được dùng đầu tiên vào năm 1961 cũng tại MIT.- Những năm 60 là giai đoạn lạc quan cao độ về khả năng làm cho máytính biết suy nghĩ. Trong giai đoạn này người ta đã được chứng kiến máy chơicờ đầu tiên và các chương trình chứng minh định lý tự động. Cụ thể:+ 1961: Chương trình tính tích phân bất định+ 1963: Các chương trình Heuristics: Chương trình chứng minh cácđịnh lý hình học không gian có tên là “tương tự”, chương trình chơi cờ củaSamuel, tìm kiếm đường đi có giá thành cực tiểu.+1964: Chương trình giải phương trình đại số sơ cấp, chương trình trợgiúp ELIZA (có khả năng làm việc giống như một chuyên gia phân tích tâm lý).+ 1966: Chương trình phân tích và tổng hợp tiếng nói.+ 1968: Chương trình điều khiển người máy (Robot) theo đồ án “Mát –tay”, chương trình học nói.- Vào những năm 60, do giới hạn khả năng của các thiết bị, bộ nhớ vàđặc biệt là yếu tố thời gian thực hiện nên có sự khó khăn trong việc tổng quáthoá các kết quả cụ thể vào trong một chương trình mềm dẻo thông minh.10- Vào những năm 70, máy tính với bộ nhớ lớn và tốc độ tính toán nhanhnhưng các phương pháp tiếp cận trí tuệ nhân tạo cũ vẫn thất bại (do sự bùngnổ tổ hợp trong quá trình tìm kiếm lời giải các bài toán đặt ra).- Vào cuối những năm 70 một vài kết quả như xử lý ngôn ngữ tự nhiên,biểu diễn tri thức và giải quyết vấn đề. Những kết quả đó đã tạo điều kiện chosản phẩm thương mại đầu tiên của trí tuệ nhân tạo ra đời đó là hệ chuyên gia,được đem áp dụng trong các lĩnh vực khác nhau (hệ chuyên gia là một phầnmềm máy tính chứa các thông tin và tri thức về một lĩnh vực cụ thể nào đó, cókhả năng giải quyết những yêu cầu của người sử dụng trong một mức độ nào đó,ở một trình độ như một chuyên gia con người có kinh nghiệm khá lâu năm).- Một sự kiện quan trọng vào những năm 70 là sự ra đời ngôn ngữProlog, tương tự LISP nhưng nó có cơ sở dữ liệu đi kèm.- Vào những năm 80, thị trường các sản phẩm dân dụng đã có khánhiều sản phẩm ở trình đô cao như: máy giặt, máy ảnh,... sử dụng trí tuệ nhântạo. Các hệ thống nhận dạng và xử lý ảnh, tiếng nói.- Những năm 90, các nghiên cứu nhằm vào cài đặt thành phần thông minhtrong các hệ thống thông tin, gọi chung là cài đặt trí tuệ nhân tạo, làm rõ hơn cácngành của khoa học trí tuệ nhân tạo và tiến hành các nghiên cứu mới, đặc biệt lànghiên cứu về cơ chế suy lý, về trí tuệ nhân tạo phân tạo, về các mô hình tương tác.1.3. Tổng quan về khoa học trí tuệ nhân tạoTrong công nghệ thông tin, trí tuệ nhân tạo (Artificial Intelligence) làmột ngành mới, nhưng phát triển rất mạnh mẽ và đem lại nhiều kết quả to lớn.Con người thường tự cho mình là sinh vật thông minh vì khả năng trí tuệđóng vai trò quan trọng trong cuộc sống. Trong văn học cũng đã từng cónhững câu chuyện đề cao về trí thông minh của con người.Trí tuệ nhân tạo chỉ mới hình thành từ năm 1956. Tuy nhiên, việcnghiên cứu trí tuệ đã có từ lâu. Trên 2000 năm trước, các nhà triết học đã tìmhiểu về cách thức nhìn nhận, học tập, nhớ và suy lý. Việc ra đời của máy tính11điện tử vào những năm 50 của thế kỷ 20 đã sinh ra khuynh hướng đưa cáclĩnh vực nghiên cứu trí tuệ về các vấn đề lý thuyết và thực nghiệm trên máy.1.4. Các khái niệm cơ bảnTrí tuệ con người (Human Intelligence): Cho đến nay chưa có mộtđịnh nghĩa chính xác về trí tuệ con người và đã có rất nhiều quan điểm khácnhau. Sau đây là một số quan điểm:- Năm 1950, Alan Turing đã đưa ra các “trắc nghiệm thông minh” để nhậnbiết máy tính có thông minh hay không. Tuy vậy, theo ông tuy máy tính có thểthất bại trong các trắc nghiệm thông minh nhưng nó vẫn có thể thông minh.- Theo quan điểm của Minsky, trí tuệ nhân tạo là một ngành khoa họcnhằm nghiên cứu, mô phỏng trên máy tính các hành vi và tư duy thông minhtương tự như con người. Nó giúp máy tính có khả năng nhận thức, suy luận vàphản ứng. Có hai hướng tiếp cận trí tuệ nhân tạo:+ Dùng máy tính để làm theo quá trình xử lý của con người.+ Thiết kế những máy tính thông minh độc lập với cách suy nghĩ củacon người.- Khái niệm trí tuệ theo quan điểm của Turing: Trí tuệ là những gì cóthể đánh giá được thông qua các trắc nghiệm thông minh.- Theo từ điển bách khoa toàn thư Webstes định nghĩa. Trí tuệ là khả năng:+ Phản ứng một cách thích hợp những tình huống mới thông qua hiệuchỉnh hành vi một cách thích đáng.+ Hiểu rõ những mối liên hệ qua lại của các sự kiện của thế giới bênngoài nhằm đưa ra những hành động phù hợp đạt tới một mục đích nào đó.- Theo nhữngnhà tâm lý học nhận thức thì quá trình hoạt động trí tuệcủa con người bao gồm 4 thao tác cơ bản:+ Xác định tập đích (goals) cần đạt tới.+ Thu thập các sự kiện (facts) và các luật suy diễn (inference rules) đểđạt tới tập đích đặt ra.12+ Thu gọn (pruning) quá trình suy luận nhằm xác định một cách nhanhchóng tập các suy diễn có thể sử dụng được để đạt tới một đích chung nào đó.+ Áp dụng các cơ chế suy diễn (tiến hoặc lùi) cụ thể (inferencemechanisms) dựa trên các thao tác thu gọn quá trình suy luận và những sựkiện trung gian mới được tạo ra, để dẫn dắt từ những sự kiện ban đầu đếnnhững đích đã đặt ra.Trí tuệ máy: Cho đến nay cũng không có một định nghĩa chính xác nàođược đưa ra để định nghĩa về trí tuệ máy, chỉ có một vài dấu hiệu quan trọngcủa trí tuệ máy:- Trí tuệ máy là khả năng học.- Khả năng mô phỏng các hành vi sáng tạo của con người.- Khả năng trừu tượng hoá, tổng quát hoá và suy diễn .- Khả năng tự giải thích hành vi.- Khả năng thích nghi tình huống mới gồm khả năng thu nạp dữ liệutích hợp, rút tri thức từ dữ liệu.- Khả năng xử lý các biểu diễn hình thức như (các kí hiệu tượng trưng,danh sách).- Khả năng vận dụng các tri thức heuristic sẵn có.- Khả năng xử lý các thông tin bất định, không đầy đủ, không chính xác...Như vậy trí tuệ máy khác trí tuệ người ở chỗ nó không thể nhìn đượcmột phần hay toàn thể quá trình giải bài toán trong những tình huống mới vàkhông tự sinh ra được các heuristics.1.5. Vai trò của trí tuệ nhân tạoTrí tuệ nhân tạo bao quát rất nhiều lĩnh vực nghiên cứu hẹp. Nó nghiêncứu từ các lĩnh vực tổng quát như máy nhận biết, suy luận logic, đến các bàitoán như chơi cờ, chứng minh định lý, tìm kếm đường đi. Thường thì các nhàkhoa học ở các lĩnh vực khác tìm đến với trí tuệ nhân tạo ở các kỹ thuật hệ13thống hoá và tự động hoá các xử lý tri thức cũng như các phương pháp thuộclĩnh vực mang tính người.Trí tuệ nhân tạo nghiên cứu kỹ thuật làm cho máy tính có thể “suy nghĩmột cách thông minh” và mô phỏng quá trình suy nghĩ của con người khi đưara những quyết định, lời giải. Trên cơ sở đó, thiết kế các chương trình chomáy tính để giải quyết bài toán.Sự ra đời và phát triển của trí tuệ nhân tạo đã tạo ra một bước nhảy vọt vềchất trong kỹ thuật và kỹ nghệ xử lý thông tin. Trí tuệ nhân tạo chính là cơ sởcủa công nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyềnthống dựa trên văn bản giấy tờ. Điều này được thể hiện qua các mặt sau:- Nhờ những công cụ hình thức hoá (các mô hình logic ngôn ngữ, logicmờ,...), các tri thức thủ tục và tri thức mô tả có thể biểu diễn được trong máy.Do vậy quá trình giải bài toán được tiến hành hữu hiệu hơn.- Mô hình logic ngôn ngữ đã mở rộng khả năng ứng dụng của máy tínhtrong lĩnh vực đòi hỏi tri thức chuyên gia ở trình độ cao, rất khó như: Y học,sinh học, địa lý, tự động hóa.- Một số phần mềm trí tuệ nhân tạo thể hiện tính thích nghi và tínhmềm dẻo đối với các lớp bài toán thuộc nhiều lĩnh vực khác nhau.- Khi máy tính được trang bị các phần mềm trí tuệ nhân tạo ghép mạngsẽ cho phép giải quyết những bài toán cỡ lớn và phân tán.1.6. Các kỹ thuật trí tuệ nhân tạoCó nhiều kỹ thuật nghiên cứu, phát triển ngành khoa học trí tuệ nhântạo. Tuy vậy, các kỹ thuật trí tuệ nhân tạo thường khá phức tạp khi cài đặt cụthể, lý do là các kỹ thuật này thiên về xử lý các ký hiệu tượng trưng và đòi hỏiphải sử dụng những tri thức chuyên môn thuộc nhiều lĩnh vực khác nhau.Do vậy, các kỹ thuật trí tuệ nhân tạo hướng tới khai thác những tri thứcvề lĩnh vực đang quan tâm được mã hoá trong máy sao cho đạt được mức độtổng quát, dễ hiểu, dễ diễn đạt thông qua ngôn ngữ chuyên môn gần gũi với14ngôn ngữ tự nhiên, dễ sửa đổi, hiệu chỉnh, dễ sử dụng, khai thác nhằm thu hẹpcác khả năng cần xét để đi tới lời giải cuối cùng.Các kỹ thuật trí tuệ nhân tạo cơ bản bao gồm:- Lý thuyết giải bài toán và suy diễn thông minh: Lý thuyết giải bàitoán cho phép viết các chương trình giải câu đố, chơi các trò chơi thông quacác suy luận mang tính người, các hệ thống chứng minh định lý. Ngoài ra cáchệ thống hỏi đáp thông minh còn cho phép lưu trữ và xử lý khối lượng lớn cácthông tin.- Lý thuyết tìm kiếm may rủi: Lý thuyết này bao gồm các phươngpháp và kỹ thuật tìm kiếm với sự hỗ trợ của thông tin phụ để giải bài toán mộtcách có hiệu quả.- Các ngôn ngữ về trí tuệ nhân tạo: Để xử lý các tri thức không chỉ sửdụng các ngôn ngữ lập trình dùng cho các xử lý dữ liệu số, mà cần có ngônngữ khác. Các ngôn ngữ chuyên dụng này cho phép lưu trữ và xử lý thông tinký hiệu. Một số ngôn ngữ được nhiều người biết đến là IPL.V,LISP,PROLOG.- Lý thuyết thể hiện tri thức và hệ chuyên gia: Trí tuệ nhân tạo làkhoa học về thể hiện và sử dụng tri thức. Mạng ngữ nghĩa, lược đồ, logic vịtừ, khung là các phương pháp thể hiện tri thức thông dụng. Việc gắn liền cáchthể hiện và sử dụng tri thức là cơ sở hình thành hệ chuyên gia.- Lý thuyết nhận dạng và xử lý tiếng nói: Giai đoạn phát triển đầucủa trí tuệ nhân tạo gắn với lý thuyết nhận dạng. Các phương pháp nhận dạngchính gồm: nhận dạng hình học, nhận dạng dùng tâm lý học, nhận dạng theophương pháp hàm thế, dùng máy nhận dạng. Ứng dụng của phương pháp nàytrong việc nhận dạng chữ viết, âm thanh.- Người máy: Cuối những năm 70, người máy trong công nghiệp đãđạt được nhiều tiến bộ. Người máy có bộ phận cảm nhận và các cơ chế hoạt15động được nối ghép theo sự điều khiển thông minh. Khoa học về cơ học và trítuệ nhân tạo được tích hợp trong khoa học người máy.- Tâm lý học xử lý thông tin: Các kết quả nghiên cứu của tâm lý họcgiúp Trí tuệ nhân tạo xây dựng các cơ chế trả lời theo hành vi, có ý thức. Giúpcho việc thực hiện các suy diễn mang tính người.- Ngoài ra, xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui vàxử lý cú pháp hình thức là những kỹ thuật cơ bản của tin học truyền thốngcó liên quan trực tiếp đến trí tuệ nhân tạo.1.7. Một số vấn đề trí tuệ nhân tạo quan tâmKhoa học trí tuệ nhân tạo liên quan đến cảm giác, tri giác và cả quátrình tư duy thông qua các hành vi, giao tiếp. Trí tuệ nhân tạo có các địnhhướng nghiên cứu, ứng dụng sau:- Tìm và nghiên cứu các thủ tục giúp con người tiến hành các hoạt độngsáng tạo. Công việc sáng tạo được thực hiện trên mô hình theo cấu trúc, chứcnăng và sử dụng công nghệ thông tin.- Dùng ngôn ngữ tự nhiên. Trước hết là ngôn ngữ được dùng để thểhiện tri thức, tiếp thu và chuyển hoá sang dạng có thể xử lý được.- Hình thức hoá các khía cạnh, các hành vi liên quan đến trí tuệ nhântạo. Do vậy có thể xây dựng các bài toán mang tính người và thông minh.Các hoạt động lớn trong trí tuệ nhân tạo bao gồm: chứng minh định lý,xử lý ngôn ngữ tự nhiên, hiểu tiếng nói, phân tích ảnh và hình, người máy vàhệ chuyên gia. Về cài đặt hệ thống, khuynh hướng hiện tại của trí tuệ nhân tạolà cài đặt các hệ trí tuệ nhân tạo trong các hệ thống khác, đặc biệt là trong cáchệ thống tin học.Những vấn đề chưa được giải quyết trong trí tuệ nhân tạoNhững thành tựu nghiên cứu và ứng dụng các kỹ thuật trí tuệ nhân tạođã khẳng định tính thực tiễn của các dự án xây dựng máy tính có khả năng16suy nghĩ. Tuy vậy trong một số phạm vi, máy tính còn thua xa so với hoạtđộng của hệ thần kinh con người.Sự khác nhau trong hoạt động giữa máy tính và bộ não con người, điềunày thể hiện ưu thế của máy tính so với bộ não người vì khả năng tính toán rấtlớn (nhất là trong các chương trình xử lý dữ liệu lớn).Xử lý song song: Mặc dù công nghệ điện tử hiện đại cho phép xâydựng các bộ đa xử lý, song máy tính không thể hoạt động song song như bộnão con người được.Khả năng diễn giải: Con người có thể xem xét cùng một vấn đề theonhững phương pháp khác nhau, từ đó diễn giải theo cách dễ hiểu nhất. Ngược lại,sự linh hoạt này không thể mô phỏng được trong các hệ thống trí tuệ nhân tạo.Lôgic rời rạc và tính liên tục: Một thách đố lớn với các hệ thống trí tuệnhân tạo là khả năng kết hợp các phương pháp xử lý thông tin trong môitrường liên tục với các thao tác xử lý thông tin rời rạc.Khả năng học: Mặc dù hiện nay máy tính có nhiều tính năng caonhưng cũng không thể mô phỏng được hoàn toàn khả năng học giống bộ nãocon người.Khả năng tự tổ chức: Cho tới nay, người ta chưa thể tạo lập được cáchệ thống trí tuệ nhân tạo có khả năng tự tổ chức, tự điều khiển hoạt động củanó để thích nghi với môi trường.Những vấn đề đặt ra trong tương lai của trí tuệ nhân tạo.Trong tương lai, những nghiên cứu và ứng dụng của trí tuệ nhân tạo tậptrung vào các vấn đề lớn sau:- Nghiên cứu và thử nghiệm các mạng Neuron, các hệ thống trí tuệnhân tạo mô phỏng chức năng hoạt động của bộ não với các khả năng học, tựtổ chức, tự thích nghi, tổng quát hoá, xử lý song song, có khả năng diễn giải,xử lý thông tin liên tục và rời rạc.17- Nghiên cứu và tạo lập các hệ thống có giao tiếp thân thiện giữa ngườivà máy trên cơ sở nghiên cứu nhận thức máy, thu thập và xử lý tri thức, xử lýthông tin hình ảnh, tiếng nói.- Nghiên cứu các phương pháp biểu diễn tri thức và các phương phápsuy diễn thông minh, các phương pháp giải quyết vấn đề đối với những bàitoán phụ thuộc không gian, thời gian.Ngày nay, thế giới đang chuyển mình trong những nghiên cứu về trí tuệnhân tạo. Chắc chắn rằng máy tính với trí tuệ như con người sẽ tác động mạnhđến cuộc sống xã hội.18CHƯƠNG 2: LÝ THUYẾT ĐỒ THỊ VÀ MỘT SỐTHUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT2.1. Lý thuyết đồ thị2.1.1. Định nghĩa đồ thịĐồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối cácđỉnh này. Phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nốihai đỉnh nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến cácloại đồ thị khác nhau, ví dụ sử dụng chúng để mô tả một mạng máy tính. Giảsử có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là tên thoại)nối các máy tính này, có thể biểu diễn các vị trí đặt máy tính bởi các điểm vàcác kênh thoại nối chúng bởi các đoạn nối, xem hình 1Hà TâyĐồng NaiHà NộiQuãng NgãiHuếAn GiangTPHCMPhú YênBình ĐịnhKhánh HòaHình 2.1: Sơ đồ mạng máy tínhNhận thấy rằng trong mạng hình 1, giữa hai máy tính bất kỳ chỉ chophép nhiều nhất là một kênh thoại nối chúng, kênh thoại này cho phép liên lạccả hai chiều và không có máy tính nào lại được nối với chính nó. Sơ đồ mạngmáy tính cho trong hình 1 được gọi là đơn đồ thị vô hướng => đi đến địnhnghĩa sau:Định nghĩa 1. Đơn đồ thị vô hướng G=(V,E) bao gồm V là tập đỉnh, và Elà tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.19Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyềntải nhiều thông tin, phải nối hai máy này bởi nhiều kênh thoại. Mạng với đakênh thoại giữa các máy tính được cho trong hình 2.Hà TâyĐồng NaiHà NộiHuếHCMAn GiangBình ĐịnhQuãng NgãiPhú YênKhánh HòaHình 2.2: Sơ đồ mạng máy tính với đa kênh thoạiĐịnh nghĩa 2. Đa đồ thị vô hướng G= (V, E) bao gồm V là tập cácđỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của Vgọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tươngứng với một cặp đỉnh.Hà TâyĐồng NaiHà NộiQuãng NgãiHuếAn GiangTPHCMBình ĐịnhPhú YênKhánh HòaHình 2.3: Sơ đồ mạng máy tính với kênh thông báoRõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thịnào cũng là đơn đồ thị, vì trong đa đồ thị có hai hay nhiều hơn cạnh nối mộtcặp đỉnh nào đó.20Trong mạng máy tính có thể có những kênh thoại nối một máy tính nàođó với chính nó (chẳng hạn với mục đích thông báo), mạng như vậy được chotrong hình 3. Như vậy đa đồ thị không thể mô tả được mạng như vậy, bởi vì cónhững khuyên (cạnh nối một đỉnh với chính nó). Trong trường hợp này chúng tacần sử dụng đến khái niệm giả đồ thị vô hướng, được định nghĩa như sau:Định nghĩa 3. Giả đồ thị vô hướng G= (V, E) bao gồm V là tập cácđỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử (không nhất thiếtphải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyến nếu códạng e= (u, u).Các kênh thoại trong mạng máy tính có thể chỉ cho phép truyền tin theomột chiều. Chẳng hạn trong hình 4 máy chủ ở Hà Nội chỉ có thể nhận tin từcác máy ở địa phương, có một số máy chỉ có thể gửi tin đi, còn các kênh thoạicho phép truyền tin theo cả hai chiều được thay thế bởi hai cạnh có hướngngược chiều nhau.Hà TâyĐồng NaiHà NộiHuếAn GiangTPHCMBình ĐịnhPhú YênKhánh HòaHình 2.4: Mạng máy tính với các kênh thoại một chiềuĐịnh nghĩa 4. Đơn đồ thị có hướng G= (V,E) bao gồm V là tập cácđỉnh và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi làcác cung.21Nếu trong mạng có thể có đa kênh thoại một chiều, khi đó sẽ phải sửdụng đến khái niệm đa đồ thị có hướng:Định nghĩa 5. Đa đồ thị có hướngG= (V,E) bao gồm V là tập các đỉnhvà E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung.Hai cung e1 và e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.2.1.2. Định nghĩa đường đi, chu trình, đồ thị liên thông.Định nghĩa 6. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là sốnguyên dương, trên đồ thị vô hướng G= (V,E) là dãy xo, x1 , ... , xn-1 , xntrong đó u=x0 , v=xn , ( xi , xi+1 )  E , i= 0, 1, 2 ,..., n-1.Đường đi nói trên còn có thể biểu diễn dưới dạng các cạnh: (x0 , x1 ) , (x1 , x2), ... , ( xn-1 , xn ).Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi.Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình.Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩahoàn toàn tương tự như trường hợp đồ thị vô hướng, chỉ khác là ta chú ý đếnhướng trên các cung.Định nghĩa 7. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là sốnguyên dương, trên đồ thị có hướng G= (V,A) là dãy xo, x1 , ... , xn-1 , xntrong đó u=x0 , v=xn , ( xi , xi+1 )  A , i= 0, 1, 2 ,..., n-1.Đường đi nói trên còn có thể biểu diễn dưới dạng các cung:(x0 , x1 ) , ( x1 , x2), ... , ( xn-1 , xn ).Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi.Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình.Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại.Định nghĩa 8. Đồ thị vô hướng G= (V,E) được gọi là liên thông nếuluôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.22Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin đượcvới nhau khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.Định nghĩa 9. Ta gọi đồ thị con của đồ thị G= (V,E) là đồ thịH=(W,F), trong đó W  V và F  ETrong trường hợp đồ thị là không liên thông, nó sẽ rẽ ra thành một sốđồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liênthông như vậy gọi là các thành phần liên thông của đồ thị.Định nghĩa 10. Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ vcùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liênthông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làmtăng số thành phần liên thông của đồ thị.Định nghĩa 11. Đồ thị có hướng G= (V,A) được gọi là liên thôngmạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.Định nghĩa 12. Đồ thị có hướng G=(V,A) được gọi là liên thông yếunếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông.Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu,nhưng điều ngược lại là không luôn đúng.Một câu hỏi đặt ra là khi nào có thể định hướng các cạnh của một đồ thịvô hướng liên thông để có thể thu được một đồ thị có hướng liên thông mạnh?Ta sẽ gọi đồ thị như vậy là đồ thị định hướng được. Định lý dưới đây sẽ chỉ ratiêu chuẩn nhận biết một đồ thị có là định hướng được hay không.Định lý 1. Đồ thị vô hướng liên thông là định hướng được khi và chỉkhi mỗi cạnh của nó nằm trên ít nhất một chu trình.Chứng minh: Điều kiện cần, giả sử (u,v) là một cạnh của đồ thị, từ sựtồn tại đường đi có hướng từ u đến v và ngược lại suy ra (u,v) phải nằm trên ítnhất một chu trình.Điều kiện đủ, thủ tục sau đây cho phép định hướng các cạnh của đồ thịđể thu được đồ thị có hướng liên thông mạnh. Giả sử C là một chu trình nào23đó trong đồ thị. Định hướng các cạnh trên chu trình này theo một hướng đivòng theo nó. Nếu tất các cạnh của đồ thị là đã được định hướng thì kết thúcthủ tục. Ngược lại, C là một cạnh chưa định hướng có chung đỉnh với ít nhấtmột trong số các cạnh đã định hướng. Theo giả thiết tìm được chu trình Cchứa cạnh e. Định hướng các cạnh chưa được định hướng của C’ theo mộthướng dọc theo chu trình này (không định hướng lại các cạnh đã có hướng).Thủ tục trên sẽ được lặp lại cho đến khi tất cả các cạnh của đồ thị được địnhhướng. Khi đó thu được đồ thị có hướng liên thông mạnh.2.2. Một số khái niệm2.2.1. Mở đầuTrong phần này chỉ xét đồ thị có hướng G=(V,E) và |V|=n, |E|=m vớicác cung được gán trọng số, nghĩa là, mỗi cung (u,v)  E được đặt tương ứngvới một số thực a(u,v) gọi là trọng số của nó. Đặt a(u,v)=∞, nếu (u,v)  E. Khiđó dãy v0, v1 , ... , vp là một đường đi trên G, thì độ dài của nó được địnhnghĩa là tổng sau:p a vi 1, vi i 1tức là, độ dài của đường đi chính là tổng các trọng số trên các cung của nó.(Chú ý rằng nếu gán trọng số cho tất cả các cung đều bằng 1, sẽ thu được địnhnghĩa độ dài đuờng đi như là số cung của đường đi).Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thểđược phát biểu dưới dạng tổng quát như sau: Tìm đường đi có độ dài nhỏ nhấttừ một đỉnh xuất phát s  V đến đỉnh cuối (đích) t  V. Đường đi như vậy sẽ gọilà đường đi ngắn nhất từ s đến t còn độ dài của nó sẽ kí hiệu là d(s,t) và còngọi là khoảng cách từ s đến t (khoảng cách định nghĩa như vậy có thể là sốâm). Nếu như không tồn tại đường đi từ s đến t thì ta đặt d(s,t)=∞ từ đó tathấy chu trình trong đồ thị có độ dài dương, thì trong đường đi ngắn nhấtkhông có đỉnh nào lặp lại (đường đi như thế gọi là đường đi cơ bản).24Mặt khác, nếu trong đồ thị có chu trình với độ dài âm (gọi là chu trìnhâm) thì khoảng cách giữa 1 số cặp đỉnh nào đó của đồ thị có thể là không xácđịnh, bởi vì, bằng cách đi vòng theo chu trình này một số đủ lớn lần, ta có thểchỉ ra đường đi giữa các đỉnh này có độ dài nhỏ hơn bất kì số thực cho trướcnào. Trong truờng hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản ngắnnhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất nhiều, bởi vì nóchứa bài toán xét sự tồn tại đường đi Hamintơn trong đồ thị như là một trườnghợp riêng.Trước hết cần chú ý rằng nếu biết khoảng cách từ s đến t, thì đường đingắn nhất từ s đến t, trong trường hợp trọng số không âm, có thể tìm mộtcách dễ dàng. Để tìm đường đi, chỉ cần chú ý là đối với cặp đỉnh s,t  V tuỳ ý(s  t) luôn tìm được đỉnh v sao cho:d(s,t) = d(s,v) + a(v,t)Thực vậy, đỉnh v như vậy chính là đỉnh đi trước đỉnh t trong đường đingắn nhất từ s đến t. Tiếp theo có thể tìm được u sao chod(s,v)=d(s,u)+a(u,v),... Từ giả thiết về tính không âm của các trọng số dễdàng suy ra rằng dãy t, v, u... Không chứa đỉnh lặp lại và kết thúc ở đỉnh s. Rõràng dãy thu được xác định đường đi ngắn nhất từ s đến t.2.2.2. Giải quyết vấn đề bằng phương pháp tìm kiếmTìm kiếm là một trong những hướng nghiên cứu quan trọng trong trítuệ nhân tạo. Mục đích của trí tuệ nhân tạo là tìm cách giải quyết vấn đề haybài toán một cách hợp lý, trong khi đó một lớp lớn các bài toán có thể phátbiểu và giải quyết dưới dạng tìm kiếm. Sau đây là một số các bài toán:- Trò chơi: Nhiều trò chơi, ví dụ như cờ vua hay Pikachu thực chất làquá trình tìm kiếm nước đi bên trong số mà luật chơi cho phép.- Tìm đường đi: Trong số những đường đi, lựa chọn đường đi tới đích,có thể thỏa mãn một số tiêu chí nào đó như tiêu chí tối ưu về độ dài, thời gian,giá thành...25

Trích đoạn

Cấu trúc game Pikachu
Một số giao diện và kết quả chạy chương trình

Tài liệu liên quan

Lý thuyết về thuật toán tìm đường đi ngắn nhất
- 25
- 2
- 5
Song song hoá thuật toán tìm đường đi ngắn nhất trên nguồn dữ liệu lớn dùng MPI luận văn thạc sĩ
- 53
- 1
- 2
đề tài CÀI đặt THUẬT TOÁN tìm ĐƯỜNG đi NGẮN NHẤT TRONG đồ THỊ
- 40
- 5
- 25
đồ án cơ sở thuật toán tìm đường đi ngắn nhất trong lý thuyết đồ thị vuson.tk
- 27
- 1
- 1
Thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng ( Khóa luận tốt nghiệp )
- 54
- 1
- 11
Một số thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng GAME PIKACHU
- 50
- 2
- 5
Một số thuật toán trong trò chơi đối kháng và xây dựng game cờ caro
- 57
- 966
- 1
thuật toán tìm đường đi ngắn nhất
- 26
- 608
- 1
Ứng dụng Maple cài đặt thuật toán tìm đường đi ngắn nhất Dijkstra
- 10
- 1
- 4
Tiểu luận môn học THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
- 19
- 1
- 0