Nhóm nghiên cứu ETH Zurich phát triển thuật toán luồng nhanh nhất có thể

 (ethz.ch)
1 điểm bởi GN⁺ 2024-06-30 | 1 bình luận | Chia sẻ qua WhatsApp
  • Nhóm nghiên cứu của Rasmus Kyng tại ETH Zurich đã phát triển một thuật toán tính toán bài toán tìm luồng cực đại trong mạng và tối thiểu hóa chi phí vận chuyển với tốc độ gần chạm tới giới hạn toán học
  • Thuật toán mới sử dụng cách tiếp cận thời gian gần tuyến tính, cho ra đáp án với quy mô thời gian gần tương đương với việc đọc dữ liệu mạng, và có thể áp dụng cho các phép tính trên mạng như đường sắt, đường bộ, đường thủy và Internet
  • Trước đây, nếu gọi số lượng kết nối là m, thì cho đến trước năm 2000 tốc độ chỉ đạt mức m^1.5, và đến năm 2004 là khoảng m^1.33, nhưng cách tiếp cận của Kyng đã hạ thời gian tính toán bổ sung sau khi đọc dữ liệu xuống mức có thể xem như không đáng kể
  • Nhóm nghiên cứu còn tính được đường đi ngắn nhất và luồng cực đại chi phí tối thiểu trong đồ thị tăng dần có thêm kết nối và đồ thị suy giảm có xóa kết nối, không chỉ với mạng tĩnh có hướng, cũng trong thời gian gần tuyến tính
  • Đây là nền tảng để nhanh chóng tính lại tuyến tối ưu trong các tình huống mạng thực tế thay đổi, như việc đóng cửa rồi mở lại một phần đường hầm Gotthard Base Tunnel hay vụ sạt lở trên cao tốc A13

Tính bài toán luồng mạng với tốc độ gần giới hạn

  • Thuật toán luồng mạng của nhóm Rasmus Kyng xử lý bài toán vừa tìm luồng lớn nhất có thể trong mạng vừa tối thiểu hóa chi phí vận chuyển
  • Một ví dụ tiêu biểu là tìm tuyến đường để vận chuyển nhiều hàng hóa nhất từ Copenhagen đến Milan theo cách nhanh nhất và rẻ nhất có thể
  • Có thể tính được luồng tối ưu chi phí thấp trong các mạng có kết nối và dung lượng như đường sắt, đường bộ, đường thủy và Internet
  • Tốc độ tính toán đã được giảm xuống gần ngang với thời gian máy tính đọc dữ liệu mạng

Vì sao đây là thuật toán “nhanh nhất”

  • Trước đây, thời gian tính luồng tối ưu dài hơn rất nhiều so với thời gian xử lý dữ liệu mạng
  • Mạng càng lớn và phức tạp thì thời gian tính toán cần thiết tăng nhanh hơn cả kích thước của bài toán
  • Cách tiếp cận của Kyng khiến thời gian tính toán và kích thước mạng tăng theo cùng một tỷ lệ
    • Nếu gọi số kết nối trong mạng là m, thì chỉ riêng việc đọc dữ liệu một lần đã mất thời gian m
    • Cho đến trước năm 2000, không có thuật toán nào tính nhanh hơn m^1.5
    • Năm 2004, lượng tính toán cần để giải bài toán đã giảm xuống m^1.33
    • Thuật toán của Kyng hạ thời gian tính bổ sung để đi tới lời giải sau khi đọc dữ liệu xuống mức có thể bỏ qua

Đánh giá và mở rộng của thuật toán thời gian gần tuyến tính

  • Nhóm của Kyng đã công bố một bài báo cách đây 2 năm chứa chứng minh toán học cho khái niệm này
  • Những thuật toán nhanh gần tối ưu như vậy được gọi là thuật toán thời gian gần tuyến tính
  • Daniel A. Spielman ví thuật toán này như một chiếc Porsche vượt qua xe ngựa
  • Bài báo đó đã giành Best Paper Award tại IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
  • Communications of the ACM cũng đã giới thiệu nghiên cứu này, và ban biên tập Quanta chọn thuật toán của Kyng là một trong 10 khám phá hàng đầu của khoa học máy tính năm 2022

Từ mạng tĩnh sang mạng thay đổi

  • Thuật toán ban đầu tập trung vào mạng cố định, tĩnh có hướng kết nối xác định
    • Kết nối có hướng là cấu trúc giống như các tuyến một chiều trong mạng đường phố đô thị
  • Sau đó, nhóm nghiên cứu đã phát triển các thuật toán tính luồng tối ưu cả trong những mạng thay đổi dần theo thời gian
  • Simon Meierhans đã trình bày thuật toán thời gian gần tuyến tính mới tại Annual ACM Symposium on Theory of Computing, STOC, ở Vancouver
    • Thuật toán này giải bài toán luồng cực đại chi phí tối thiểu trong các mạng có thêm kết nối mới
  • Trong bài báo thứ hai được nhận tại IEEE Symposium on Foundations of Computer Science, FOCS, vào tháng 10, nhóm đã phát triển một thuật toán cũng xử lý được việc xóa kết nối
  • Cả hai thuật toán đều xác định đường đi ngắn nhất trong các mạng có thêm hoặc bớt kết nối

Ví dụ về thay đổi trong mạng thực tế

  • Gotthard Base Tunnel ở Thụy Sĩ đã bị đóng hoàn toàn từ mùa hè năm 2023 rồi sau đó mở lại một phần
  • Một phần của cao tốc A13, tuyến thay thế chính cho Gotthard Road Tunnel, gần đây đã bị phá hủy do sạt lở
  • Khi các thay đổi như vậy xảy ra, máy tính, dịch vụ bản đồ trực tuyến và bộ lập kế hoạch tuyến đường phải tính lại kết nối chi phí thấp nhất và ngắn nhất giữa Milan và Copenhagen
  • Thuật toán mới của Kyng tính được tuyến tối ưu trong thời gian gần tuyến tính ngay cả trong các mạng có thêm hoặc xóa kết nối
  • Ngay cả khi có đường tránh hoặc tuyến mới làm phát sinh thêm kết nối, thời gian tính toán bổ sung cũng ở mức có thể xem như không đáng kể

Hai chiến lược cũ và cách kết hợp mới

  • Việc tính luồng mạng đòi hỏi phải phân tích mạng nhiều lần để tìm ra luồng tối ưu và tuyến đường chi phí thấp nhất
  • Trong mỗi vòng lặp, cần xem xét các biến thể như kết nối nào đang mở, kết nối nào đang đóng, hay kết nối nào đã đạt giới hạn dung lượng và bị tắc nghẽn
  • Trước Kyng, các nhà khoa học máy tính chủ yếu dùng một trong hai chiến lược
    • Mô hình mạng đường sắt: ở mỗi vòng lặp, tính toàn bộ một đoạn của mạng nơi luồng giao thông đã thay đổi
    • Mô hình lưới điện: ở mỗi vòng lặp, tính toàn bộ mạng, nhưng dùng giá trị trung bình thống kê cho luồng đã thay đổi trên từng đoạn để tăng tốc tính toán
  • Nhóm của Kyng đã kết hợp ưu điểm của cả hai chiến lược để tạo ra một cách tiếp cận kết hợp mới
  • Maximilian Probst Gutenberg cho rằng việc ghép nhiều bước tính toán nhỏ, hiệu quả và chi phí thấp sẽ nhanh hơn nhiều so với chỉ dùng vài bước lớn

Bối cảnh lịch sử của thuật toán luồng

  • Bài toán luồng mạng là một trong những bài toán đầu tiên được giải một cách có hệ thống bằng thuật toán vào thập niên 1950
  • Các thuật toán luồng đã đóng vai trò quan trọng trong việc đưa khoa học máy tính lý thuyết trở thành một lĩnh vực nghiên cứu độc lập
  • Thuật toán nổi tiếng của Lester R. Ford Jr. và Delbert R. Fulkerson cũng ra đời trong giai đoạn này
  • Thuật toán Ford-Fulkerson giải hiệu quả bài toán luồng cực đại là vận chuyển nhiều hàng hóa nhất có thể qua mạng mà không vượt quá dung lượng của từng tuyến
  • Nghiên cứu sau đó cho thấy bài toán luồng cực đại, bài toán chi phí tối thiểu và nhiều bài toán luồng mạng khác là các trường hợp đặc biệt của bài toán luồng chi phí tối thiểu tổng quát

Giới hạn của các thuật toán cũ và bước ngoặt năm 2004

  • Trước nghiên cứu của Kyng, nhiều thuật toán có thể giải hiệu quả một bài toán cụ thể nhưng vẫn chưa đủ nhanh và khó mở rộng sang bài toán luồng chi phí tối thiểu rộng hơn
  • John Edward Hopcroft, Richard Manning Karp và Robert Endre Tarjan, những người tạo ra các thuật toán luồng tiên phong trong thập niên 1970, đều đã nhận Turing Award
    • Karp nhận giải năm 1985
    • Hopcroft và Tarjan nhận giải năm 1986
  • Năm 2004, Daniel Spielman, Shang-Hua Teng, và sau đó là Samuel Daitch, đã xây dựng các thuật toán cung cấp lời giải nhanh và hiệu quả cho cả bài toán luồng chi phí tối thiểu
  • Nhóm này đã chuyển góc nhìn từ đường sắt sang dòng điện trong lưới điện
  • Trong lưới điện, dòng điện có thể được chuyển hướng một phần qua các kết nối vốn đã có dòng điện chạy qua
  • Kyng không đi theo nguyên xi cách tiếp cận thuật toán mạnh cho toàn bộ mạng của Spielman, mà áp dụng ý tưởng tính toán đường đi cục bộ vào cách tiếp cận trước đó của Hopcroft và Karp
  • Việc tính các đường đi cục bộ ở mỗi vòng lặp đóng vai trò lớn trong việc tăng tốc tính toàn bộ luồng

Công cụ toán học mới và cấu trúc dữ liệu

  • Tiến triển của nhóm ETH Zurich không chỉ dựa trên thuật toán mới mà còn dựa trên việc thiết kế các công cụ toán học giúp tăng tốc tính toán hơn nữa
  • Nhóm đã phát triển một cấu trúc dữ liệu mới để tổ chức dữ liệu mạng
  • Cấu trúc dữ liệu này cho phép xác định rất nhanh các thay đổi trong kết nối mạng
  • Việc nhận diện thay đổi nhanh là một yếu tố giúp tăng tốc lời giải của thuật toán
  • Các thuật toán thời gian gần tuyến tính và cấu trúc dữ liệu mới đặt nền móng cho việc giải những bài toán rất lớn mà trước đây không thể tính hiệu quả

Các bài báo và tài liệu liên quan

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-06-30
Ý kiến trên Hacker News

  • Thuật toán này gần như tuyến tính về mặt tiệm cận trong giới hạn n -> inf
    Ở cuối video có nói rằng bất kỳ triển khai nào của thuật toán này trong thế giới thực cũng khó mà thắng được các thuật toán hiện có
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • Vậy đây lại là một thuật toán thiên hà nữa à?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • Sau khi phần đầu tạo kỳ vọng rất cao thì khá là hụt hẫng
    • Vừa nhìn thấy tiêu đề là tôi đã rất hoài nghi
      Cụm tốc độ nhanh nhất có thể là một tuyên bố thật sự táo bạo
    • Một dấu hiệu khác trong những trường hợp này là gần như cần nghiệm tối ưu tuyệt đối
      Dùng chỉ 1% thời gian để đạt 99% chất lượng thường thực tế hơn nhiều

  • Thú vị là cùng người đó cũng nghiên cứu cách biến các thuật toán chỉ dành cho lý thuyết thành thứ thực sự chạy tốt [1]
    Tuy vậy, quá trình đó có vẻ cũng mất khoảng 20 năm nữa. [1] được xây trên đột phá lý thuyết năm 2004 [2], và theo tôi hiểu thì các thuật toán này mãi đến năm 2024 mới bắt đầu hoạt động trong thực tế. Nếu vậy, có lẽ ta có thể kỳ vọng một thuật toán luồng chi phí tối thiểu thực dụng vào năm 2044
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    Đi từ O(mn) xuống O(m) nghĩa là loại N, tức số đỉnh, ra khỏi phép tính; như vậy chẳng phải tốt đến mức khó tin sao?

    • Hệ số hằng số quá lớn, nên với các đầu vào thực tế nó sẽ chậm hơn những thuật toán hiện có dù có tiệm cận tệ hơn
      Dù vậy về mặt lý thuyết thì đây là một kết quả rất hay

  • Chỉ nhìn các con số thô cũng thấy chúng ta đã đi xa đến đâu. Trước thập niên 2000, không thuật toán nào có thể tính nhanh hơn m1.5. Ở đây m là số kết nối mạng mà máy tính phải tính toán, và chỉ riêng việc đọc dữ liệu mạng một lần đã mất thời gian m. Năm 2004, tốc độ tính toán cần thiết để giải bài toán này giảm xuống m1.33. Với thuật toán của Kyng, sau khi đọc dữ liệu mạng, thời gian tính toán “bổ sung” cần để đi tới nghiệm giờ đây là không đáng kể.
    Bài gốc không giải thích đột phá của Kyng theo góc nhìn chỉ số m mà họ xem là quan trọng như vậy, nên tôi thắc mắc vì sao

  • Đôi khi tôi cảm thấy chúng ta đã hoàn toàn lạc lối khi lấy độ phức tạp làm thước đo
    Ngày càng có nhiều thuật toán tối ưu chỉ số độ phức tạp đến mức điên rồ nhưng thực tế lại không hữu ích

    • Hiện tượng đó đã có từ nhiều thập kỷ trước
      Sau khi các thành quả dễ đạt đã hết, nghiên cứu thuật toán trở thành một lĩnh vực chuyên môn hóa cao khác, và nếu không phải là nhà nghiên cứu trong lĩnh vực rất gần thì đa số bài báo không đáng để bỏ nhiều thời gian

  • Bài liên quan: https://news.ycombinator.com/item?id=31149038 (40 bình luận)
    https://news.ycombinator.com/item?id=31675015 (72 bình luận)

  • Bài báo hoặc code ở đâu?

  • Có chỗ tôi thấy khó hiểu: o(n) có vẻ là một mệnh đề mạnh hơn O(n)
    Vì mọi thuật toán o(n) đều là O(n), nhưng chiều ngược lại thì không đúng. Ngoài ra nếu o(n) áp dụng cho cả n nhỏ đến đâu đi nữa, còn O(n) chỉ áp dụng khi n -> inf, thì chẳng phải thuật toán này cũng phải áp dụng được cho n nhỏ sao? Vậy chẳng phải nó phải là đối lập với thuật toán thiên hà nói ở trên à? Tôi đang bỏ sót điều gì sao?

    • Ký hiệu o nhỏ vẫn là một mệnh đề tiệm cận, nên không cần áp dụng cho n nhỏ
      Định nghĩa f(n) = o(g(n)) đại khái là lim (n -> infinity) f(n)/g(n) = 0. Nói cách khác, với n đủ lớn, g tăng nhanh hơn f
      Ví dụ một hàm như f(n) = 10n if n < 1000 else 1e1000 là o(n). Vì khi n lớn lên, 1e1000/n tiến về 0. Đây là cách viết giả Python cho một hàm từng đoạn tăng theo hàm mũ đến 101000 khi n = 1000, rồi sau đó giữ nguyên là hằng số
    • Nếu độ phức tạp thuật toán là 3↑↑64*n^0.999 thì thuật toán đó là o(n), nhưng cứ yên tâm gọi nó là thuật toán thiên hà cũng được

  • Nếu tôi nhớ đúng thì 3↑↑64 là số Graham

  • Chết tiệt mấy hệ số hằng số này, làm tôi muốn giơ nắm đấm lên trời

  • Phần tóm tắt chỉ nói thời gian là m^(1+o(1))
    Có ai biết cận trên cụ thể hơn được nêu ở đâu không?

    • Ở đây o là o nhỏ, nên nó bắt lấy một hạng mà “giá trị chia cho 1” tiến về 0 khi m tiến tới vô hạn
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • Nghĩa là có thể chọn hằng số để đưa nó gần O(m) tùy ý
      Nói cách khác, đây là một sơ đồ thuật toán cho phép nhận được thuật toán chạy trong thời gian O(m^ɛ) với mọi ɛ>1 tùy ý
    • Đó chính là cận trên cụ thể rồi
      o nhỏ là một hàm tiến gần 0 khi n tiến tới vô hạn, và được gọi là không đáng kể về mặt tiệm cận