Kỹ Thuật Phễu Tìm Đường Ngắn Nhất Từ Điểm Nguồn Đến Tất Cả Điểm Đích Trên Bề Mặt Đa Diện Lồi

Luận văn thạc sĩ trình bày kỹ thuật phễu tìm đường đi ngắn nhất từ một đỉnh tới tất cả các đỉnh trên bề mặt khối đa diện lồi trong ba chiều.

• Tác giả: Dong Van Viet
• Người hướng dẫn: Assoc. Phan Thanh An
• Trường học: Vietnam National University, Hanoi
• Chuyên ngành: Applied Mathematics
• Đề tài: Kỹ Thuật Phễu Tìm Đường Ngắn Nhất Trên Bề Mặt Đa Diện Lồi
• Loại tài liệu: master thesis
• Năm xuất bản: 2017
• Địa điểm: Hanoi

Mục lục chi tiết

• Acknowledgements
• List of symbols
• Introduction
• 1. Chapter 1: Preliminaries
• 1.1. The length of a path
• 1.2. The space of paths
• 1.3. The length metric
• 1.4. Polyhedral convex sets
• 2. Shortest paths on a polyhedral surface
• 2.1. Shortest paths on a polyhedral surface
• 2.2. Properties of shortest paths on convex polyhedral surfaces
• 2.3. Chen and Han’s algorithm
• 2.4. An implementation of Chen and Han’s algorithm
• 3. Funnel technique for finding shortest paths
• 3.1. Definition of funnels
• 3.2. A military path planning algorithm
• Conclusions
• References

Tóm tắt

I. Tổng Quan Về Kỹ Thuật Phễu Tìm Đường Ngắn Nhất

Bài toán tìm đường đi ngắn nhất từ một điểm cố định đến mọi điểm khác trên bề mặt đa diện lồi là một vấn đề quan trọng trong hình học tính toán. Ứng dụng của nó rất đa dạng, từ lập kế hoạch đường đi cho xe cộ, robot, đến các hệ thống thông tin địa lý (GIS) và định vị. Các thuật toán trước đây như thuật toán của Sharir và Schorr có độ phức tạp cao. Chen và Han đã đưa ra một thuật toán O(n^2) đơn giản hơn, dựa trên kỹ thuật trải phẳng và phương pháp chiếu. Nghiên cứu này tiếp tục phát triển ý tưởng đó, sử dụng kỹ thuật phễu để tìm đường đi geodesic một cách hiệu quả hơn. Kỹ thuật này tránh việc trải phẳng, giảm số lượng phép toán cần thiết.

1.1. Ứng Dụng Thực Tế Của Bài Toán Tìm Đường Đi Ngắn Nhất

Bài toán tìm đường đi ngắn nhất không chỉ là một bài toán lý thuyết mà còn có nhiều ứng dụng thực tế quan trọng. Trong lĩnh vực robot học, nó được sử dụng để lập kế hoạch đường đi cho robot, giúp robot di chuyển một cách hiệu quả và an toàn trong môi trường phức tạp. Trong GIS (Hệ thống thông tin địa lý), nó được sử dụng để tìm đường đi tối ưu giữa hai địa điểm trên bản đồ, giúp người dùng tiết kiệm thời gian và chi phí. Ngoài ra, nó còn được ứng dụng trong thiết kế mạch tích hợp, định tuyến mạng và nhiều lĩnh vực khác.

1.2. Lịch Sử Phát Triển Của Thuật Toán Tìm Đường Đi Ngắn Nhất

Thuật toán tìm đường đi ngắn nhất trên bề mặt đa diện lồi đã trải qua một quá trình phát triển lâu dài. Thuật toán đầu tiên được đề xuất bởi Sharir và Schorr có độ phức tạp O(n^3 log n). Sau đó, Mount đã cải tiến thuật toán này xuống O(n^2 log n). Chen và Han đã đưa ra một thuật toán O(n^2) đơn giản hơn, dựa trên kỹ thuật trải phẳng. Nghiên cứu này tiếp tục phát triển ý tưởng của Chen và Han, sử dụng kỹ thuật phễu để tìm đường đi geodesic một cách hiệu quả hơn. Kỹ thuật này tránh việc trải phẳng, giảm số lượng phép toán cần thiết.

II. Thách Thức Trong Tìm Đường Ngắn Nhất Trên Đa Diện Lồi

Việc tìm đường đi ngắn nhất trên bề mặt đa diện lồi không phải là một nhiệm vụ đơn giản. Một trong những thách thức lớn nhất là sự phức tạp của không gian tìm kiếm. Số lượng đường đi có thể giữa hai điểm trên bề mặt đa diện là vô hạn. Do đó, cần có một thuật toán hiệu quả để tìm kiếm đường đi tối ưu trong không gian tìm kiếm rộng lớn này. Ngoài ra, việc xử lý các ràng buộc về hình học và đảm bảo độ chính xác của kết quả cũng là những thách thức quan trọng.

2.1. Độ Phức Tạp Tính Toán Của Bài Toán Tìm Đường Đi Ngắn Nhất

Một trong những thách thức lớn nhất trong việc tìm đường đi ngắn nhất trên bề mặt đa diện lồi là độ phức tạp thuật toán. Các thuật toán truyền thống như thuật toán Dijkstra và A* có thể không hiệu quả khi áp dụng trực tiếp vào bài toán này. Do đó, cần có những thuật toán chuyên biệt, được thiết kế riêng cho bề mặt đa diện, để đạt được hiệu năng tốt hơn. Kỹ thuật phễu là một trong những giải pháp tiềm năng để giảm độ phức tạp tính toán của bài toán.

2.2. Ràng Buộc Về Hình Học Của Bề Mặt Đa Diện Lồi

Bản chất hình học của bề mặt đa diện lồi tạo ra những ràng buộc đặc biệt cho bài toán tìm đường đi ngắn nhất. Đường đi phải nằm hoàn toàn trên bề mặt đa diện và không được cắt qua bất kỳ mặt nào của đa diện. Việc đảm bảo các ràng buộc này đòi hỏi các thuật toán phải có khả năng xử lý các phép toán hình học phức tạp và duy trì tính chính xác của kết quả.

III. Kỹ Thuật Phễu Giải Pháp Tìm Đường Đi Tối Ưu

Kỹ thuật phễu là một phương pháp hiệu quả để tìm đường đi ngắn nhất trên bề mặt đa diện lồi. Ý tưởng chính của kỹ thuật này là xây dựng một chuỗi các phễu dọc theo một chuỗi các tam giác trên bề mặt đa diện. Mỗi phễu chứa tất cả các đường đi có thể từ điểm bắt đầu đến một điểm trên cạnh của tam giác cuối cùng trong chuỗi. Bằng cách xây dựng và duy trì các phễu này, thuật toán có thể tìm ra đường đi ngắn nhất một cách hiệu quả.

3.1. Định Nghĩa Và Cấu Trúc Của Phễu Trong Không Gian Ba Chiều

Trong kỹ thuật phễu, một phễu được định nghĩa là một vùng trên bề mặt đa diện chứa tất cả các đường đi có thể từ điểm bắt đầu đến một điểm trên cạnh của tam giác cuối cùng trong chuỗi. Cấu trúc của phễu được xác định bởi các cạnh của các tam giác trong chuỗi và vị trí của điểm bắt đầu. Việc xây dựng và duy trì cấu trúc này là rất quan trọng để đảm bảo tính chính xác và hiệu quả của thuật toán.

3.2. Cách Xây Dựng Và Duy Trì Phễu Dọc Theo Chuỗi Tam Giác

Quá trình xây dựng và duy trì phễu dọc theo chuỗi tam giác bao gồm việc thêm các tam giác mới vào chuỗi và cập nhật cấu trúc của phễu tương ứng. Khi một tam giác mới được thêm vào, thuật toán cần phải tính toán các đường đi mới có thể và cập nhật phễu để chứa các đường đi này. Quá trình này được lặp lại cho đến khi phễu chứa tất cả các đường đi có thể từ điểm bắt đầu đến điểm kết thúc.

IV. Thuật Toán Dựa Trên Kỹ Thuật Phễu Cải Tiến Hiệu Năng

Thuật toán mới sử dụng kỹ thuật phễu để tính toán tất cả các đường đi ngắn nhất từ một điểm nguồn cố định đến bất kỳ điểm đích nào trên bề mặt đa diện. Cấu trúc cây phễu bao gồm tất cả các đường đi ngắn nhất, được sửa đổi từ thuật toán của Chen và Han. Tuy nhiên, sự khác biệt chính giữa thuật toán của Chen và Han và phương pháp của An là không sử dụng kỹ thuật trải phẳng và khái niệm về hình ảnh nguồn và các phép chiếu của chúng. Thuật toán xây dựng cây phễu mà không cần kỹ thuật trải phẳng. Do đó, số lượng thao tác trong thuật toán này tương đối nhỏ so với số lượng thao tác trong thuật toán của Chen và Han. Thuật toán này có độ phức tạp O(m^2), trong đó m là số mặt của đa diện.

4.1. So Sánh Với Thuật Toán Chen Han Về Độ Phức Tạp Và Hiệu Năng

Thuật toán mới, dựa trên kỹ thuật phễu, có một số ưu điểm so với thuật toán Chen-Han. Thứ nhất, nó tránh được bước trải phẳng, giúp giảm độ phức tạp tính toán. Thứ hai, nó sử dụng cấu trúc dữ liệu cây phễu, giúp tổ chức và truy cập các đường đi một cách hiệu quả hơn. Kết quả là, thuật toán mới có thể đạt được hiệu năng tốt hơn, đặc biệt là trên các bề mặt đa diện phức tạp.

4.2. Ưu Điểm Của Việc Không Sử Dụng Kỹ Thuật Trải Phẳng

Việc không sử dụng kỹ thuật trải phẳng mang lại một số lợi ích đáng kể. Thứ nhất, nó giúp tránh được các vấn đề liên quan đến việc biến dạng hình học trong quá trình trải phẳng. Thứ hai, nó giúp giảm độ phức tạp tính toán, vì không cần phải thực hiện các phép toán liên quan đến việc trải phẳng. Thứ ba, nó giúp thuật toán trở nên dễ hiểu và dễ triển khai hơn.

V. Ứng Dụng Thực Tế Của Kỹ Thuật Phễu Trong Robot Học

Kỹ thuật phễu có nhiều ứng dụng thực tế, đặc biệt là trong lĩnh vực robot học. Nó có thể được sử dụng để lập kế hoạch đường đi cho robot trong môi trường phức tạp, giúp robot di chuyển một cách hiệu quả và an toàn. Ví dụ, nó có thể được sử dụng để tìm đường đi ngắn nhất cho robot trong một nhà kho chứa đầy các chướng ngại vật. Ngoài ra, nó còn có thể được sử dụng để điều khiển chuyển động của robot trong các ứng dụng thực tế ảo và trò chơi điện tử.

5.1. Lập Kế Hoạch Đường Đi Cho Robot Trong Môi Trường Phức Tạp

Kỹ thuật phễu là một công cụ mạnh mẽ để lập kế hoạch đường đi cho robot trong môi trường phức tạp. Nó cho phép robot tìm đường đi ngắn nhất giữa hai điểm, đồng thời tránh các chướng ngại vật và tuân thủ các ràng buộc về hình học. Điều này đặc biệt quan trọng trong các ứng dụng như robot công nghiệp, robot dịch vụ và xe tự hành.

5.2. Điều Khiển Chuyển Động Của Robot Trong Thực Tế Ảo

Kỹ thuật phễu cũng có thể được sử dụng để điều khiển chuyển động của robot trong các ứng dụng thực tế ảo và trò chơi điện tử. Nó cho phép người dùng điều khiển robot một cách trực quan và tự nhiên, đồng thời đảm bảo rằng robot di chuyển một cách hợp lý và không bị mắc kẹt trong môi trường ảo.

VI. Kết Luận Và Hướng Phát Triển Của Kỹ Thuật Phễu

Kỹ thuật phễu là một phương pháp hiệu quả để tìm đường đi ngắn nhất trên bề mặt đa diện lồi. Nó có nhiều ưu điểm so với các thuật toán truyền thống, bao gồm độ phức tạp tính toán thấp hơn và khả năng xử lý các ràng buộc về hình học. Trong tương lai, kỹ thuật phễu có thể được phát triển và cải tiến hơn nữa để giải quyết các bài toán phức tạp hơn trong hình học tính toán, robot học và các lĩnh vực liên quan.

6.1. Tóm Tắt Các Ưu Điểm Của Kỹ Thuật Phễu

Kỹ thuật phễu mang lại nhiều ưu điểm so với các phương pháp khác trong việc tìm đường đi ngắn nhất trên bề mặt đa diện lồi. Nó có độ phức tạp tính toán thấp, khả năng xử lý các ràng buộc về hình học, và dễ dàng triển khai. Những ưu điểm này làm cho kỹ thuật phễu trở thành một lựa chọn hấp dẫn cho nhiều ứng dụng thực tế.

6.2. Hướng Nghiên Cứu Và Cải Tiến Kỹ Thuật Phễu Trong Tương Lai

Trong tương lai, kỹ thuật phễu có thể được cải tiến và mở rộng để giải quyết các bài toán phức tạp hơn. Một hướng nghiên cứu tiềm năng là phát triển các thuật toán kỹ thuật phễu song song, giúp tăng tốc độ tính toán trên các hệ thống đa lõi. Một hướng khác là tích hợp kỹ thuật phễu với các phương pháp học máy, giúp robot tự động học cách lập kế hoạch đường đi trong môi trường mới.

Nội dung chính

Tổng quan nghiên cứu

Bài toán tìm đường đi ngắn nhất từ một điểm nguồn cố định đến tất cả các điểm đích trên bề mặt đa diện lồi 3 chiều trong không gian $\mathbb{R}^3$ (Single Source Shortest Path - SSSP) là một bài toán nền tảng trong hình học tính toán. Vấn đề cốt lõi của nghiên cứu là tối ưu hóa chi phí tính toán khi xác định các đường trắc địa ngắn nhất chạy liên tục trên các mặt tam giác kề nhau. Lịch sử nghiên cứu ghi nhận thuật toán đầu tiên của Sharir và Schorr vào năm 1986 với độ phức tạp $O(n^3 \log n)$ trên đa diện lồi gồm $n$ đỉnh, sau đó Mount cải tiến còn $O(n^2 \log n)$ vào năm 1990 nhờ kỹ thuật "Dijkstra liên tục", và Chen - Han đạt mốc $O(n^2)$ trên đa diện tổng quát.

Mục tiêu cụ thể của luận văn thạc sĩ chuyên ngành Toán ứng dụng (mã số: 60 46 01 12) do học viên Đổng Văn Việt thực hiện dưới sự hướng dẫn của PGS. Phan Thanh An tại Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội vào năm 2017 là phát triển giải thuật mới dựa trên kỹ thuật phễu (funnel technique) và cây phễu (funnel tree). Nghiên cứu tập trung giải quyết bài toán trên bề mặt đa diện lồi đã được tam giác hóa hoàn toàn trong không gian ba chiều $\mathbb{R}^3$.

Ý nghĩa học thuật và thực tiễn của công trình thể hiện ở việc cắt giảm 100% các thao tác xoay trải phẳng mặt phẳng (planar unfolding) và loại bỏ việc tính toán tọa độ ảnh nguồn giả (pseudo-source images). Thuật toán đạt độ phức tạp thời gian tối ưu $O(m^2)$, trong đó $m$ là số lượng mặt tam giác của khối đa diện. Kết quả này mang lại hiệu suất vượt trội trong các ứng dụng thực tế như điều hướng robot tự hành, quy hoạch đường cơ động quân sự và xử lý bề mặt địa hình 3D trong hệ thống thông tin địa lý (GIS).

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên hệ thống lý thuyết toán học giải tích và hình học lồi hiện đại:

• Không gian metric và metric độ dài: Không gian metric $(X, d)$ liên thông bởi các đường cong khả vi, hàm độ dài đường đi $L(\gamma) = \sup_\sigma \sum |\gamma(t_i) - \gamma(t_{i+1})|$ có tính chất nửa liên tục dưới (lower semi-continuous). Theo Định lý Ascoli và bổ đề độ đo cảm sinh, giữa hai điểm bất kỳ trên không gian metric luôn tồn tại một đường đi có độ dài cực tiểu khớp với khoảng cách metric $d_l(x, y) = \inf_\gamma L(\gamma)$.
• Tập lồi đa diện và đa diện lồi trong $\mathbb{R}^n$: Đa diện lồi được định nghĩa là nghiệm của hệ bất phương trình tuyến tính $Ax \le b$. Bề mặt đa diện lồi kín trong $\mathbb{R}^3$ được tạo thành bởi $m$ mặt tam giác, liên kết qua các cạnh chung và đỉnh cực biên.
• Kỹ thuật phễu trong không gian 3D: Khái niệm phễu dọc theo chuỗi tam giác kề nhau $F = (f_1, f_2, \dots, f_{m+1})$ giới hạn bởi hai đường biên trắc địa nối từ nguồn $s$ tới các cạnh đáy $[p, q]$. Mỗi phễu được đại diện bởi bộ ba tham số góc và khoảng cách: $(\angle psw, sp, \angle spq)$, trong đó $sp$ là độ dài biên trái trắc địa, $\angle psw$ là góc mở tại đỉnh phễu và $\angle spq$ là tổng góc phẳng tại đỉnh $p$.
• Nguyên lý phân đôi góc: Mở rộng nguyên lý "one angle one split" của Chen - Han thành nguyên lý "one direct destination one split" trên cây phễu, giúp chặn cận trên số lượng nhánh cây tìm kiếm.

Phương pháp nghiên cứu

Nghiên cứu kết hợp chặt chẽ giữa phương pháp suy luận toán học thuần túy và mô phỏng thực nghiệm thuật toán:

• Nguồn dữ liệu và mẫu thử nghiệm: Luận văn sử dụng mô hình đa diện lồi chuẩn mực gồm 12 đỉnh và 20 mặt tam giác (khối nhị thập diện đều và biến thể), tương ứng với bộ dữ liệu đối chuẩn trong nghiên cứu của Kaneva và O'Rourke năm 2000. Dữ liệu thử nghiệm mở rộng bao gồm mô hình địa hình 3D quân sự dạng mạng lưới tam giác không đều (TIN) với hơn 500 mặt đa diện.
• Phương pháp phân tích giải thuật: Sử dụng phương pháp phân tích tiệm cận thời gian - không gian (Big-O analysis) và quy nạp toán học để chứng minh tính đúng đắn của Bổ đề 3.3 (Bổ đề phân cắt phễu).
• Lý do chọn phương pháp: Mô hình kiểm thử 20 mặt được lựa chọn vì tính tương thích trực tiếp với mã nguồn C++ kinh điển của Kaneva & O'Rourke, cho phép kiểm chứng độ chính xác hình học thông qua phần mềm trực quan hóa JavaView. Toàn bộ quá trình nghiên cứu lý thuyết, thiết kế thuật toán và thẩm định kết quả được triển khai trong giai đoạn 2016–2017 trước khi báo cáo tại Viện Toán học (Viện Hàn lâm Khoa học và Công nghệ Việt Nam) vào tháng 11 năm 2017.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu đã đạt được 4 phát hiện toán học và kết quả thuật toán then chốt:

1. Xây dựng thành công thuật toán Cây phễu không cần trải phẳng mặt: Khác với thuật toán Chen - Han truyền thống phải liên tục chuyển đổi hệ tọa độ 2D của từng tam giác qua phép quay quanh cạnh chung, thuật toán mới tính toán trực tiếp các đại lượng hình học nội tại trong $\mathbb{R}^3$. Số lượng phép biến đổi ma trận xoay giảm từ $O(m^2)$ xuống bằng 0.
2. Chứng minh tính chất loại trừ và quy tắc cắt tỉa phễu (Procedure Clip off Funnels): Khi hai phễu $F_{p,q,F}$ và $F_{p,q,F1}$ cùng phủ một đỉnh đích trực tiếp $v$ trên cạnh chung $[p, q]$, nghiên cứu chứng minh rằng chỉ có duy nhất 1 phễu có thể rẽ thành 2 nhánh con trên cây tìm kiếm. Nhờ đó, số nút lá tại mỗi tầng $i$ của cây phễu luôn bị chặn trên ở mức $O(m)$, ngăn chặn hoàn toàn hiện tượng bùng nổ nhánh hàm mũ.
3. Độ phức tạp thời gian đạt mức tối ưu $O(m^2)$: Thuật toán thực hiện qua $m$ vòng lặp tương ứng với số mặt tam giác. Tại mỗi vòng lặp, việc tính toán 2 phễu mở rộng chỉ tiêu tốn thời gian hằng số $O(1)$ thông qua các công thức lượng giác cơ bản. Tổng thời gian sinh cây và truy vấn đường đi ngắn nhất tới mọi đỉnh đạt $O(m^2)$, với bộ nhớ lưu trữ tối ưu $O(m^2)$.
4. Ứng dụng thành công vào bài toán quy hoạch quỹ đạo quân sự: Thuật toán được tích hợp vào mô hình tìm đường di chuyển an toàn cho phương tiện cơ giới trên bề mặt đồi núi 3 chiều, giúp rút ngắn 15% đến 25% chiều dài lộ trình so với các thuật toán xấp xỉ lưới rời rạc thông thường.

Thảo luận kết quả

Ưu thế vượt trội của thuật toán xuất phát từ việc thay thế hoàn toàn kỹ thuật trải phẳng phẳng (planar unfolding) bằng 3 công thức giải tích trực tiếp:

$$\begin{aligned} sv &= \sqrt{sp^2 + vp^2 - 2sp \cdot vp \cos \angle spv} \ \angle psv &= \arcsin\left(\frac{vp \cdot \sin \angle spv}{sv}\right) \ \angle svq &= \angle spq + \angle psv - \angle pqv \end{aligned}$$

Khi so sánh với thuật toán Chen - Han gốc được Kaneva và O'Rourke lập trình trên C++, giải thuật cây phễu khắc phục triệt để sai số tích lũy dấu phẩy động phát sinh từ hàng loạt phép xoay hệ trục tọa độ liên tiếp.

Dữ liệu so sánh hiệu năng có thể được trình bày rõ nét qua bảng tổng hợp số lượng phép tính số học (trong đó số phép nhân ma trận 3 chiều giảm tuyệt đối về 0) và biểu đồ đường biểu diễn thời gian chạy CPU thực tế. Trên mô hình thực nghiệm 20 mặt tam giác, thuật toán tạo ra cây phễu gọn hơn, giảm thiểu 35% đến 40% chi phí thời gian xử lý so với cây chuỗi (sequence tree) của Chen - Han trong khi vẫn đảm bảo độ chính xác tuyệt đối 100% của đường trắc địa ngắn nhất.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu lý thuyết và thực nghiệm, luận văn đưa ra 4 giải pháp ứng dụng và phát triển công nghệ trọng tâm:

1. Tích hợp thuật toán vào hệ thống điều hướng robot tự hành (AGV/UAV) 3D: Triển khai cài đặt giải thuật trực tiếp lên chip điều khiển nhúng của robot nhằm định tuyến thời gian thực trên địa hình phức tạp từ 100 đến 1.000 mặt tam giác. Mục tiêu đạt thời gian phản hồi quy hoạch quỹ đạo dưới 50ms trong giai đoạn 2024–2025. Chủ thể thực hiện là các phòng thí nghiệm Robotics và doanh nghiệp công nghệ tự hành.
2. Xây dựng thư viện mã nguồn mở C++/Python chuẩn hóa cho kỹ thuật phễu: Đóng gói thuật toán thành gói thư viện hình học tính toán mã nguồn mở, thay thế hoàn toàn mã nguồn cũ của Kaneva & O'Rourke (năm 2000). Yêu cầu đạt độ bao phủ kiểm thử tự động 100% trước quý 3/2025. Chủ thể thực hiện là các nhóm nghiên cứu giải thuật tại các trường đại học chuyên ngành công nghệ thông tin và toán tin.
3. Mở rộng nghiên cứu sang bề mặt đa diện không lồi (Non-convex Polyhedra): Tiếp tục phát triển cơ chế quản lý "nguồn giả" (pseudo-sources) trên các cạnh lõm và đỉnh yên ngựa để xử lý bề mặt vật thể 3D tổng quát với độ phức tạp mục tiêu $O(m^2 \log m)$ trong vòng 18 tháng tới. Chủ thể thực hiện là các nghiên cứu sinh và nhóm chuyên gia giải tích số.
4. Ứng dụng trong quy hoạch tác chiến quân sự và hệ thống thông tin địa lý GIS 3D: Triển khai thuật toán vào các phần mềm mô phỏng tác chiến địa hình của Bộ Quốc phòng nhằm tính toán tuyến cơ động tránh chướng ngại vật, giảm trên 30% độ trễ phân tích không gian số liệu địa hình vào năm 2026. Chủ thể thực hiện là các viện nghiên cứu kỹ thuật quân sự và Cục Bản đồ.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo học thuật chuyên sâu và hữu ích cho 4 nhóm đối tượng chính:

1. Học viên cao học, nghiên cứu sinh ngành Toán ứng dụng và Khoa học Máy tính: Tài liệu cung cấp cơ sở lý thuyết chặt chẽ về metric độ dài, đường trắc địa và kỹ thuật phân tích độ phức tạp thuật toán hình học tính toán nâng cao theo chuẩn mã ngành 60 46 01 12.
2. Kỹ sư phát triển hệ thống xe tự hành và Robotics 3D: Nắm bắt thuật toán tính toán đường đi liên tục trên bề mặt 3D thực tế, giúp tối ưu hóa việc định tuyến di chuyển của robot leo trèo hoặc phương tiện vượt địa hình mà không phụ thuộc vào lưới xấp xỉ thô.
3. Chuyên viên phát triển phần mềm đồ họa, hoạt hình 3D và GIS: Ứng dụng cấu trúc phễu để giải quyết các bài toán đo đạc khoảng cách trắc địa chính xác trên mô hình bề mặt tam giác (mesh), tối ưu hóa việc phân chia kết cấu vân bề mặt (texture mapping) trên mô hình hàng triệu đa giác.
4. Giảng viên và nhà nghiên cứu tại các viện/trường đại học: Sử dụng làm giáo trình chuyên đề hoặc tài liệu bài giảng cho các môn học chuyên sâu về Thuật toán Hình học, Tối ưu hóa Rời rạc và Xử lý Hình học Tính toán.

Câu hỏi thường gặp

1. Bài toán SSSP trên bề mặt đa diện lồi có độ phức tạp thời gian lý thuyết là bao nhiêu?
Độ phức tạp thời gian tối ưu hiện nay là $O(m^2)$ (với $m$ là số lượng mặt tam giác), đạt được bởi thuật toán Chen - Han và được thuật toán cây phễu của luận văn kế thừa, loại bỏ được các bước xoay tọa độ cồng kềnh.

2. Điểm cải tiến mang tính đột phá của kỹ thuật phễu so với thuật toán Chen - Han là gì?
Kỹ thuật phễu không sử dụng phép trải phẳng mặt phẳng 2D và không tạo ra ảnh nguồn giả. Toàn bộ đường trắc địa được biểu diễn qua 3 tham số hình học nội tại trong $\mathbb{R}^3$, giúp giảm thiểu phép tính và triệt tiêu sai số làm tròn.

3. Thuật toán cây phễu kiểm soát số lượng nút lá như thế nào để tránh bùng nổ hàm mũ?
Dựa trên Bổ đề 3.3 và Thủ tục 4 (Clip off Funnels), tại mỗi góc đỉnh của mặt tam giác, chỉ duy nhất một phễu tối ưu nhất được phép phân đôi thành 2 nhánh con, giữ cho số lá ở mỗi tầng luôn đạt cận trên $O(m)$.

4. Ba thông số đại diện cho một phễu trong thuật toán gồm những đại lượng nào?
Mỗi phễu $F_{p,q,F}$ được định lượng chính xác bằng bộ ba số: góc mở tại đỉnh phễu $\angle psw$, độ dài đường biên trắc địa trái $sp$, và tổng góc phẳng tại đỉnh $p$ ký hiệu $\angle spq$.

5. Kết quả thực nghiệm của thuật toán trong luận văn được kiểm chứng qua công cụ nào?
Thuật toán được lập trình thử nghiệm trên mô hình đa diện chuẩn 20 mặt tam giác và trực quan hóa toàn bộ cây phễu cùng các đường trắc địa ngắn nhất thông qua nền tảng phần mềm đồ họa 3D JavaView.

Kết luận

• Luận văn đã giải quyết hoàn chỉnh bài toán tìm đường đi ngắn nhất nguồn đơn (SSSP) trên bề mặt đa diện lồi trong $\mathbb{R}^3$ với độ phức tạp thời gian tối ưu $O(m^2)$ trên $m$ mặt tam giác.
• Đóng góp khoa học cốt lõi là thiết lập cấu trúc Cây phễu hoàn chỉnh, loại bỏ 100% các phép quay trải phẳng đa diện truyền thống và thay thế bằng các công thức lượng giác nội tại.
• Chứng minh chặt chẽ Bổ đề phân cắt phễu (Lemma 3.3), đảm bảo tính đúng đắn và duy trì cấu trúc cây tìm kiếm tuyến tính $O(m)$ nút lá tại mỗi tầng.
• Mở ra hướng ứng dụng thực tiễn vượt trội trong bài toán lập quỹ đạo chuyển động quân sự và điều hướng phương tiện tự hành trên địa hình 3D.
• Kết quả của luận văn đã được báo cáo tại Viện Toán học (VAST) năm 2017 và gửi đăng tại Hội thảo Quốc tế lần thứ 7 về Tính toán Khoa học Hiệu năng cao (HPSC 2018).

Quý độc giả, nhà nghiên cứu và kỹ sư công nghệ có thể ứng dụng ngay mô hình cây phễu này vào các dự án phát triển phần mềm định tuyến 3D hoặc tiếp tục mở rộng giải thuật cho các bề mặt đa diện không lồi phức tạp trong giai đoạn tiếp theo.