Một trong những thuật toán kinh điển nhất của khoa học máy tính vừa trở thành tâm điểm của một thử nghiệm đáng chú ý về khả năng nghiên cứu tự động của AI. Vals AI cho biết họ đã đưa 10 tác nhân Claude Opus 5.5 vào cùng một môi trường cộng tác và yêu cầu chúng tìm một thuật toán giải bài toán đường đi ngắn nhất nhanh hơn về mặt lý thuyết so với cận quen thuộc của Dijkstra, đồng thời phải xây dựng bằng chứng hình thức bằng Lean.
Sau khoảng 15 giờ và 733 lượt trao đổi trên bảng tin, các tác nhân đã tạo ra một phương pháp có tên C-HD, cùng một gói chứng minh Lean được máy kiểm tra. Vals AI mô tả đây là một cải thiện về cận lý thuyết cho bài toán đường đi ngắn nhất trên đồ thị có hướng với trọng số thực không âm.
Điều đáng chú ý là câu chuyện này không đơn giản là “AI đã đánh bại Dijkstra”. Giá trị lớn hơn nằm ở chỗ các tác nhân AI đã có thể phối hợp, phản biện, thử nghiệm ý tưởng và cuối cùng tạo ra một kết quả toán học có thể được kiểm chứng bằng máy.
Dijkstra – biểu tượng của bài toán đường đi ngắn nhất
Đối với sinh viên khoa học máy tính, Dijkstra là một trong những thuật toán nền tảng khi học về đồ thị và bài toán đường đi ngắn nhất.
Bài toán cơ bản có thể mô tả như sau: cho một đồ thị có hướng gồm nhiều đỉnh và cạnh, mỗi cạnh có trọng số không âm. Từ một đỉnh nguồn, thuật toán phải tìm khoảng cách ngắn nhất đến những đỉnh còn lại, hoặc xác định rằng một đỉnh không thể tiếp cận được.
Edsger W. Dijkstra công bố thuật toán này vào năm 1959. Phương pháp sử dụng chiến lược tham lam: tại mỗi bước, thuật toán chọn đỉnh chưa được xử lý có khoảng cách tạm thời nhỏ nhất, sau đó tiếp tục “thư giãn” các cạnh đi ra từ đỉnh đó.
Với cấu trúc dữ liệu phù hợp, đặc biệt là Fibonacci heap, cận thời gian kinh điển của Dijkstra có thể đạt O(m + n log n), trong đó n là số đỉnh và m là số cạnh.
Trong nhiều thập kỷ, Dijkstra trở thành một chuẩn mực để so sánh các phương pháp giải bài toán đường đi ngắn nhất. Tuy nhiên, “kinh điển” không đồng nghĩa với “không thể cải thiện”.
Năm 2025, nhóm Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu và Longhui Yin công bố một thuật toán có thời gian O(m log^(2/3)n) trong mô hình so sánh-cộng đối với bài toán đường đi ngắn nhất một nguồn trên đồ thị có hướng với trọng số thực không âm. Công trình này được mô tả là lần đầu phá vỡ cận O(m + n log n) của Dijkstra trên các đồ thị thưa trong mô hình nói trên.
Chính bối cảnh đó khiến thử thách mà Vals AI đặt ra cho các tác nhân Claude trở nên đặc biệt.
10 tác nhân Claude Opus 5.5 được giao một nhiệm vụ rất khó
Theo Vals AI, nhóm thử nghiệm gồm 10 tác nhân Claude Opus 5.5 cùng làm việc trên một bảng tin chung.
Mục tiêu không đơn thuần là viết một đoạn chương trình tìm đường đi ngắn nhất.
Các tác nhân phải đáp ứng một loạt yêu cầu nghiêm ngặt:
- Giải chính xác bài toán đường đi ngắn nhất một nguồn trên đồ thị có hướng với trọng số thực không âm.
- Tìm được cải thiện về độ phức tạp lý thuyết.
- Xây dựng bằng chứng toán học có thể kiểm chứng bằng Lean.
- So sánh kết quả với các nghiên cứu tiên tiến trước đó.
- Ghi lại các hướng tiếp cận thất bại để những tác nhân khác không lặp lại.
- Phối hợp giữa nhiều tác nhân thay vì để một mô hình làm toàn bộ công việc đơn lẻ.
Điểm đáng chú ý là các tác nhân không chỉ lần lượt đưa ra câu trả lời rồi kết thúc. Chúng có thể trao đổi trên cùng một môi trường, đặt câu hỏi, phản biện ý tưởng và chuyển hướng công việc khi một hướng nghiên cứu không còn triển vọng.
Vals AI cho biết sau khoảng 15 giờ, hệ thống đã tạo ra 733 lượt trao đổi và đi đến thuật toán C-HD.
Đây chính là phần khiến thử nghiệm trở nên đáng chú ý: AI không chỉ được sử dụng như một công cụ sinh mã mà được đặt trong vai trò của một nhóm nghiên cứu nhỏ.
C-HD khác Dijkstra ở điểm nào?
Dijkstra dựa trên một chiến lược tương đối trực tiếp: duy trì các khoảng cách tạm thời và liên tục chọn đỉnh có khoảng cách nhỏ nhất để xử lý tiếp.
C-HD đi theo một hướng khác.
Theo mô tả của Vals AI, phương pháp này sử dụng một chiến lược phân rã dựa trên heuristic, kết hợp tìm kiếm cục bộ, cây tìm kiếm và các “điểm xoay” để tổ chức công việc đệ quy.
Ý tưởng có thể hình dung ở mức khái quát như sau:
- Bắt đầu từ đỉnh nguồn và phần biên hiện tại của quá trình tìm kiếm.
- Thực hiện tìm kiếm cục bộ giới hạn trên các cạnh đi ra.
- Đưa các đỉnh mới phát hiện vào các ràng buộc của quá trình tìm kiếm.
- Sử dụng cấu trúc cây và các điểm xoay để phân chia công việc thành những phần nhỏ hơn.
- Duy trì các bất biến toán học để bảo đảm rằng quá trình cập nhật không làm mất tính đúng đắn của thuật toán.
Mục tiêu không phải đơn giản hóa Dijkstra mà là thay đổi cách tổ chức công việc trong một số vùng mật độ đồ thị nhất định.
Cận lý thuyết của C-HD mới là điểm đáng chú ý nhất
Theo Vals AI, trong vùng mật độ đồ thị mà bài viết phân tích, C-HD có cận được chứng nhận là:
O(n log^(11/12)n)
Trong khi đó, cận tương ứng của Dijkstra trong phép so sánh được đưa ra là:
O(n log n)
Vals AI cho biết kết quả này tạo ra một cải thiện về cận tiệm cận trong phạm vi đồ thị được xét.
Điểm cần hiểu rõ là sự khác biệt giữa hai biểu thức này mang tính lý thuyết và tiệm cận.
Nó không có nghĩa rằng nếu lấy hai chương trình C-HD và Dijkstra chạy trên một chiếc máy tính hiện nay thì C-HD sẽ hoàn thành nhanh hơn.
Đây là một khác biệt rất quan trọng.
Trong khoa học máy tính lý thuyết, việc giảm số mũ của logarit có thể có ý nghĩa lớn khi kích thước đầu vào tiến tới cực lớn. Nhưng trong triển khai thực tế, các hằng số ẩn trong ký hiệu Big-O, chi phí tiền xử lý, quản lý bộ nhớ và cấu trúc dữ liệu có thể khiến thuật toán có cận lý thuyết tốt hơn vẫn chạy chậm hơn rất nhiều.
Đó cũng chính là vấn đề mà các thử nghiệm triển khai thực tế của những thuật toán đường đi ngắn nhất mới hơn từng cho thấy: cải thiện tiệm cận không tự động biến thành lợi thế về thời gian chạy trên các bộ dữ liệu thực tế.
Lean biến kết quả của AI thành một bài toán có thể kiểm chứng
Một trong những yêu cầu quan trọng nhất của thử nghiệm là AI không được chỉ đưa ra một lập luận bằng ngôn ngữ tự nhiên.
Nó phải chứng minh kết quả bằng Lean, một hệ thống hỗ trợ hình thức hóa và kiểm tra các định lý toán học.
Đây là điểm khác biệt quan trọng giữa một chatbot đưa ra lời giải có vẻ hợp lý và một hệ thống tạo ra một chứng minh có thể được máy kiểm tra.
Trong thử nghiệm, các tác nhân tạo ra một gói mã Lean để mô tả và chứng minh các thuộc tính cần thiết của thuật toán. Vals AI cho biết gói bằng chứng đi kèm với kết quả C-HD và được Lean kiểm tra.
Điều này không đồng nghĩa với việc mọi khía cạnh của tuyên bố khoa học đã được cộng đồng nghiên cứu độc lập xác nhận.
Một bằng chứng Lean có thể xác nhận rằng một mệnh đề hình thức đã được chứng minh từ những giả định và định nghĩa được mã hóa. Nhưng tính mới của thuật toán, cách lựa chọn mô hình tính toán, mức độ phù hợp với các công trình trước đó và ý nghĩa thực tiễn vẫn cần được các nhà nghiên cứu bên ngoài xem xét.
Đây là lý do C-HD nên được nhìn nhận trước hết như một thử nghiệm quan trọng về khả năng nghiên cứu toán học của các tác nhân AI, thay vì xem nó như một thuật toán mới đã sẵn sàng thay thế Dijkstra trong phần mềm thực tế.
Khi lý thuyết gặp thực tế
Một trong những bài học thú vị nhất của câu chuyện C-HD nằm ở khoảng cách giữa toán học và kỹ thuật.
Một thuật toán có cận Big-O tốt hơn vẫn có thể không thắng trong benchmark thực tế.
Chi phí tiền xử lý, cấu trúc dữ liệu phức tạp, truy cập bộ nhớ và các hằng số ẩn có thể áp đảo lợi thế lý thuyết trên những kích thước dữ liệu mà máy tính hiện nay có thể xử lý.
Đây không phải là vấn đề riêng của C-HD. Một nghiên cứu triển khai thuật toán Duan và cộng sự năm 2025 cũng cho thấy thuật toán có cận tiệm cận tốt hơn Dijkstra nhưng trong các thử nghiệm trên đồ thị thưa, Dijkstra vẫn nhanh hơn do các hằng số lớn của phương pháp mới.
Vì vậy, nếu đặt câu hỏi “C-HD có thay thế Dijkstra trong các hệ thống định tuyến hiện nay không?”, câu trả lời từ những thông tin hiện có là chưa có cơ sở để kết luận như vậy.
Giá trị của C-HD nằm ở một tầng khác.
15 giờ có thể nói lên điều gì về AI nghiên cứu?
Trước đây, một nhà nghiên cứu sử dụng máy tính chủ yếu như công cụ hỗ trợ.
Con người đặt câu hỏi, xây dựng giả thuyết, viết mã, chạy thí nghiệm, đọc kết quả rồi tiếp tục điều chỉnh.
Mô hình tác nhân AI đang mở ra một quy trình khác.
Thay vì một mô hình tạo ra một câu trả lời duy nhất, nhiều tác nhân có thể được giao cùng một mục tiêu, chia sẻ kết quả, phản biện lẫn nhau và tiếp tục tìm kiếm trong không gian giải pháp.
Trong trường hợp của Vals AI, 10 tác nhân Claude Opus 5.5 đã hoạt động theo mô hình đó trong khoảng 15 giờ.
Điều này không chứng minh rằng AI đã có thể tự mình thay thế các nhà khoa học.
Nhưng nó cho thấy một khả năng mới: chi phí để khám phá nhiều giả thuyết khác nhau có thể giảm xuống đáng kể khi hàng loạt tác nhân AI cùng hoạt động song song.
Nếu cách tiếp cận này tiếp tục phát triển, những lĩnh vực vốn đòi hỏi rất nhiều thời gian để tìm kiếm không gian giải pháp có thể trở thành ứng viên tự nhiên cho các “phòng thí nghiệm AI”.
Câu hỏi về C-HD
C-HD có thực sự nhanh hơn Dijkstra không?
Không nên hiểu theo nghĩa thời gian chạy trên máy tính. Kết quả của Vals AI cho thấy C-HD đạt được một cải thiện về cận độ phức tạp tiệm cận trong một phạm vi mật độ đồ thị cụ thể. Vals AI đưa ra cận O(n log^(11/12)n), so với O(n log n) của Dijkstra trong vùng phân tích đó.
C-HD có thay thế được Dijkstra không?
Hiện chưa có cơ sở để nói như vậy. Dijkstra vẫn là thuật toán kinh điển, đơn giản và có nhiều triển khai hiệu quả. C-HD chủ yếu đáng chú ý ở kết quả lý thuyết và quy trình nghiên cứu do các tác nhân AI thực hiện.
Vì sao Lean quan trọng trong nghiên cứu này?
Lean cho phép kiểm tra hình thức các mệnh đề toán học và mã hóa các bước chứng minh để kernel kiểm tra. Điều này giúp giảm nguy cơ một lập luận tưởng như hợp lý nhưng chứa lỗi logic mà con người bỏ sót.
Claude Opus 5.5 là gì?
Claude Opus 5.5 là mô hình AI do Anthropic phát hành ngày 22/9/2026. Anthropic cho biết đây là thành viên đầu tiên của dòng Claude 5.5 và có chi phí vận hành thấp hơn Opus 5 khoảng 40%.
Tại sao phát hiện này đáng chú ý nếu C-HD chưa có lợi thế thực tế?
Bởi giá trị của thử nghiệm nằm không chỉ ở bản thân thuật toán. Nó cho thấy nhiều tác nhân AI có thể phối hợp để tìm kiếm một ý tưởng thuật toán mới, xây dựng mã và tạo bằng chứng hình thức trong thời gian tương đối ngắn. Đây là một hướng nghiên cứu có thể ảnh hưởng đến cách con người sử dụng AI trong khoa học máy tính.
AI đang tiến gần hơn tới vai trò “đồng nghiệp nghiên cứu”?
Câu chuyện C-HD có thể được xem như một thử nghiệm nhỏ nhưng đáng chú ý về tương lai của nghiên cứu khoa học.
Trong khoảng 15 giờ, 10 tác nhân Claude Opus 5.5 đã tạo ra hàng trăm lượt trao đổi, khám phá nhiều hướng tiếp cận và đi đến một thuật toán có cận lý thuyết mới trong phạm vi được xét. Vals AI cũng công bố kết quả như một ví dụ về khả năng phối hợp của nhiều tác nhân AI trong nghiên cứu thuật toán.
Nguồn tham khảo
- Vals AI – thông tin về thử nghiệm 10 tác nhân Claude Opus 5.5 và thuật toán C-HD.
- Vals AI – bài viết về C-HD và nghiên cứu đường đi ngắn nhất.
- Anthropic – thông tin phát hành Claude Opus 5.5 ngày 22/9/2026.
- Duan và cộng sự – Breaking the Sorting Barrier for Directed Single-Source Shortest Paths.
- Tài liệu học thuật về Dijkstra và Fibonacci heap.
