aidokhongphailatoi
Chịu khó la liếm
Thuật toán Dijkstra - thuật toán kinh điển của sinh viên IT đã có người kế vị sau hơn 65 năm trị vì 🏆
#dev_share #dijkstra
Đối với các sinh viên IT, có lẽ các bạn không còn xa lạ gì với thuật toán Dijkstra - thuật toán kinh điển dành cho bài toán tìm đường đi ngắn nhất (bạn thường sẽ được làm quen với thuật toán kinh điển này trong môn học cũng kinh điển không kém - Cấu trúc dữ liệu & Giải thuật)
Trong nhiều thập kỷ, thuật toán Dijkstra (được tối ưu bởi Robert Tarjan – người đoạt giải Turing) với độ phức tạp thời gian O(m + n log n) được coi là tiêu chuẩn vàng. Trong trường hợp tổng quát (đồ thị có trọng số, có hướng), chưa từng ai vượt qua được mốc này - cho đến bây giờ.
Tuy nhiên gần đây, một nhóm nghiên cứu do Giáo sư Ran Duan tại Đại học Thanh Hoa (Tsinghua University) dẫn đầu đã đạt được điều mà nhiều người cho là bất khả thi: Tìm ra thuật toán nhanh nhất cho bài toán đường đi ngắn nhất trên đồ thị trong nhiều thập kỷ qua, với độ phức tạp là O(m log^(2/3) n)
Tại sao điều này quan trọng?
🔥Bài báo và thuật toán này đã viết lại một chương của lý thuyết thuật toán mà chúng ta tưởng như đã khép lại.
🔥Thuật toán này có thể lan tỏa thành các giải pháp nhanh hơn cho vô số bài toán đồ thị khác.
🔥Chứng minh rằng ngay cả những vấn đề được coi là “đã giải xong” vẫn có thể ẩn chứa những bất ngờ sâu sắc.
Trong thời đại tràn ngập các mô hình AI mới, đây là một lời nhắc nhở: những bước đột phá thật sự trong khoa học máy tính ngày nay không nhất thiết phải đến từ các mô hình ngôn ngữ lớn (LLM) - đôi khi, đó chỉ là nhờ cách tư duy thông minh hơn 😎
Paper: https://arxiv.org/html/2504.17033v2
#dev_share #dijkstra
Đối với các sinh viên IT, có lẽ các bạn không còn xa lạ gì với thuật toán Dijkstra - thuật toán kinh điển dành cho bài toán tìm đường đi ngắn nhất (bạn thường sẽ được làm quen với thuật toán kinh điển này trong môn học cũng kinh điển không kém - Cấu trúc dữ liệu & Giải thuật)
Trong nhiều thập kỷ, thuật toán Dijkstra (được tối ưu bởi Robert Tarjan – người đoạt giải Turing) với độ phức tạp thời gian O(m + n log n) được coi là tiêu chuẩn vàng. Trong trường hợp tổng quát (đồ thị có trọng số, có hướng), chưa từng ai vượt qua được mốc này - cho đến bây giờ.
Tuy nhiên gần đây, một nhóm nghiên cứu do Giáo sư Ran Duan tại Đại học Thanh Hoa (Tsinghua University) dẫn đầu đã đạt được điều mà nhiều người cho là bất khả thi: Tìm ra thuật toán nhanh nhất cho bài toán đường đi ngắn nhất trên đồ thị trong nhiều thập kỷ qua, với độ phức tạp là O(m log^(2/3) n)
Tại sao điều này quan trọng?
🔥Bài báo và thuật toán này đã viết lại một chương của lý thuyết thuật toán mà chúng ta tưởng như đã khép lại.
🔥Thuật toán này có thể lan tỏa thành các giải pháp nhanh hơn cho vô số bài toán đồ thị khác.
🔥Chứng minh rằng ngay cả những vấn đề được coi là “đã giải xong” vẫn có thể ẩn chứa những bất ngờ sâu sắc.
Trong thời đại tràn ngập các mô hình AI mới, đây là một lời nhắc nhở: những bước đột phá thật sự trong khoa học máy tính ngày nay không nhất thiết phải đến từ các mô hình ngôn ngữ lớn (LLM) - đôi khi, đó chỉ là nhờ cách tư duy thông minh hơn 😎
Paper: https://arxiv.org/html/2504.17033v2
