I. Toàn cảnh luận văn lý thuyết đồ thị tìm đường đi ngắn nhất
Luận văn khóa luận tốt nghiệp của sinh viên Phongsavath Chanthavong tại Trường Đại học Quảng Nam là một công trình nghiên cứu chi tiết, hệ thống hóa kiến thức nền tảng về lý thuyết đồ thị và ứng dụng thực tiễn của nó. Trọng tâm của tài liệu là bài toán tìm đường đi ngắn nhất, một trong những vấn đề kinh điển và có tính ứng dụng cao nhất trong lĩnh vực khoa học máy tính. Được xây dựng trên nền tảng của toán rời rạc và cấu trúc dữ liệu và giải thuật, luận văn không chỉ dừng lại ở việc trình bày lý thuyết mà còn đi sâu vào việc phân tích, so sánh các thuật toán và cài đặt một ứng dụng minh họa. Công trình này đóng vai trò như một tài liệu chuyên ngành CNTT quan trọng, cung cấp một cái nhìn toàn diện từ các khái niệm cơ bản như đồ thị, đường đi, chu trình cho đến các thuật toán định tuyến phức tạp. Cấu trúc của luận văn được chia thành ba chương rõ ràng: Chương 1 tổng quan về lý thuyết, Chương 2 phân tích các thuật toán, và Chương 3 tập trung vào việc xây dựng ứng dụng thực tế. Cách tiếp cận này giúp người đọc dễ dàng theo dõi và nắm bắt được bản chất của vấn đề, từ đó thấy được sức mạnh của lý thuyết đồ thị trong việc mô hình hóa và giải quyết các bài toán tối ưu hóa trong thế giới thực.
1.1. Giới thiệu khóa luận tốt nghiệp của Phongsavath Chanthavong
Công trình nghiên cứu mang tên "Lý thuyết đồ thị và ứng dụng trong bài toán tìm đường đi ngắn nhất" được thực hiện bởi sinh viên Phongsavath Chanthavong, thuộc Khoa Công nghệ thông tin, Trường Đại học Quảng Nam, vào năm 2017. Dưới sự hướng dẫn của ThS. Lê Thị Nguyên Án, khóa luận này là kết quả của một quá trình tìm hiểu, thu thập tài liệu và đánh giá các thuật toán liên quan. Mục tiêu của đề tài, như tác giả trình bày, là nhằm hiểu rõ các khái niệm cốt lõi, nắm vững và so sánh các thuật toán tìm đường đi, và đặc biệt là xây dựng một ứng dụng thực tế sử dụng thuật toán Floyd. Đây là một ví dụ điển hình về việc kết hợp giữa lý thuyết và thực hành trong nghiên cứu khoa học sinh viên, tạo ra một sản phẩm có giá trị tham khảo cao.
1.2. Nền tảng toán rời rạc và cấu trúc dữ liệu và giải thuật
Lý thuyết đồ thị là một nhánh quan trọng của toán rời rạc, cung cấp một ngôn ngữ hình thức để mô tả các mối quan hệ giữa các đối tượng. Các khái niệm như đỉnh (nodes) và cạnh (edges) cho phép mô hình hóa vô số hệ thống phức tạp, từ mạng máy tính, mạng xã hội đến mạng lưới giao thông. Việc giải quyết bài toán tìm đường đi ngắn nhất đòi hỏi sự am hiểu sâu sắc về cấu trúc dữ liệu và giải thuật. Các thuật toán như Dijkstra hay Bellman-Ford không chỉ là các công thức toán học, mà còn là các quy trình tính toán hiệu quả, phụ thuộc vào cách dữ liệu đồ thị được lưu trữ và truy xuất. Luận văn đã làm nổi bật mối liên kết chặt chẽ này, cho thấy tầm quan trọng của việc lựa chọn đúng giải thuật cho từng loại cấu trúc dữ liệu cụ thể để đạt được hiệu suất tối ưu.
1.3. Mục tiêu và đóng góp của tài liệu chuyên ngành CNTT này
Đóng góp chính của khóa luận không chỉ là việc tổng hợp kiến thức. Nó cung cấp một cái nhìn chi tiết và so sánh trực tiếp giữa các phương pháp tìm đường đi, giúp người đọc nhận ra ưu và nhược điểm của từng thuật toán. Theo tác giả, mục tiêu của đề tài là "Cung cấp kiến thức đầy đủ hơn, chi tiết hơn về lý thuyết đồ thị cũng như các phương pháp tìm đường đi ngắn nhất trên đồ thị". Quan trọng hơn, việc demo thành công thuật toán Floyd trong một ứng dụng thực tế đã chứng minh tính khả thi và hiệu quả của các giải pháp lý thuyết. Công trình này trở thành một tài liệu tham khảo hữu ích cho sinh viên ngành Công nghệ thông tin, đặc biệt là những ai quan tâm đến lĩnh vực tối ưu hóa mạng lưới và các thuật toán định tuyến.
II. Thách thức cốt lõi trong bài toán tìm đường đi ngắn nhất
Bài toán tìm đường đi ngắn nhất là một vấn đề tối ưu hóa kinh điển, tuy nhiên, việc giải quyết nó phải đối mặt với nhiều thách thức phức tạp. Thách thức đầu tiên đến từ chính cấu trúc của đồ thị. Một đồ thị có hướng đặt ra các ràng buộc về chiều di chuyển, trong khi một đồ thị có trọng số yêu cầu tính toán chi phí trên mỗi cạnh, làm cho bài toán không còn đơn thuần là tìm đường đi có ít cạnh nhất. Luận văn của Phongsavath Chanthavong đã chỉ rõ những khái niệm này trong Chương 1, nhấn mạnh rằng việc lựa chọn thuật toán phụ thuộc rất nhiều vào đặc điểm của đồ thị. Một trong những trở ngại lớn nhất, được thảo luận kỹ lưỡng, là sự tồn tại của chu trình âm. Một chu trình có tổng trọng số âm cho phép tạo ra một đường đi ngắn vô hạn bằng cách lặp lại chu trình đó, khiến nhiều thuật toán kinh điển thất bại. Đây là một vấn đề nan giải trong các bài toán tối ưu hóa mạng lưới thực tế, chẳng hạn như trong lĩnh vực tài chính hoặc logistics. Hơn nữa, khi quy mô của mạng lưới tăng lên với hàng ngàn hoặc hàng triệu đỉnh, độ phức tạp tính toán của các thuật toán trở thành một yếu tố quyết định. Việc tìm ra một giải pháp không chỉ đúng mà còn phải hiệu quả về mặt thời gian là mục tiêu cuối cùng mà các nhà khoa học máy tính hướng tới.
2.1. Phân biệt đồ thị có trọng số và đồ thị có hướng
Luận văn định nghĩa rõ ràng các loại đồ thị khác nhau. Đồ thị có hướng (directed graph) là đồ thị mà các cạnh (cung) chỉ có thể được duyệt theo một chiều nhất định, mô phỏng các mối quan-hệ một chiều như đường một chiều hay dòng chảy dữ liệu. Ngược lại, đồ thị vô hướng cho phép di chuyển hai chiều. Trong khi đó, đồ thị có trọng số (weighted graph) gán một giá trị (trọng số) cho mỗi cạnh, đại diện cho chi phí, khoảng cách, hoặc thời gian. Sự kết hợp của hai đặc tính này tạo ra các mô hình phức tạp, đòi hỏi các thuật toán định tuyến phải xem xét cả hướng đi và chi phí tích lũy để tìm ra lộ trình tối ưu nhất.
2.2. Vấn đề chu trình âm trong các thuật toán định tuyến
Một chu trình âm là một chu trình trong đồ thị có trọng số mà tổng trọng số của các cạnh trong chu trình đó là một số âm. Như luận văn đã nêu, sự tồn tại của chu trình âm làm cho khái niệm "đường đi ngắn nhất" trở nên vô nghĩa đối với các cặp đỉnh có thể đi đến và đi từ chu trình đó. Bằng cách đi qua chu trình này nhiều lần, độ dài đường đi có thể giảm xuống âm vô cực. Đây là một vấn đề nghiêm trọng, vì các thuật toán tham lam như thuật toán Dijkstra không thể xử lý được trường hợp này. Do đó, cần có các thuật toán mạnh mẽ hơn như thuật toán Bellman-Ford để vừa tìm đường đi, vừa có khả năng phát hiện sự tồn tại của các chu trình âm này.
2.3. Sự phức tạp tính toán khi tối ưu hóa mạng lưới lớn
Hiệu suất là yếu tố sống còn trong các ứng dụng thực tế. Khi một mạng lưới, ví dụ như mạng Internet hoặc mạng lưới giao thông của một thành phố lớn, được mô hình hóa thành đồ thị, số lượng đỉnh và cạnh có thể rất lớn. Độ phức tạp tính toán của một thuật toán (thường được biểu diễn bằng ký hiệu Big O) cho biết thời gian thực thi sẽ tăng như thế nào khi kích thước đầu vào tăng lên. Một thuật toán có độ phức tạp cao, chẳng hạn như O(n³), có thể hoạt động tốt trên đồ thị nhỏ nhưng sẽ trở nên cực kỳ chậm chạp trên các đồ thị lớn. Việc lựa chọn và cải tiến các cấu trúc dữ liệu và giải thuật để giảm độ phức tạp là một thách thức không ngừng trong khoa học máy tính.
III. Hướng dẫn thuật toán Dijkstra và Bellman Ford tìm đường đi
Chương 2 của luận văn tập trung phân tích các thuật toán kinh điển để giải quyết bài toán tìm đường đi ngắn nhất từ một đỉnh xuất phát (single-source shortest path). Hai trong số các thuật toán nổi bật nhất được trình bày là thuật toán Dijkstra và thuật toán Bellman-Ford. Mặc dù cả hai đều nhằm mục đích tìm ra lộ trình tối ưu, chúng hoạt động dựa trên những nguyên lý khác nhau và có các điều kiện áp dụng riêng biệt. Thuật toán Dijkstra sử dụng một chiến lược tham lam (greedy), luôn chọn đỉnh chưa được duyệt có khoảng cách ngắn nhất từ điểm xuất phát. Phương pháp này rất hiệu quả và nhanh chóng, nhưng nó có một hạn chế nghiêm trọng: chỉ hoạt động chính xác trên các đồ thị không có trọng số cạnh âm. Ngược lại, thuật toán Bellman-Ford có cách tiếp cận tổng quát hơn. Nó hoạt động dựa trên nguyên lý quy hoạch động, thực hiện lặp lại việc "thư giãn" (relax) tất cả các cạnh của đồ thị. Quá trình này đảm bảo rằng thuật toán có thể xử lý các đồ thị có trọng số âm và quan trọng hơn là có khả năng phát hiện sự tồn tại của chu trình âm. Sự khác biệt cơ bản này làm cho việc lựa chọn giữa hai thuật toán trở thành một quyết định quan trọng trong thiết kế hệ thống tối ưu hóa mạng lưới.
3.1. Nguyên lý hoạt động của thuật toán Dijkstra với trọng số không âm
Thuật toán Dijkstra hoạt động bằng cách duy trì một tập hợp các đỉnh đã được tìm thấy đường đi ngắn nhất. Ban đầu, tập hợp này chỉ chứa đỉnh xuất phát. Ở mỗi bước, thuật toán sẽ chọn ra đỉnh u chưa được xét có khoảng cách d[u] nhỏ nhất. Sau đó, nó cập nhật khoảng cách đến tất cả các đỉnh v kề với u theo công thức d[v] = min(d[v], d[u] + w(u,v)). Quá trình này lặp lại cho đến khi tất cả các đỉnh đều được xét hoặc đến khi tìm được đường đi đến đỉnh đích. Do tính chất tham lam, nó giả định rằng một khi đã chọn đường đi ngắn nhất đến một đỉnh, sẽ không có con đường nào khác tốt hơn. Giả định này chỉ đúng khi tất cả các trọng số cạnh đều không âm.
3.2. Cách thuật toán Bellman Ford xử lý trọng số âm hiệu quả
Thuật toán Bellman-Ford có cách tiếp cận khác biệt. Thay vì chọn đỉnh tốt nhất ở mỗi bước, nó lặp lại việc cập nhật khoảng cách cho tất cả các cạnh trong đồ thị. Cụ thể, thuật toán lặp lại quá trình này |V| - 1 lần, trong đó |V| là số đỉnh. Sau i lần lặp, thuật toán đảm bảo tìm thấy đường đi ngắn nhất có chứa tối đa i cạnh. Sau |V| - 1 lần lặp, nó sẽ tìm được tất cả các đường đi ngắn nhất. Nếu ở lần lặp thứ |V|, khoảng cách vẫn còn có thể được cải thiện, điều đó chứng tỏ đồ thị chứa một chu trình âm. Khả năng xử lý trọng số âm và phát hiện chu trình âm làm cho Bellman-Ford trở thành một công cụ mạnh mẽ và an toàn hơn Dijkstra trong nhiều trường hợp.
3.3. So sánh hiệu quả giữa hai thuật toán tìm đường đi phổ biến
Về hiệu quả, thuật toán Dijkstra, khi được triển khai với hàng đợi ưu tiên (priority queue), thường có độ phức tạp là O(E + V log V), nhanh hơn đáng kể so với độ phức tạp O(V * E) của thuật toán Bellman-Ford. Do đó, đối với các đồ thị lớn không có cạnh âm, Dijkstra luôn là lựa chọn ưu tiên. Tuy nhiên, Bellman-Ford lại vượt trội về tính tổng quát. Nó không chỉ áp dụng được cho các đồ thị có cạnh âm mà còn là nền tảng cho các thuật toán định tuyến trong các giao thức mạng phức tạp như RIP (Routing Information Protocol). Luận văn đã nhấn mạnh việc hiểu rõ các điều kiện của bài toán là yếu tố then chốt để lựa chọn thuật toán phù hợp.
IV. Giải pháp toàn diện từ thuật toán Floyd Warshall trong luận văn
Trong khi Dijkstra và Bellman-Ford giải quyết bài toán từ một nguồn duy nhất, luận văn đã dành sự quan tâm đặc biệt đến thuật toán Floyd-Warshall (thường được gọi là thuật toán Floyd), một giải pháp toàn diện cho bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh (all-pairs shortest path). Đây là thuật toán được chọn để xây dựng ứng dụng minh họa trong Chương 3, cho thấy tầm quan trọng của nó trong nghiên cứu. Thuật toán Floyd-Warshall hoạt động dựa trên nguyên tắc quy hoạch động, một kỹ thuật mạnh mẽ trong khoa học máy tính. Ý tưởng cốt lõi là xây dựng lời giải một cách tuần tự. Thuật toán xem xét tất cả các đỉnh trong đồ thị lần lượt như những đỉnh trung gian tiềm năng. Với mỗi đỉnh trung gian k được thêm vào, nó kiểm tra xem việc đi qua k có tạo ra một đường đi ngắn hơn giữa hai đỉnh i và j bất kỳ hay không. Bằng cách lặp qua tất cả các đỉnh trung gian, thuật toán đảm bảo sẽ tìm ra đường đi ngắn nhất tuyệt đối giữa mọi cặp đỉnh. Phương pháp này đặc biệt hữu ích trong các ứng dụng cần truy vấn khoảng cách giữa nhiều cặp điểm khác nhau, chẳng hạn như trong việc tính toán ma trận khoảng cách cho các thành phố hoặc các nút mạng.
4.1. Phát biểu bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh
Bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh yêu cầu tìm ra chi phí nhỏ nhất để di chuyển từ đỉnh i đến đỉnh j với mọi cặp (i, j) trong đồ thị. Thay vì chạy |V| lần thuật toán Dijkstra hoặc Bellman-Ford từ mỗi đỉnh, thuật toán Floyd-Warshall cung cấp một phương pháp duy nhất, thanh lịch để giải quyết vấn đề này. Kết quả của thuật toán thường là một ma trận khoảng cách, trong đó phần tử D[i][j] lưu trữ độ dài đường đi ngắn nhất từ i đến j. Điều này rất tiện lợi cho các hệ thống cần tra cứu khoảng cách nhanh chóng mà không cần tính toán lại.
4.2. Triển khai thuật toán Floyd qua ma trận kề trong luận văn
Luận văn mô tả chi tiết cách triển khai thuật toán Floyd-Warshall bằng cách sử dụng ma trận kề. Ban đầu, ma trận khoảng cách D được khởi tạo bằng chính ma trận trọng số của đồ thị. Sau đó, thuật toán thực hiện ba vòng lặp lồng nhau: vòng lặp ngoài cùng k duyệt qua các đỉnh trung gian từ 1 đến n, hai vòng lặp bên trong i và j duyệt qua tất cả các cặp đỉnh nguồn và đích. Tại mỗi bước, nó cập nhật khoảng cách theo công thức D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Sự đơn giản trong logic cài đặt là một trong những ưu điểm lớn của thuật toán này, làm cho nó dễ hiểu và dễ áp dụng.
4.3. Đánh giá độ phức tạp và ưu điểm của thuật toán Floyd Warshall
Ưu điểm lớn nhất của thuật toán Floyd-Warshall là khả năng tìm ra tất cả các đường đi ngắn nhất chỉ trong một lần chạy và sự đơn giản trong việc cài đặt. Nó cũng có thể xử lý các đồ thị có trọng số âm, miễn là không có chu trình âm. Tuy nhiên, nhược điểm chính của nó là độ phức tạp tính toán khá cao, luôn là O(V³), bất kể cấu trúc của đồ thị. Điều này làm cho nó không phù hợp với các đồ thị rất lớn và thưa (sparse graphs), nơi các thuật toán như Johnson's algorithm hoặc chạy Dijkstra nhiều lần có thể hiệu quả hơn. Luận văn đã chọn thuật toán này cho ứng dụng demo vì sự rõ ràng và tính toàn diện của nó.
V. Xây dựng ứng dụng lý thuyết đồ thị từ luận văn ĐH Quảng Nam
Điểm sáng và là đóng góp thực tiễn nhất của luận văn thạc sĩ này (mặc dù là khóa luận tốt nghiệp) chính là Chương 3: Xây dựng ứng dụng. Phần này đã biến những khái niệm trừu tượng của lý thuyết đồ thị thành một sản phẩm phần mềm trực quan. Tác giả đã sử dụng ngôn ngữ lập trình C# và bộ công cụ Microsoft Visual Studio 2010 để tạo ra một chương trình demo cho thuật toán Floyd-Warshall. Ứng dụng này cho phép người dùng tương tác trực tiếp với đồ thị: tạo các đỉnh, vẽ các cạnh nối giữa chúng, và gán trọng số cho từng cạnh. Sau khi đồ thị được xây dựng, người dùng có thể chọn một cặp đỉnh bất kỳ và chương trình sẽ tính toán, sau đó tô màu và hiển thị đường đi ngắn nhất giữa chúng. Việc trực quan hóa này không chỉ giúp kiểm chứng tính đúng đắn của thuật toán mà còn mang lại một công cụ học tập hiệu quả. Nó cho thấy cách các cấu trúc dữ liệu và giải thuật được áp dụng để giải quyết một bài toán tìm đường đi ngắn nhất cụ thể, làm cầu nối vững chắc giữa lý thuyết hàn lâm và ứng dụng của lý thuyết đồ thị trong thực tế.
5.1. Mô hình hóa bài toán bằng ngôn ngữ lập trình C
Để xây dựng ứng dụng, tác giả đã thiết kế một cấu trúc hướng đối tượng rõ ràng. Luận văn mô tả việc tạo ra các lớp (class) cốt lõi như Node để biểu diễn đỉnh, Edge để biểu diễn cạnh, và Matrix để quản lý ma trận kề và thực thi thuật toán Floyd-Warshall. Lớp Node xử lý việc vẽ và tương tác với các đỉnh trên giao diện. Lớp Matrix không chỉ lưu trữ dữ liệu trọng số mà còn chứa logic tính toán cốt lõi của thuật toán. Cách tiếp cận này thể hiện tư duy lập trình tốt, giúp mã nguồn trở nên dễ quản lý, bảo trì và mở rộng, một kỹ năng quan trọng trong ngành khoa học máy tính.
5.2. Kết quả demo và ứng dụng của lý thuyết đồ thị trong thực tế
Hình ảnh chương trình demo trong luận văn (Hình 12) cho thấy một giao diện người dùng đơn giản nhưng đầy đủ chức năng. Người dùng có thể chọn đỉnh bắt đầu và đỉnh kết thúc từ các combobox, sau đó nhấn nút "Đường đi ngắn nhất" để xem kết quả. Chương trình sẽ làm nổi bật đường đi tìm được trên đồ thị. Kết quả này chứng minh rằng lý thuyết đã được áp dụng thành công. Các ứng dụng của lý thuyết đồ thị không chỉ giới hạn trong môi trường học thuật mà còn rất phổ biến trong thực tế: từ các hệ thống định vị GPS, thuật toán định tuyến trong mạng máy tính, đến việc lập kế hoạch vận tải và logistics.
5.3. Tiềm năng tối ưu hóa mạng lưới giao thông và viễn thông
Mặc dù ứng dụng demo có quy mô nhỏ, nó đã minh họa cho một nguyên tắc có thể áp dụng trên các hệ thống lớn hơn rất nhiều. Trong tối ưu hóa mạng lưới giao thông, các giao lộ là đỉnh và các con đường là cạnh với trọng số là khoảng cách hoặc thời gian di chuyển. Việc tìm đường đi ngắn nhất giúp các ứng dụng bản đồ chỉ đường cho người dùng. Trong mạng viễn thông, các router là đỉnh và kết nối mạng là cạnh, việc tìm đường đi ngắn nhất (ít trễ nhất) giúp tối ưu hóa luồng dữ liệu, đảm bảo tốc độ truyền tải nhanh và ổn định. Nghiên cứu tại Đại học Quảng Nam này đã đặt một viên gạch nền tảng cho việc hiểu và áp dụng các nguyên tắc này.
VI. Kết luận tương lai cho ứng dụng lý thuyết đồ thị
Tổng kết lại, khóa luận tốt nghiệp của Phongsavath Chanthavong là một công trình nghiên cứu toàn diện và có giá trị, thành công trong việc kết nối lý thuyết đồ thị với ứng dụng thực tiễn. Luận văn đã hệ thống hóa một cách bài bản các khái niệm nền tảng, đi sâu phân tích các thuật toán tìm đường đi ngắn nhất tiêu biểu và minh họa thành công bằng một ứng dụng cụ thể. Công trình này không chỉ cho thấy năng lực nghiên cứu của sinh viên mà còn khẳng định tầm quan trọng của lý thuyết đồ thị như một công cụ không thể thiếu trong khoa học máy tính và các ngành liên quan. Nhìn về tương lai, lĩnh vực tìm đường đi và tối ưu hóa mạng lưới vẫn còn rất nhiều tiềm năng để phát triển. Các thuật toán hiện tại vẫn có thể được cải tiến để xử lý các đồ thị có quy mô cực lớn hoặc các đồ thị động (dynamic graphs) nơi trọng số cạnh thay đổi theo thời gian. Hơn nữa, việc tích hợp các yếu tố Heuristics vào thuật toán để tìm kiếm thông minh hơn cũng là một hướng đi đầy hứa hẹn, mở ra những giải pháp tối ưu hơn cho các bài toán ngày càng phức tạp trong thế giới thực.
6.1. Tóm tắt giá trị nghiên cứu của khóa luận tốt nghiệp này
Giá trị cốt lõi của luận văn nằm ở ba điểm chính. Thứ nhất, nó là một tài liệu chuyên ngành CNTT có chất lượng, tổng hợp kiến thức một cách rõ ràng, phù hợp cho việc tham khảo và học tập. Thứ hai, nó cung cấp một sự so sánh, đánh giá khách quan giữa các thuật toán phổ biến, giúp người đọc hiểu được điểm mạnh, yếu của từng phương pháp. Cuối cùng, việc xây dựng thành công ứng dụng demo đã chứng minh tính ứng dụng cao của lý thuyết, là một minh chứng thuyết phục về khả năng giải quyết vấn đề của lý thuyết đồ thị.
6.2. Hướng phát triển các thuật toán tìm đường đi như A
Trong khi luận văn tập trung vào các thuật toán kinh điển, hướng phát triển trong tương lai có thể khám phá các thuật toán tiên tiến hơn. Thuật toán A* (A-star) là một ví dụ điển hình. Đây là một thuật toán tìm kiếm thông minh, một biến thể của thuật toán Dijkstra, nhưng được cải tiến bằng cách sử dụng một hàm Heuristic (ước tính) để ưu tiên các đỉnh có vẻ gần với đích hơn. Điều này giúp A* tìm ra đường đi nhanh hơn đáng kể trong nhiều trường hợp, đặc biệt trong các ứng dụng như tìm đường trong game, robot tự hành hay các bài toán quy hoạch lộ trình phức tạp.
