Luận văn Thạc sĩ Toán học: Sử dụng kỹ thuật 'phễu' và 'cây phễu' để tìm đường đi ngắn nhất trên bề mặt của khối đa diện

Luận văn "Sử dụng kỹ thuật “phễu” và “cây phễu” để tìm đường đi ngắn nhất trên bề mặt của khối đa diện" trình bày lại một số thuật toán về tìm đường đi ngắn nhất trong một đa giác đơn, một khối đa điện và một dãy mặt tam giác trong không gian ba chiều.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Sử dụng kỹ thuật “phễu” và “cây phễu” để tìm đường đi ngắn nhất trên bề mặt của khối đa diện BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Mỹ Hạnh SỬ DỤNG KỸ THUẬT “PHỄU” VÀ “CÂY PHỄU” ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2020 BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Mỹ Hạnh SỬ DỤNG KỸ THUẬT “PHỄU” VÀ “CÂY PHỄU” ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Phan Thành An Hà Nội - 2020 LỜI CAM ĐOAN Tôi xin cam đoan mọi kết quả của đề tài: Sử dụng kỹ thuật “phễu” và “cây phễu” để tìm đường đi ngắn nhất trên bề mặt của khối đa diện đã được trình bày trong ba bài báo [7], [10] và [5], các ví dụ và số liệu trong luận văn là trung thực. Nếu không đúng như đã nêu trên, tôi xin hoàn toàn chịu trách nhiệm về đề tài của mình. Hà Nội, ngày 25 tháng 8 năm 2020 Nguyễn Thị Mỹ Hạnh LỜI CẢM ƠN Lời đầu tiên trong bản luận văn tôi xin gửi lời cảm ơn chân thành tới PGS. TS. Phan Thành An đã hướng dẫn tôi hoàn thiện bản luận văn này. Mặc dù rất bận rộn với công việc nhưng thầy vẫn luôn dành những thời gian quý giá của mình để hướng dẫn và chỉ bảo tôi tận tình. Trong quá trình làm luận văn bản thân tôi còn có nhiều thiếu sót, tuy nhiên thầy đã luôn luôn động viên và tạo điều kiện tốt nhất để tôi có thể hoàn thiện bản luận văn của mình. Tôi xin bày tỏ lòng biết ơn sâu sắc tới toàn thể các thầy cô trong Viện Toán học đã truyền đạt, chia sẻ cho tôi những kiến thức bổ ích. Đồng thời, tôi cũng xin bày tỏ sự biết ơn sâu sắc tới các thầy cô và các anh chị em của Học viện Khoa học và Công nghệ đã giúp đỡ và quan tâm tôi trong suốt quá trình học tập. Tôi cũng xin được gửi lời cảm ơn tới gia đình, bạn bè và anh chị trong nhóm nghiên cứu đã luôn cổ vũ, động viên, giúp đỡ tôi trong quá trình tham gia nhóm nghiên cứu để tôi củng cố được kiến thức và trau dồi các kĩ năng sử dụng các phần mềm hỗ trợ cho đề tài của mình. Hà Nội, ngày 25 tháng 8 năm 2020 Nguyễn Thị Mỹ Hạnh Mục lục LỜI CAM ĐOAN 3 LỜI CẢM ƠN 0 DANH MỤC KÍ HIỆU 3 MỞ ĐẦU 4 1 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN 6 1.1 ĐA GIÁC ĐƠN . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 ĐỒ THỊ, CÂY VÀ CHU TRÌNH, CÂY ĐỐI NGẪU . . . . 8 1.3 HÌNH ỐNG TAY VÀ HÌNH “PHỄU” . . . . . . . . . . . . . 11 1.4 THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN . . . . . . . . . . . . . . . 14 2 TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN 19 2.1 PHÉP LẬT . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 THUẬT TOÁN DÙNG NGUỒN SÁNG VÀ BÓNG . . . . . 23 3 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG MỘT DÃY MẶT TAM GIÁC TRONG KHÔNG GIAN BA CHIỀU 31 3.1 ĐƯỜNG TRẮC ĐỊA THẲNG NHẤT VÀ CÁC PHỄU DỌC THEO DÃY MẶT TAM GIÁC TRONG KHÔNG GIAN BA CHIỀU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1 2 3.2 THUẬT TOÁN TÌM CHÍNH XÁC ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM DỌC THEO DÃY MẶT TAM GIÁC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 ỨNG DỤNG THUẬT TOÁN NFU TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ MỘT ĐIỂM TỚI TẤT CẢ CÁC ĐIỂM TRÊN BỀ MẶT KHỐI ĐA DIỆN . . . . . . . . . . . . . . . . . . 43 KẾT LUẬN 51 TÀI LIỆU THAM KHẢO 52 3 DANH MỤC KÍ HIỆU [a, b] Một đoạn thẳng giới hạn bởi hai điểm a và b E = (e1 , . . . , em ) Một dãy các cạnh chung F = (f1 , . . . , fm+1 ) Một dãy mặt có m + 1 tam giác liền kề Fpq (s) Một phễu dọc theo F tương ứng với [p, q] có chóp là điểm s G Một đồ thị vô hướng P = (q1 , q2 , . . . , qn ) Một đa giác đơn có n đỉnh di Một đường chéo của đa giác P (1) (2) vi ; vi Hai điểm đầu mút của đường chéo di (j) SP (s, vi ) Đường đi ngắn nhất từ s tới điểm cuối vi (j) Ri Phễu được giới hạn bởi SP (v, vi (1) ), SP (v, vi (2) ) và đường chéo di I ei Ảnh của của điểm nguồn s lên cạnh ei Ie P rojei i Hình chiếu của Iei lên cạnh ei CF (u, v) Đường trắc địa thẳng nhất từ u tới v 4 MỞ ĐẦU Hiện nay, một trong những vấn đề đang được các nhà khoa học nghiên cứu trong lĩnh vực tối ưu, hình học tính toán là tính được đường đi ngắn nhất giữa hai điểm trên bề mặt của một khối đa diện, điều này rất có ích trong ngành công nghiệp chế tạo rô-bốt, tối ưu hệ thống thông tin địa lý và điều hướng ...