intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Đề tài: Trí tuệ nhân tạo trong xây dựng Games

Chia sẻ: Nguyễn Thị Hồng Ngọc | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
309
lượt xem 70
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

MỤC LỤC Chương 1 GIỚI THIỆU . 1 1. Lý do chọn đề tài . 1 1.1. Các ngôn ngữ lập trình game 1 1.2. Phân loại game 2 1.2.1. Game hành động . 2 1.2.2. Game nhập vai 3 1.2.3. Game đua xe . 3

Chủ đề:

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

Lưu

Nội dung Text: Đề tài: Trí tuệ nhân tạo trong xây dựng Games

  1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC NGUYỄN THANH PHONG ỨNG DỤNG TRÍ TUỆ NHÂN TẠO TRONG XÂY DỰNG GAME KHÓA LUẬN CỬ NHÂN TIN HỌC TP. HCM, 2005
  2. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC NGUYỄN THANH PHONG - 0112191 ỨNG DỤNG TRÍ TUỆ NHÂN TẠO TRONG XÂY DỰNG GAME KHÓA LUẬN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN TH.S BÙI TIẾN LÊN NIÊN KHÓA 2001-2005
  3. NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ......................................................................................................
  4. NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ......................................................................................................
  5. LỜI CẢM ƠN Em sẽ không thể hoàn thành luận văn nếu không có sự hướng dẫn và chỉ bảo tận tình của thầy Bùi Tiến Lên. Em xin chân thành cảm ơn sự chỉ bảo của thầy. Em cũng rất cảm ơn các thầy cô trong khoa Công nghệ Thông tin trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, truyền đạt những kiến thức quý báu và tạo điều kiện cho em hoàn thành luận văn này. Xin chân thành cảm ơn sự giúp đỡ, động viên của của tất cả các bạn trong quá trình thực hiện luận văn. Em cũng muốn cảm ơn những người thân trong gia đình đã động viên, giúp đỡ và tạo điều kiện để hoàn thành luận văn. Mặc dù đã cố gắng hoàn thành luận văn với tất cả sự nổ lực của bản thân, nhưng luận văn chắc chắn không tránh khỏi những thiếu xót. Em rất mong nhận được sự thông cảm và chỉ bảo tận tình của các thầy cô và các bạn. Tp.HCM 7/2005 Sinh viên thực hiện Nguyễn Thanh Phong
  6. Mục lục MỤC LỤC Chương 1 GIỚI THIỆU ................................................................................... 1 1. Lý do chọn đề tài ....................................................................................... 1 1.1. Các ngôn ngữ lập trình game ............................................................ 1 1.2. Phân loại game .................................................................................. 2 1.2.1. Game hành động....................................................................... 2 1.2.2. Game nhập vai.......................................................................... 3 1.2.3. Game đua xe ............................................................................. 3 2. Mục đích của đề tài ................................................................................... 3 Chương 2 CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI ....................................... 4 1. Mô tả các thủ tục tìm kiếm rộng, sâu và sâu dần ...................................... 6 2. Thuật giải tìm đường đi có giá thành nhỏ nhất AT ................................... 7 3.Tìm kiếm với tri thức bổ sung .................................................................... 8 4.Tìm đường đi trên đồ thị tổng quát ............................................................ 9 Chương 3 GAME ENGINE ........................................................................... 12 I. WED editor: ................................................................................................... 13 1. Những khái niệm cơ bản ......................................................................... 13 a. Giao diện người dùng......................................................................... 13 b. Thanh Icon ......................................................................................... 15 c. Mode .................................................................................................. 15 d. Thiết kế một khung cảnh ................................................................... 14 e. Hướng đối tượng ................................................................................ 16 f. Cửa sổ dự án ....................................................................................... 18 2. Các lệnh trong WED ............................................................................... 19 2.1.Các lệnh trong các thực đơn ............................................................ 19 2.1.1. Thực đơn file .......................................................................... 20 2.1.2. Thực đơn edit: ........................................................................ 24 i
  7. Mục lục 2.1.3. Thực đơn mode ...................................................................... 25 2.1.4. Thực đơn Object ..................................................................... 29 2.1.5. Thực đơn Texture ................................................................... 32 2.1.5. Thực đơn View ....................................................................... 33 2.1.6. Thực đơn help ........................................................................ 34 2.2 Giao diện sử dụng ............................................................................ 35 2.3. Cửa sổ dự án ................................................................................... 36 2.3.1. Tab đối tượng ......................................................................... 36 2.3.2. Tab Views .............................................................................. 38 2.3.3. Tab Texture ............................................................................ 38 2.3.4. Tab Resource .......................................................................... 41 2.4. Cửa sổ Bookmark ........................................................................... 41 2.5. Thuộc tính của khối ........................................................................ 41 2.6. Thuộc tính của thực thể .................................................................. 43 3. Thiết kế một map ..................................................................................... 45 4. Thực thể ................................................................................................... 46 4.1. Thực thể mô hình ............................................................................ 46 4.2. Thực thể Sprite................................................................................ 47 4.3. Thực thể Map .................................................................................. 47 4.4. Thực thể Địa hình (terrain) ............................................................. 48 4.5. Bóng ................................................................................................ 48 4.5. Thuộc tính trong suốt ...................................................................... 49 II. CÁCH SỬ DỤNG MED .............................................................................. 50 1. Trình thiết kế ........................................................................................... 50 1.1. Các thực đơn ................................................................................... 50 1.1.1. Thực đơn File ......................................................................... 50 1.1.2. Thực đơn Edit ......................................................................... 53 1.1.3. Thực đơn View ....................................................................... 55 ii
  8. Mục lục 1.1.4. Thực đơn Options ................................................................... 56 1.1.5. Thực đơn Help........................................................................ 57 1.2. Toolbars ................................................................................................ 58 1.2.1. Toolbar File ............................................................................ 58 1.2.2. Toolbar Edit............................................................................ 58 1.2.3. Toolbar Select ........................................................................ 60 1.2.4. Toolbar Mesh ......................................................................... 60 1.2.5. Toolbar các đối tượng cơ sở ................................................... 61 1.2.6. Toolbar view .......................................................................... 62 1.2.7. Toolbar Frame ........................................................................ 63 1.2.8. Thanh trạng thái ..................................................................... 64 2.Trình thiết kế Skin .................................................................................... 64 2.1. Các thực đơn ................................................................................... 65 2.1.1. Thực đơn File ......................................................................... 65 2.1.2. Thực đơn Edit ......................................................................... 66 2.1.3. Thực đơn View ....................................................................... 67 2.2. Các Toolbar..................................................................................... 68 2.2.1. Toolbar Skin ........................................................................... 68 2.2.2. Toolbar Edit............................................................................ 68 2.2.3. Toolbar Paint .......................................................................... 69 III. SED, C-Script editor ................................................................................... 70 1. Giao diện sử dụng.................................................................................... 71 2. Soạn thảo ................................................................................................. 72 2.1. Lệnh Insert ...................................................................................... 72 2.2. Dòng chú thích ................................................................................ 72 2.3. Nhảy đến một đoạn mã ................................................................... 72 2.4. Sử dụng danh sách các thành phần ................................................. 73 2.5. Kiểm tra cú pháp ............................................................................. 73 iii
  9. Mục lục 2.6. Soạn thảo thông minh ..................................................................... 73 3. Cấu hình .................................................................................................. 74 4. Thực đơn.................................................................................................. 75 4.1. Thực đơn File .................................................................................. 75 4.2. Thực đơn Edit ................................................................................. 76 4.3. Thực đơn Options ........................................................................... 76 4.4. Thực đơn Tools ............................................................................... 77 4.5. Thực đơn Debug ............................................................................. 77 IV. Giao tiếp với các DLL ................................................................................ 79 1. Bắt đầu với SDK ..................................................................................... 79 2. Sử dụng đối tượng C-Script trong một DLL ........................................... 82 3. Sử dụng các hàm API .............................................................................. 83 4. Lập trình một game trong C++................................................................ 87 Chương 4 CÀI ĐẶT ........................................................................................ 89 I. Người chơi ..................................................................................................... 89 1. Chuyển động vật lý.................................................................................. 89 a. Gia tốc, quán tính và lực ma sát ......................................................... 89 b. Rơi từ trên xuống ............................................................................... 93 2. Cách di chuyển camera theo người chơi ................................................. 97 2.1. Tầm nhìn của người thứ nhất .......................................................... 97 2.2. Quay tự do tầm nhìn của người thứ 3 ........................................... 101 2.3. Cách để cho camera tránh chạm vào tường .................................. 106 II. Xe tự động .................................................................................................. 108 Tránh chướng ngại vật trên đường đi ........................................................ 108 iv
  10. Chương 1: Giới thiệu Chương 1 GIỚI THIỆU 1. Lý do chọn đề tài Ngày nay, do nhu cầu đời sống của con người ngày càng được nâng cao, trong đó nhu cầu giải trí của con người được quan tâm đến rất nhiều. Trong đó việc giải trí bằng Game máy tính ngày càng phát triển nhanh và lan rộng ra do sự lôi cuốn rất mạnh mẽ của nó. Hầu như ai đã sử dụng máy tính đều đã giải trí bằng một số game nào đó trên máy tính. Có thể nói Game là một thể loại phóng phú nhất trong tất cả các loại chương trình trên máy tính. Mặc dù các chương trình Game rất nhiều, nhưng để có thể viết ra được một game hay, có thể chơi được quả là một điều không dễ. Tuy vậy, với niềm đam mê về game máy tính, em cũng muốn tiếp cận với lĩnh vực này. 1.1. Các ngôn ngữ lập trình game Có rất nhiều chương trình hỗ trợ cho việc viết game: các ngôn ngữ lập trình như C++, Visual C++, Delphi, Dark Basic Pro, 3D Game Studio. Nhưng với các ngôn ngữ lập trình C++, Visual C++, DelPhi… có thể là những ngôn ngữ rất mạnh, có thể viết ra được những game có quy mô lớn. Đây là những ngôn ngữ lập trình có thể hoạt động trong nhiều lĩnh vực: với cơ sở dữ liệu, lập trình hệ thống, hoặc viết game…Do đó sự hỗ trợ của nó trong việc viết game là rất ít. Để có thể viết được một game bằng những ngôn ngữ lập trình này mà không sử dụng một thư viện nào, đòi hỏi phải bỏ ra rất nhiều công sức. Với engine Dark Basic Pro, đây là loại engine rất đơn giản và dễ sử dụng, là một ngôn ngữ Script theo họ Basic. Nó chỉ thích hợp với các game nhỏ. Tại sao lại sử dụng ngôn ngữ 3D Game Studio để viết game? 3D Game Studio là chương trình chuyên dụng dùng để tạo ra game 3D. 1
  11. Chương 1: Giới thiệu Với hàng trăm game đã được phát hành, 3D Game Studio xứng đáng là một ngôn ngữ lập trình game lớn. Với 3D Game Studio, chúng ta có thể: - Tạo ra một game đơn giản từ những script mẫu có sẵn. - Tạo ra các game thương mại viết bằng ngôn ngữ script. - Có thể sử dụng VisualC++ hoặc Delphi để kết hợp với 3D Game Studio để viết game. Có rất nhiều tài liệu hướng dẫn lập trình game bằng 3D Game Studio. Ngay cả với những người chưa có kiến thức về lập trình, nhưng nếu theo từng bước hướng dẫn tạo một game hành động đơn giản thì cũng có thể hoàn thành nó trong một thời gian ngắn. Theo Dr.Dobb's Journal: “Đây là bộ công cụ tuyệt vời để nhanh chóng tạo ra mẫu ban đầu và phát triển ứng dụng 3D”. Chúng ta có thể sử dụng ngôn ngữ script trong 3D Game Studio để viết và phân phối một game thương mại. Dưới đây là những game thương mại được làm bằng 3D Game Studio: 1.2. Phân loại game Thể loại của game thì rất phong phú và đa dạng, ở đây chúng ta chỉ xét các thể loại game thường thấy nhất là: 1.2.1. Game hành động Game hành động xuất hiện rất nhiều trong cả game 3D và game 2D. Game loại này có đặc điểm chúng là tính co giật trong game, như trong game bắn 2
  12. Chương 1: Giới thiệu súng. Game hành động thường đơn giản hơn tất cả các loại game khác bởi vì những người bình thường dễ dàng biết cách chơi và chơi hay game này . 1.2.2. Game nhập vai Game nhập vai thường có hai đặc trưng là: sự thay đổi, phát triển nhân vật và một câu chuyện mà trong đó nhân vật sẽ trải qua. 1.2.3. Game thể thao Game thể thao là sự thách thức cho các nhà thiết kế game. Không giống như hầu hết các thể loại game khác, người chơi biết rất ít về nó, trong game thể thao người chơi biết rất rõ vì nó mô phỏng một môn thể thao có sẵn trong thực tế. 1.2.3. Game đua xe Game đua xe tạo ra cảm giác giống như người chơi đang lái xe bên ngoài thế giới thực. Tuy trong đề tài của em không thể nói là viết ra được một game chơi được như một game đua xe, mà đây chỉ là một chương trình ở mức độ mô phỏng giao thông trên đường phố. 2. Mục đích của đề tài Tìm hiểu ngôn ngữ lập trình game trong 3D GameStudio: - Tìm hiểu về WED, một chương trình thiết kế khung cảnh trong game. - Tìm hiểu về MED, một chương trình thiết kế các mô hình trong game. - Tìm hiểu về SED, trình soạn thảo dùng để viết các câu lệnh script để kết nối các mô hình được tạo ra trong MED, các khung cảnh được tạo ra trong WED và sử dụng những hàm có sẵn trong SED hoặc trong các DLL khác để tạo ra một game. Sử dụng thuật toán cổ điển A* tìm kiếm đường đi để một đối tượng có thể chuyển động theo một hướng mong muốn nào đó. 3
  13. Chương 2: Các thuật toán tìm đường đi Chương 2 CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI Hầu hết các bài toán hoặc vấn đề đều có thể phát biểu dưới dạng “từ một trạng thái xuất phát hãy tìm đường dẫn đến một trạng thái kết thúc mong muốn” Việc tìm “đường dẫn” từ trạng thái xuất phát (S0) đến trạng thái kết thúc (Sn) gồm có một số bước sau đây: − Chọn không gian tìm kiếm thích hợp. − Tiến hành tìm kiếm có hệ thống và hiệu quả trong không gian tìm kiếm. − Sử dụng triệt để các nguồn tri thức liên quan trong quá trình tìm kiếm tương ứng với miền đối tượng cụ thể. Không gian tìm kiếm của một vấn đề cần giải trên máy tính thường được biểu diễn bằng đồ thị hay một dạng đặt biệt của đồ thị là cây. Đồ thị là một tập hợp giữa các đỉnh và các cung nối giữa các đỉnh. Các cung có thể được định hướng hoặc không định hướng, gán giá trị hoặc không gán giá trị. Cây là đồ thị định hướng đặt biệt có duy nhất một đỉnh mà không có cung nào hướng đến (gốc của cây), và mỗi đỉnh khác của cây chỉ có duy nhất một cung hướng đến. Sau khi bài toán hoặc vấn đề được biểu diễn lại dưới dạng đồ thị hoặc cây: − Mỗi đỉnh là một trạng thái của quá trình giải bài toán. − Mỗi cung là tác động biến đổi quá trình từ giai đoạn này sang giai đoạn khác. Như vậy, việc giải quyết một bài toán cũng chỉ là tìm đường đi từ trạng thái ban đầu đến trạng thái mong muốn được biểu diễn qua hai đỉnh nào đó của đồ 4
  14. Chương 2: Các thuật toán tìm đường đi thị hoặc cây tìm kiếm. Nhiều bài toán phức tạp nếu giải quyết bằng phương pháp tìm kiếm ngẫu nhiên thì hầu như vô vọng vì số đường đi có thể sẽ tăng lên theo hàm mũ của số đỉnh. Chính ở đây biểu lộ toàn bộ bản chất của trí tuệ nhân tạo khi giải quyết các vấn đề: Đó là nghệ thuật xử trí với các vấn đề lớn bằng cách giảm số lượng tìm kiếm. Các thủ tục tìm kiếm điển hình bao gồm: − Tìm kiếm rộng: đường đi được tìm theo mọi hướng có thể ở mỗi bước. − Tìm kiếm sâu: đường đi sâu mãi theo một hướng đến khi nào không tiếp tục được nữa mới chuyển sang hướng khác. − Tìm kiếm sâu dần: kết hợp tìm kiếm rộng và tìm kiếm sâu trên cơ sở cho trước mức sâu n rồi tìm kiếm rộng ứng với mức sâu đó. − Tìm kiếm cực tiểu hóa giá thành: mỗi cung của cây (đồ thị) được gán giá thành và hướng tìm kiếm được xác định bởi việc cực tiểu hóa giá thành đường đi. − Tìm kiếm với tri thức bổ sung: hướng tìm kiếm được xác định với tri thức bổ sung ở mỗi bước. Trước hết các thủ tục tìm kiếm rộng, sâu và sâu dần sẽ được mô tả qua một ví dụ. Sau đó một số thuật giải tìm kiếm cực tiểu hóa giá thành và bổ sung tri thức sẽ được trình bày chi tiết. 5
  15. Chương 2: Các thuật toán tìm đường đi 1. Mô tả các thủ tục tìm kiếm rộng, sâu và sâu dần 100 1 1 A 17 D B C 1 1 10 10 12 1 E F G H I J 1 1 1 1 K L M N 1 1 O P 1 1 Q R 1 1 T S 1 U 1 Trạng thái mong muốn V Tìm kiếm rộng: quá trình tìm kiếm sẽ lần lượt là A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V… Tìm kiếm sâu: quá trình tìm kiếm sẽ lần lượt là A, E, K, O, Q, S, T, U, V, …B, F,… C, G, L, H, M, … D, I, J, N, P, R. Chú ý: nếu nhánh dưới v dài vô hạn thì quá trình tìm kiếm sẽ không bao giờ đến được mục tiêu. Tìm kiếm sâu dần: ứng với mức sâu 2: (A,E), (B,F), (C,G), (C,H), (D,I), (D,J). 6
  16. Chương 2: Các thuật toán tìm đường đi ứng với mức sâu 3: (A,E,K), (B,F), (C,G,L), (C,H,M), (D,I), (D,J,N). 2. Thuật giải tìm đường đi có giá thành nhỏ nhất AT (Algorithm for Trees) với mỗi đỉnh n tương ưng số g(n) là giá thành đường đi từ đỉnh đầu tới n. (g(n) có thể chưa xác định đối với các đỉnh thuộc phần cây chưa hướng đến). Mỗi đỉnh n có thể là: − Đỉnh đóng: nghĩa là đỉnh đã được xem xét; − Đỉnh mở: là đỉnh giả định sẽ được xem ở bước sau; − Đỉnh ẩn: là đỉnh mà hàm g(n) tương ứng chưa được tính đến và chưa được xem xét đến. Thuật giải AT gồm các bước sau: Bước 1: Đầu tiên, mọi đỉnh n và mọi giá trị g(n) đều là ẩn. Mở đỉnh đầu tiên (coi đỉnh đầu tiên là đỉnh mở và đặt giá trị g tương ứng bằng 0). Bước 2: Chọn đỉnh mở với giá thành g tương ứng nhỏ nhất. Gọi đỉnh này là N, nếu N là đỉnh mục tiêu thì đường dẫn tới N là đường đi có giá thành nhỏ nhất g(n) và vấn đề đã được giải. Nếu không còn đỉnh mở nào thì cây biểu diễn vấn đề không có đường đi tới mục tiêu. Nếu có từ 2 đỉnh trở lên cùng giá trị g nhỏ nhất thì kiểm tra trong số đó có đỉnh mục tiêu không? Nếu có thì chọn đỉnh mục tiêu đó và quá trình giải kết thúc. Nếu không thì chọn tùy ý một đỉnh trong số đó và gọi là N. Bước 3: Đóng đỉnh N và mở các đỉnh sau N (có cùng hướng đến N), với mỗi đỉnh sau N gọi là s, ta tính: g(s)=g(N)+(giá thành cung từ N tới s) Bước 4: Quay trở lại bước 2. Thuật giải AT đã được chứng minh là luôn luôn tìm được đường đi với giá thành nhỏ nhất nếu như tồn tại đường đó trên đồ thị và là thuật giải tối ưu theo nghĩa số đỉnh đóng trong quá trình tìm kiếm là ít nhất. 7
  17. Chương 2: Các thuật toán tìm đường đi 3. Tìm kiếm với tri thức bổ sung Thuật giải AT là thuật giải tìm kiếm đường đi tốt nhất đối với các cây chỉ có thông tin về đỉnh, cung và giá thành cung. Nhưng trong nhiều trường hợp việc tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các tri thức thu được dựa trên những hiểu biết về tình huống vấn đề ở mỗi bước. Các thủ tục tìm kiểm dựa trên 3 cách tiếp cận: − Không tính đến các tri thức bổ sung ngoài thông tin về đỉnh, cung, giá thành. − Sử dụng tri thức bổ sung để tìm cách giải riêng biệt cho vấn đề mà bỏ qua việc xây dựng cây biểu diễn cho vấn đề. − Xây dựng biểu diễn vấn đề dưới dạng cây có tính đến tri thức bổ sung trong cấu trúc cây hoặc giá thành các cung. Ngoài ra có có cách tiếp cạn theo hướng xây dựng các thuật giải “vạn năng”, tìm kiếm đường đi với tri thức bổ sung. Họ thuật giải này mang tên là AKT(Algorithm for knowledgeable Tree search). Tri thức bổ sung ở mỗi đỉnh ∧ được tương ứng một giá trị h(n) . Chẳng hạn đó là ước lượng giá thành đường ∧ đi từ n đến mục tiêu (như vậy h là ước lượng giá thành đường đi con chương biết đến). Thuật giải AKT gồm các bước sau: ∧ ∧ a) Đầu tiên, mọi đỉnh cũng như giá trị g, h , f là chưa biết. Mở đỉnh đầu tiên (o) và gán g(0), sử dụng tri thức bổ sung để ước tính h(0) và tính ∧ ∧ f (0) = g (0) + h(0) . ∧ ∧ b) Chọn đỉnh mở có giá trị f = g (n) + h(n) nhỏ nhất. Gọi đỉnh này là N. Nếu N là mục tiêu thì đường tới N là đường đi có giá thành nhỏ nhất g(N). Nếu không tồn tại đỉnh mở nào thì cây không tồn tại đường đi tới mục tiêu. Nếu có 8
  18. Chương 2: Các thuật toán tìm đường đi ∧ từ 2 đỉnh mở trở lên cùng giá trị f nhỏ nhất, hãy kiểm tra trong các đỉnh này có chứa mục tiêu không? Nếu một trong các đỉnh này là mục tiêu thì vấn đề đã được giải quyết, còn không thì chọn tùy ý một trong các đỉnh này là N. c) Đóng đỉnh N, mở đỉnh sau N. Với mỗi đỉnh S sau N ta tính g(s)=g(N)+(giá thành cung từ N đến S). Sử dụng tri thức bổ sung ở bước này, ∧ ∧ ∧ ước lượng h( s) và gán cho f(s) giá trị f ( s) = g ( s ) + h( s) . d) Quay về bước 2. Giải thích ý nghĩa AKT: giả sử h(n) là giá thành nhỏ nhất được biết chính xác từ n đến mục tiêu. Như vậy h(n) chỉ là ước lượng gần đúng về h(n). nếu ∧ h(n) ≡ h(n) thì AKT là thủ tục hoàn toàn tuyệt đối (các đỉnh đóng đúng là các đỉnh nằm trên đường đi ngắn nhất đến mục tiêu). Trong trường hợp không có ∧ tri thức bổ sung, h(n) = 0 và AKT suy biến thành AT. Ta thấy rõ ràng rằng giữa ∧ ∧ h = 0 và h = h sẽ tồn tại các thuật giải với mức độ hiệu quả rất thú vị. Nếu ∧ h ≤ h (với mọi n), AKT sẽ bảo đảm tìm ra được đường đi giá thành nhỏ nhất và tối ưu theo nghĩa sử dụng số đỉnh đóng ít nhất so với mọi thuật giải cũng chỉ làm việc với các tri thức như vậy. ∧ Nếu h > h (với mọi n, hoặc với một số đỉnh). AKT không bảo đảm tìm được đường đi giá thành nhỏ nhất nhưng đường đi mà AKT tìm ra vẫn dùng được trong nhiều trường hợp thực tiễn giải quyết vấn đề. 4. Tìm đường đi trên đồ thị tổng quát Các phần trên đã trình bày thuật giải tìm đường đi trên đồ thị dạng cây. Tuy nhiên biểu diễn dạng cây nhiều khi sẽ lặp lại quá nhiều một trạng thái. Điều đó sẽ tăng thêm thời gian tim kiếm. Để khắc phục cần nới bỏ điều kiện mỗi đỉnh chỉ có một cung hướng đến và do vậy phải nghiên cứu thuật giải tìm đường đi 9
  19. Chương 2: Các thuật toán tìm đường đi trên một đồ thị dạng tổng quát. Ta cũng có thể mở rộng thuật giải AKT thành thuật giải tổng quát A* như sau: ∧ ∧ Bước 1: Đầu tiên, mọi đỉnh và các giá trị g, h , f đều xem như chưa biết, ∧ ∧ ∧ mở đỉnh đầu tiên 0, gán cho g(0)=0, ước lượng h(0) và gán f (0) = h(0) . ∧ ∧ Bước 2: Chọn đỉnh mở với giá trị f = g + h nhỏ nhất và gọi là N. Nếu N là mục tiêu thì đường dẫn tới N đã tìm được và g(N) là giá thành của đường đi đó. Nếu không tồn tại đỉnh mở thì đồ thị đó không tồn tại đường đi đến mục tiêu. ∧ Nếu có từ 2 đỉnh mở trở lên cùng giá trị f và 1 trong 2 đỉnh đó là mục tiêu thì quá trình tìm đường đi cũng kết thúc, còn không thì chọn tùy ý một trong 2 đỉnh đó là N. Bước 3: Đóng đỉnh N và đối với mỗi đỉnh sau đó, ta tính g′( s) = g ( N ) + (giá thành cung từ N đến S). Nếu đỉnh S đã mở và g(s) ≤ g′( s ) thì bỏ qua S. Ngược ∧ ∧ ∧ lại ta mở S và đặt g(s) = g′( s ) , tính h( s) và f ( s ) = g ( s) + h( s ) . Bước 4: Quay về bước 2. Bây giờ chúng ta có thể dùng A* để tìm đường đi ngắn nhất giữa 2 thành ∧ phố dựa theo bản đồ giao thông với tri thức bổ sung h(n) có thể là khoảng cách đường chim bay từ điểm (thành phố) n tới mục tiêu (thành phố cần đến). Do khoảng cách đường chim bay bao giờ cũng nhỏ hơn khoảng cách đường giao ∧ ∧ thông nên h(n) ≤ h(n) với mọi n. Thuật giải A* với tri thức bổ sung h(n) như trên sẽ tìm được đường đi ngắn nhất (hoặc giá thành nhỏ nhất) với mức độ hiệu ∧ quả càng cao nếu h(n) càng gần h(n). ∧ ∧ ∧ Trong thuật giải A*, ta đặc f = g + h ở đây vai trò của g và h được xem là ∧ ∧ như nhau. Nhưng tùy theo trường hợp, có thể xét f = w1.g + w2. h với w1, w2 10
  20. Chương 2: Các thuật toán tìm đường đi ∧ là các trọng số cho biết vai trò của g và h tham gia trong quá trình giải. Ngoài ∧ ra cũng cần thêm các ước lượng về giá thành (độ phức tạp) của việc xác định h và tập đỉnh đóng để có cơ sở đánh giá hiệu quả của thuật giải một cách đầy đủ. 11
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
841 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.

 

Đồng bộ tài khoản
3=>0