Nhóm nghiên cứu của Đại học Thanh Hoa (Tsinghua University) đã hợp tác với Đại học Stanford và đạt được bước tiến lớn về mặt độ phức tạp tính toán đối với bài toán đường đi ngắn nhất truyền thống (single-source shortest path, SSSP). Nghiên cứu này đã giành giải Best Paper tại hội nghị STOC 2025.
Phương pháp được dùng phổ biến theo truyền thống là thuật toán Dijkstra, với độ phức tạp thời gian có dạng O(m + n log n) (n = số nút, m = số cạnh).
Hạng tử log n liên quan đến hàng đợi ưu tiên (priority queue) hoặc sắp xếp (sorting), và trong 40 năm qua chưa có cải tiến nào vượt qua được phần này.
Thuật toán mới đã giảm độ phức tạp thời gian xuống O(m · log^(2/3) n).
Vì log^(2/3) n tăng chậm hơn log n (tức là tăng ít hơn log n), nên khi số lượng nút rất lớn, khác biệt sẽ trở nên đáng kể.
18 bình luận
Nhớ lại kỷ niệm (?) hồi cuối những năm 2000 khi làm ở một công ty phần mềm dẫn đường cho xe cộ và phát triển mô-đun tìm đường. Dijkstra quá chậm để dùng cho tìm đường trên hệ thống dẫn đường, nên người ta không dùng mà dùng A*(A Star), phiên bản cải tiến dựa trên heuristic. Tìm hiểu mới biết A* không phải là thuật toán SSSP mà là thuật toán SPSP(Single-Pair Shortest Path).
Trong trường hợp sparse, có vẻ hơi khó nói là nó đã vượt qua các thuật toán nhanh hiện có.
CLRS mới được chỉnh sửa chưa lâu mà, giờ lại in bản mới à
Cảm giác như The Beatles hay Oasis, những ban nhạc đã xuất hiện từ lâu và vẫn nổi tiếng cho đến nay, bất ngờ ra album mới sau 41 năm vậy. Trước hết là thấy ngạc nhiên và khơi dậy sự hứng thú haha
Có khi Mỹ đã có từ trước rồi cũng nên? run run run
Đẹp thật kinh khủng
Dạo này Trung Quốc đang bứt phá thật.
Không biết tên thuật toán sẽ được đặt như thế nào nhỉ
Chắc sắp có ai đó ra đề trên Baekjoon với đúng các ràng buộc đó rồi đây, hồi hộp quá.
Dijkstra đầy hoài niệm..
Wow... đỉnh thật...
Thật tuyệt.
Wow......
Cái này cũng làm được nhỉ...
Chà~~
Chà...
Có lẽ nội dung môn học thuật toán sẽ được bổ sung rồi đây, haha
Trời ơi...