Trong hơn nửa thế kỷ, các nhà nghiên cứu trên khắp thế giới đã phải vật lộn với một vấn đề thuật toán được gọi là “bài toán đường đi ngắn nhất từ nguồn duy nhất”. Về cơ bản, vấn đề là làm thế nào để đưa ra một công thức toán học tìm ra con đường ngắn nhất tốt nhất giữa một nút và tất cả các nút khác trong mạng, nơi có thể có các kết nối có trọng số âm.
Nghe có vẻ phức tạp? Có khả năng. Nhưng trên thực tế, kiểu tính toán này đã được sử dụng trong nhiều loại ứng dụng và công nghệ mà chúng ta dựa vào để tìm đường — chẳng hạn như Google Maps hướng dẫn chúng ta qua các phong cảnh và qua các thành phố.
Giờ đây, các nhà nghiên cứu từ Khoa Khoa học Máy tính của Đại học Copenhagen đã thành công trong việc giải bài toán đường đi ngắn nhất từ nguồn duy nhất, một câu đố đã làm đau đầu các nhà nghiên cứu và chuyên gia trong nhiều thập kỷ.
>> Tham khảo: Thiết bị điện tử giống như da có thể theo dõi sức khỏe của bạn liên tục.
“Chúng tôi đã phát hiện ra một thuật toán giải quyết vấn đề trong thời gian hầu như tuyến tính, theo cách nhanh nhất có thể. Đây là một vấn đề thuật toán cơ bản đã được nghiên cứu từ những năm 1950 và được giảng dạy trên khắp thế giới. Đây là một trong những lý do thôi thúc chúng tôi giải quyết nó,” phó giáo sư Christian Wulff-Nilsen giải thích, người rõ ràng thấy khó khăn khi để một vấn đề thuật toán chưa được giải quyết một mình.
Tính toán nhanh hơn để định tuyến ô tô điện
Năm ngoái, Wulff-Nilsen đã tạo ra một bước đột phá khác trong cùng lĩnh vực, một bước đột phá tạo ra kết quả giải quyết cách tìm đường đi ngắn nhất trong một mạng thay đổi theo thời gian. Giải pháp của anh ấy cho câu đố gần đây được xây dựng dựa trên công việc đó.
Nhà nghiên cứu cho rằng việc giải bài toán đường đi ngắn nhất từ một nguồn duy nhất có thể mở đường cho các thuật toán không chỉ giúp ô tô điện tính toán lộ trình nhanh nhất từ A đến B ngay lập tức mà còn thực hiện theo cách tiết kiệm năng lượng nhất.
“Chúng tôi đang thêm một thứ nguyên mà các thuật toán trước đây không có. Thứ nguyên này cho phép chúng tôi xem xét cái mà chúng tôi gọi là trọng số âm. Một ví dụ thực tế về điều này có thể là tham chiếu đến những ngọn đồi trong mạng lưới đường bộ, điều này thật tốt nếu biết nếu bạn có một chiếc ô tô điện sạc khi đang xuống dốc,” Wulff-Nilsen giải thích.
>> Tham khảo: Các nhà vật lý tìm ra cách mới để đo tính chất của lớp bề mặt vật liệu.
Sự thật về vấn đề đường dẫn ngắn nhất nguồn duy nhất
- Mục đích của bài toán đường đi ngắn nhất nguồn đơn là tìm các đường đi ngắn nhất từ một nút bắt đầu cho trước đến tất cả các nút khác trong mạng.
- Mạng được biểu diễn dưới dạng biểu đồ bao gồm các nút và kết nối giữa chúng, được gọi là các cạnh.
- Mỗi cạnh có một hướng (ví dụ: điều này có thể được sử dụng để biểu thị đường một chiều), cũng như trọng số, biểu thị mức độ tốn kém khi di chuyển dọc theo cạnh đó. Nếu tất cả các trọng số cạnh là không âm, vấn đề có thể được giải quyết trong thời gian hầu như tuyến tính bằng thuật toán Dijkstra cổ điển.
- Kết quả mới giải quyết vấn đề trong khoảng thời gian gần bằng thuật toán Dijkstra, nhưng cũng cho phép trọng số cạnh âm.
“Về nguyên tắc, thuật toán có thể được sử dụng để cảnh báo các tác nhân, chẳng hạn như ngân hàng trung ương, nếu các nhà đầu cơ đang đầu cơ mua và bán các loại tiền tệ khác nhau. Rất nhiều điều này xảy ra khi sử dụng máy tính ngày nay.
Nhưng vì thuật toán của chúng tôi quá nhanh nên nó có thể được sử dụng để phát hiện sơ hở trước khi chúng bị khai thác,” Christian Wulff-Nilsen nói.
>> Tham khảo: Để ngăn chặn đại dịch tiếp theo, hãy khôi phục môi trường sống của động vật hoang dã.
Nhà nghiên cứu nhấn mạnh rằng các hệ thống tính toán cả tiền tệ và lộ trình cho ô tô điện đã tồn tại. Nhưng việc giải bài toán đường đi ngắn nhất từ một nguồn duy nhất đã cho phép các nhà nghiên cứu tạo ra một thuật toán tuyệt vời hầu như không thể bị đánh bại về mặt tốc độ. Đồng thời, tính đơn giản của nó giúp dễ dàng áp dụng cho các nhu cầu khác nhau của xã hội.
Được vinh danh tại Mỹ
Công việc để giải quyết vấn đề đã không được chú ý. Thật vậy, Christian Wulff-Nilsen và các đồng nghiệp của ông đã được mọi người trên khắp thế giới liên hệ để chúc mừng họ và tìm hiểu thêm về cách họ đã làm được điều đó.
Đồng thời, bài báo nghiên cứu trình bày chi tiết khám phá của họ đã được vinh danh với “giải thưởng bài báo hay nhất” tại hội nghị FOCS (Quỹ Khoa học Máy tính) ở Denver, Colorado. Cùng với STOC, đây là hội nghị uy tín nhất về khoa học máy tính lý thuyết. Hội nghị FOCS diễn ra từ ngày 31 tháng 10 đến ngày 3 tháng 11 năm 2022.
Christian Wulff-Nilsen nói: “Mọi người từ khắp nơi trên thế giới tham dự hội nghị này để xem những kết quả tốt nhất được trình bày.
>> Tham khảo: Phương pháp thống kê mới cải thiện phân tích bộ gen.
Nghiên cứu được thực hiện với sự hợp tác giữa Christian Wulff-Nilsen, từ Khoa Khoa học Máy tính, Danupon Nanongkai của Viện Max Planck và đồng nghiệp người Mỹ của họ, Aaron Bernstein từ Đại học Rutgers.
