Phiên bản gốc của câu chuyện này xuất hiện ở Tạp chí Quanta.
Nếu bạn muốn giải quyết một vấn đề phức tạp, việc tổ chức thường sẽ giúp ích. Ví dụ, bạn có thể chia vấn đề thành nhiều phần và giải quyết những phần dễ nhất trước tiên. Nhưng kiểu phân loại này có chi phí. Cuối cùng, bạn có thể mất quá nhiều thời gian để sắp xếp các phần theo thứ tự.
Vấn đề nan giải này đặc biệt liên quan đến một trong những vấn đề mang tính biểu tượng nhất của khoa học máy tính: tìm đường đi ngắn nhất từ một điểm bắt đầu cụ thể trong mạng đến mọi điểm khác. Nó giống như một phiên bản cải tiến của một vấn đề bạn cần giải quyết mỗi khi di chuyển: tìm hiểu con đường tốt nhất từ nhà mới đến nơi làm việc, phòng tập thể dục và siêu thị.
Mikkel Thorup, một nhà khoa học máy tính tại Đại học Copenhagen cho biết: “Con đường ngắn nhất là một vấn đề hay mà bất kỳ ai trên thế giới cũng có thể liên quan đến”.
Theo trực giác, việc tìm ra con đường ngắn nhất tới các điểm đến gần đó sẽ là cách dễ dàng nhất. Vì vậy, nếu bạn muốn thiết kế thuật toán nhanh nhất có thể cho bài toán đường đi ngắn nhất, có vẻ hợp lý khi bắt đầu bằng cách tìm điểm gần nhất, sau đó là điểm gần nhất tiếp theo, v.v. Nhưng để làm được điều đó, bạn cần phải liên tục tìm ra điểm nào gần nhất. Bạn sẽ sắp xếp các điểm theo khoảng cách khi bạn đi. Có một giới hạn tốc độ cơ bản cho bất kỳ thuật toán nào tuân theo phương pháp này: Bạn không thể nhanh hơn thời gian cần thiết để sắp xếp.
Bốn mươi năm trước, các nhà nghiên cứu thiết kế thuật toán đường đi ngắn nhất đã gặp phải “rào cản sắp xếp” này. Giờ đây, một nhóm các nhà nghiên cứu đã nghĩ ra một thuật toán mới có thể phá vỡ nó. Nó không sắp xếp và chạy nhanh hơn bất kỳ thuật toán nào thực hiện chức năng này.
Robert Tarjan, một nhà khoa học máy tính tại Đại học Princeton cho biết: “Các tác giả đã táo bạo khi nghĩ rằng họ có thể phá vỡ rào cản này”. “Đó là một kết quả tuyệt vời.”
Biên giới của tri thức
Để phân tích bài toán đường đi ngắn nhất về mặt toán học, các nhà nghiên cứu sử dụng ngôn ngữ đồ thị—mạng lưới các điểm hoặc nút, được kết nối bằng các đường thẳng. Mỗi liên kết giữa các nút được gắn nhãn bằng một số gọi là trọng số của nó, có thể biểu thị độ dài của đoạn đó hoặc thời gian cần thiết để đi qua nó. Thường có nhiều tuyến đường giữa hai nút bất kỳ và tuyến đường ngắn nhất là tuyến có tổng trọng số nhỏ nhất. Với một biểu đồ và một nút “nguồn” cụ thể, mục tiêu của thuật toán là tìm đường đi ngắn nhất tới mọi nút khác.
Thuật toán đường đi ngắn nhất nổi tiếng nhất do nhà khoa học máy tính tiên phong Edsger Dijkstra nghĩ ra vào năm 1956, bắt đầu từ nguồn và tiến hành từng bước một. Đó là một cách tiếp cận hiệu quả vì biết đường đi ngắn nhất tới các nút lân cận có thể giúp bạn tìm ra đường đi ngắn nhất đến các nút ở xa hơn. Nhưng vì kết quả cuối cùng là một danh sách được sắp xếp gồm các đường đi ngắn nhất nên rào cản sắp xếp đặt ra giới hạn cơ bản về tốc độ chạy của thuật toán.
