Một nhóm nghiên cứu từ Đại học ETH Zurich vừa phát triển một thuật toán dòng chảy mạng lưới có khả năng tính toán siêu nhanh, giúp tối ưu hóa luồng lưu thông trong thời gian thực mà không cần quan tâm đến kích thước hay độ phức tạp của mạng lưới. Đột phá này mở ra tiềm năng ứng dụng trong nhiều lĩnh vực.
Thuật toán dòng chảy mạng lưới là gì?
Mạng lưới trong lý thuyết khoa học máy tính có thể hiểu đơn giản là một hệ thống các điểm nút và các đường kết nối chúng. Mục tiêu của thuật toán dòng chảy mạng lưới là tìm ra cách di chuyển nhiều nhất có thể một lượng hàng hóa hoặc dữ liệu từ điểm này đến điểm kia, trong khi vẫn giữ chi phí thấp nhất. Việc này giống như tìm cách vận chuyển một lượng hàng hóa từ Copenhagen đến Milan qua hệ thống giao thông châu Âu sao cho vừa nhanh vừa rẻ. Thuật toán của nhóm nghiên cứu có thể tính toán điều này cực nhanh, ngay khi máy tính nhận dữ liệu về mạng lưới.
Vượt qua thách thức tính toán lớn
Trước khi có phát minh của Rasmus Kyng và đội ngũ của ông, không ai có thể tính toán nhanh như vậy. Vấn đề tính toán tối ưu cho các mạng lưới lớn luôn làm khó các nhà khoa học trong suốt 90 năm. Trước đây, việc tính toán luôn chậm hơn nhiều so với tốc độ thu thập dữ liệu mạng lưới. Và khi mạng lưới càng phức tạp, thời gian tính toán cũng tăng theo một cách mất cân đối. Điều này dẫn đến các bài toán mạng lưới trở nên quá lớn và không thể tính được trong thời gian thực.
Tốc độ ngang ngửa quy mô mạng lưới
Nhóm của Kyng đã giải quyết được vấn đề này. Thuật toán của họ cho phép tốc độ tính toán và kích thước mạng lưới tăng theo tỷ lệ tương đương nhau. Điều này có nghĩa là dù mạng lưới lớn đến đâu, thời gian tính toán cũng chỉ tăng như bạn đang leo núi với một tốc độ không đổi, bất kể địa hình phức tạp thế nào.
Trước năm 2000, không một thuật toán nào có thể tính toán nhanh hơn thời gian tỉ lệ với số lượng kết nối (kí hiệu là m) trong mạng lưới. Vào năm 2004, thời gian tính toán giảm xuống còn m^1.33. Nhưng với thuật toán của Kyng, thời gian tính toán thêm sau khi đọc dữ liệu mạng hầu như không đáng kể.
Giống như xe Porsche và xe ngựa
Giáo sư Daniel A. Spielman từ Đại học Yale, một người thầy và đồng nghiệp của Kyng, ví von thuật toán mới này nhanh như xe Porsche vượt qua những cỗ xe ngựa. Thuật toán của họ được gọi là “thuật toán thời gian gần như tuyến tính” và đã gây bất ngờ lớn trong cộng đồng khoa học máy tính lý thuyết. Thuật toán của Kyng và nhóm của ông thậm chí đã giành giải thưởng “Best Paper Award” vào năm 2022 tại Hội nghị IEEE về Khoa học Máy tính và được tạp chí khoa học nổi tiếng Quanta liệt kê vào top 10 khám phá quan trọng trong lĩnh vực khoa học máy tính năm 2022.
Tính toán cực nhanh cho mạng lưới động
Thuật toán ban đầu của nhóm nghiên cứu chỉ tập trung vào các mạng lưới tĩnh, nơi các kết nối không thay đổi. Tuy nhiên, họ đã tiếp tục phát triển thuật toán để có thể tính toán luồng tối ưu cho những mạng lưới có thay đổi theo thời gian, như các mạng lưới trong sinh học, hoặc mạng lưới xã hội.
Vào tháng 6 năm 2024, thành viên nhóm nghiên cứu, Simon Meierhans, đã trình bày một thuật toán mới tại Hội nghị ACM Symposium về lý thuyết tính toán (STOC). Thuật toán này giải quyết bài toán dòng chảy với chi phí tối thiểu cho các mạng lưới thay đổi dần dần khi có thêm kết nối mới.
Một ứng dụng thực tế cho những thay đổi trong mạng lưới là mạng giao thông ở Thụy Sĩ. Khi một tuyến đường bị đóng, chẳng hạn như đường hầm Gotthard bị đóng một phần sau vụ lở đất vào năm 2023, thuật toán của Kyng có thể tính toán nhanh nhất đường thay thế giữa Milan và Copenhagen.
Điều gì khiến thuật toán của Kyng đặc biệt?
Tất cả các phương pháp tính toán đều phải phân tích mạng lưới qua nhiều lần lặp lại để tìm ra luồng tối ưu và chi phí thấp nhất. Những thuật toán trước đây phải lựa chọn giữa hai cách tiếp cận chính: một là tính toàn bộ một phần mạng lưới qua mỗi lần lặp lại, hai là tính toàn bộ mạng lưới nhưng dùng các giá trị trung bình để tăng tốc độ.
Thuật toán của Kyng kết hợp ưu điểm của cả hai phương pháp này. Thay vì tính toàn bộ mạng lưới trong một lần, họ thực hiện nhiều bước nhỏ hơn, mỗi bước tốn ít tài nguyên nhưng khi tổng lại thì nhanh hơn nhiều so với cách tính toán lớn.
Từ đường sắt đến mạng điện
Một trong những thành công lớn nhất trong lĩnh vực này trước đây là thuật toán của Lester R. Ford Jr. và Delbert R. Fulkerson vào những năm 1950, giúp giải quyết bài toán dòng chảy tối đa trong mạng lưới. Thuật toán này tìm cách vận chuyển nhiều hàng hóa nhất qua mạng lưới mà không vượt quá khả năng của các tuyến đường.
Nhưng đến năm 2004, các nhà toán học như Daniel Spielman và Shang-Hua Teng đã tạo ra các thuật toán có thể giải quyết bài toán chi phí tối thiểu nhanh hơn bằng cách thay đổi cách nhìn từ mạng lưới đường sắt sang mạng điện. Trên mạng lưới điện, dòng điện có thể chia nhỏ và chảy qua các kết nối khác nhau, điều mà tàu hỏa không thể làm được. Chính sự chuyển đổi này đã tạo ra một bước ngoặt về cách tính toán.
Sự chuyển đổi trong nguyên tắc tính toán
Nhóm nghiên cứu của Kyng không chỉ phát triển thuật toán mới mà còn tạo ra các công cụ toán học mới để tối ưu hóa tốc độ của chúng. Họ đã phát minh ra một cấu trúc dữ liệu giúp tổ chức mạng lưới hiệu quả hơn, cho phép nhận diện các thay đổi trong kết nối mạng lưới một cách cực nhanh. Điều này giúp tăng tốc đáng kể quá trình tính toán.
Thuật toán thời gian gần như tuyến tính của họ không chỉ giải quyết các bài toán lớn một cách hiệu quả mà còn thay đổi cách mà máy tính xử lý những tác vụ phức tạp. Với hàng loạt ứng dụng tiềm năng, những thuật toán này sẽ tiếp tục tạo ra sự phát triển đột phá trong tương lai.
Chú thích:
- Thuật toán dòng chảy mạng lưới (network flow algorithm): Là thuật toán giúp tính toán luồng chảy tối ưu trong một mạng lưới, nhằm vận chuyển hàng hóa hoặc dữ liệu từ điểm này đến điểm kia với chi phí thấp nhất.
- Thời gian gần như tuyến tính (almost-linear-time algorithms): Là các thuật toán có thời gian thực hiện tỷ lệ gần như trực tiếp với kích thước mạng lưới, giúp xử lý các mạng lưới lớn trong thời gian ngắn.
- Dòng chảy tối đa (maximum flow problem): Là bài toán tìm cách di chuyển nhiều nhất có thể hàng hóa qua mạng lưới mà không vượt quá khả năng của các tuyến đường.
Tham khảo:
“Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow” by Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans and Maximilian Probst Gutenberg, 11 June 2024, STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. DOI: 10.1145/3618260.3649745