Thuật toán sắp xếp Topo điều phối thứ tự Backward đồ thị DAG (Topological Sort)
Mọi hệ thống Autograd (PyTorch, TensorFlow, Micrograd) đều biểu diễn các phép tính dưới dạng đồ thị có hướng không chu trình (DAG).
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: scalar-autograd-value-engine.
Nội dung đề bài
Mô tả bài toán
Mọi hệ thống Autograd (PyTorch, TensorFlow, Micrograd) đều biểu diễn các phép tính dưới dạng đồ thị có hướng không chu trình (DAG). Để thực hiện lan truyền ngược đúng đắn: Một nút V chỉ được phép thực thi hàm _backward() sau khi TẤT CẢ các nút phụ thuộc vào nó (consumers / downstream nodes) đã tính xong và cộng dồn đầy đủ gradient vào V.grad. Thứ tự này được xác định duy nhất bằng Thuật toán Sắp xếp Topo (Topological Sort):
- Duyệt đồ thị từ nút Loss bằng DFS hoặc thuật toán Kahn.
- Xây dựng danh sách topo sao cho mọi cạnh u → v (nghĩa là v là đầu vào của u) thì u xuất hiện TRƯỚC v trong danh sách duyệt backward.
Hãy viết hàm topological_sort_graph(root_node: dict) -> list[str]:
- Mỗi nút là một dictionary chứa:
{"id": str, "inputs": list[dict]} trong đó inputs là danh sách các nút đầu vào trực tiếp (parents).
- Trả về danh sách chuỗi ID các nút theo thứ tự thực thi Backward chính xác (bắt đầu từ
root_node["id"]). - Mỗi nút chỉ xuất hiện duy nhất 1 lần trong danh sách (không trùng lặp).
Input
- Hàm
topological_sort_graph(root_node): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.
Output
- Hàm
topological_sort_graph: Trả về kết quả kiểuList[str]theo đúng đặc tả kỹ thuật và kích thước quy định.
Ràng buộc
- Thời gian chạy tối đa: 6000ms.
- Giới hạn bộ nhớ: 512MB.
- Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
x = {'id': 'x', 'inputs': []}
a = {'id': 'a', 'inputs': [x]}
b = {'id': 'b', 'inputs': [x]}
loss = {'id': 'loss', 'inputs': [a, b]}
order = topological_sort_graph(loss)Output
['loss', 'b', 'a', 'x']Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Ví dụ 2
Input
x = {'id': 'x', 'inputs': []}
y = {'id': 'y', 'inputs': [x]}
z = {'id': 'z', 'inputs': [y]}
order = topological_sort_graph(z)Output
['z', 'y', 'x']Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.