Phân tích: Modern Art Plagiarism

Bài toán này là một bài toán đồ thị kinh điển được gọi là đẳng cấu cây con (subtree isomorphism). Một lưu ý thú vị là kỷ nguyên hiện đại trong lịch sử nghệ thuật thực tế bắt đầu sớm hơn nhiều so với cái gọi là thời kỳ cổ điển trong khoa học máy tính.

Trong bài toán này, chúng ta được cho hai cây \(T_1\) và \(T_2\). Chúng ta cần quyết định xem \(T_2\) có đẳng cấu với bất kỳ cây con nào của \(T_1\) hay không. Bài toán đẳng cấu đồ thị con (sub-graph isomorphism) tổng quát nổi tiếng là khó (NP-hard). Nhưng như bạn có thể đã thấy nhiều lần, khi mọi thứ liên quan đến cây, nó rất khả thi để giải quyết. Bài toán này thực tế đã được nghiên cứu kỹ lưỡng và là một bài tập chuẩn trong thiết kế thuật toán.

Đầu tiên, một chút thuật ngữ. Để thuận tiện, trong thảo luận của chúng ta, đối với hai cây có gốc, chúng ta nói cây này khớp vào (fits into) cây kia nếu có một phép đẳng cấu ánh xạ cây trước vào một cây con của cây sau sao cho gốc được ánh xạ vào gốc của cây kia.

Chúng ta có thể cố định \(T_2\) và coi nó như một cây có gốc tại đỉnh 0. Chúng ta không biết đỉnh nào của \(T_1\) tương ứng với đỉnh 0 của \(T_2\) trong phép đẳng cấu. Nhưng chúng ta có thể thử từng đỉnh trong \(T_1\) làm gốc, và xem liệu \(T_2\) có khớp vào \(T_1\) hay không.

Ví dụ cụ thể, giả sử chúng ta đặt gốc của \(T_1\) tại đỉnh \(x\). Giả sử có 3 nút con của 0 trong \(T_2\) là \(y_1, y_2,\) và \(y_3\). Giả sử có 5 nút con của \(x\) trong \(T_1\) là \(x_1, x_2, x_3, x_4, x_5\). \(T_2\) khớp vào \(T_1\) khi và chỉ khi chúng ta có thể tìm thấy cây con tại \(y_1\) khớp vào cây con tại \(x_i\) với một chỉ số \(i\) nào đó, cây con tại \(y_2\) khớp vào cây con tại \(x_j\) với một chỉ số \(j \neq i\) khác, và cây con tại \(y_3\) khớp vào cây con tại \(x_k\) với một chỉ số \(k \neq i, k \neq j\).

Giải pháp cho bài toán này như sau. Khi chúng ta đã cố định gốc \(x\), mỗi đỉnh có một cấp độ (level) trong cây của nó. Đối với mỗi cặp đỉnh \(u\) trong \(T_1\) và \(v\) trong \(T_2\) có cùng mức (đây chỉ là một tối ưu hợp lý, không bắt buộc đối với bài này), chúng ta muốn quyết định xem cây con tại \(v\) có khớp vào cây con tại \(u\) hay không. Chúng ta thực hiện việc này từ dưới lên (bottom-up), các cấp độ sâu hơn trước.

Đối với bất kỳ cặp \((u, v)\) nào với các con \(\{ u_i \mid i = 1,2,... \}\) và \(\{ v_j \mid j = 1,2,... \}\), chúng ta biết \(v_j\) nào khớp vào \(u_i\) nào vì chúng ta đang thực hiện tính toán từ dưới lên. Chúng ta tìm thấy một sự khớp (fit) khi và chỉ khi chúng ta có thể tìm thấy, cho mỗi \(v_j\), một \(u_i\) riêng biệt sao cho \(v_j\) khớp vào \(u_i\). Đây rõ ràng là bài toán ghép cặp cực đại trên đồ thị hai phía (bipartite graph matching).

Độ phức tạp

Thuật toán này chạy trong thời gian \(O(N^2 M^2)\). Có những thuật toán với độ phức tạp tốt hơn. Đối với độc giả quan tâm, chúng tôi đề xuất tham khảo bài báo sau:
R. Shamir, D. Tsur, "Faster Subtree Isomorphism", Journal of Algorithm, 33, 267-280 (1999).
Bài báo này chứa kết quả gần đây cũng như các tham chiếu đến các công trình trước đó.

Thông tin thêm

• Subtree Isomorphism
• Graph Isomorphism
• Bipartite Matching

Dựa trên phân tích chính thức của Google Code Jam.