Một bước cập nhật PageRank
PageRank cho điểm quan trọng của từng trang trong đồ thị có hướng. Một vòng lặp lặp lại
Tiến độ của tôi ở bài này
Điểm và code bạn nộp đượ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: python-basics, graph-basics.
Nội dung đề bài
Mô tả bài toán
PageRank cho điểm quan trọng của từng trang trong đồ thị có hướng. Một vòng lặp lặp lại công thức PR_new(i) = (1 - d) / N + d * tổng_j ( PR(j) / outdeg(j) ), trong đó tổng chạy qua các trang j có cạnh trỏ tới i, outdeg(j) là số cạnh ra của j và d là hệ số giảm.
Yêu cầu
Viết hàm pagerank_update(scores, adjacency, damping, node) trả về điểm PageRank mới của một đỉnh sau đúng một bước.
Quy ước nộp bài
Nộp hàm pagerank_update trong solution.py. Hệ thống gọi hàm trực tiếp và so giá trị với sai số 1e-6; không đọc stdin và không in ra stdout.
Input
- scores: vector điểm hiện tại (danh sách số thực, độ dài N).
- adjacency: ma trận kề có hướng, adjacency[j][i] == 1 nghĩa là có cạnh j -> i.
- damping: hệ số giảm d trong [0, 1].
- node: chỉ số đỉnh cần tính.
Output
Một số thực là (1 - d) / N + d * tổng_j ( scores[j] / outdeg(j) ) với j là các đỉnh trỏ tới node.
Ràng buộc
- node phải nằm trong [0, N) và adjacency phải là N x N; nếu không thì ném
ValueError.
- Chỉ dùng NumPy cho tổng và phép chia.
Ví dụ 1
Input
pagerank_update(scores=[0.3, 0.3, 0.4], adjacency=[[0, 1, 1], [0, 0, 1], [1, 0, 0]], damping=0.85, node=0)
Output
0.39
Ví dụ 2
Input
pagerank_update(scores=[0.3, 0.3, 0.4], adjacency=[[0, 1, 1], [0, 0, 1], [1, 0, 0]], damping=0.85, node=1)
Output
0.1775
Giải thích
Với scores = [0.3, 0.3, 0.4], adjacency = [[0, 1, 1], [0, 0, 1], [1, 0, 0]] và d = 0.85: chỉ đỉnh 2 trỏ tới đỉnh 0, outdeg(2) = 1, nên kết quả là (1 - 0.85) / 3 + 0.85 * 0.4 = 0.39.
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.
