Phát hiện khi nhân ma trận có thể

Question

Dưới đây là một vấn đề thú vị mà tôi gặp phải trong một cuộc thi lập trình:

tuyên bố Vấn đề: Do kích thước của n ma trận, xác định xem có tồn tại một trật tự như vậy mà các ma trận có thể nhân lên. Nếu có, in ra kích thước (sản phẩm của kích thước) của ma trận kết quả.

Quan sát của tôi: Điều này giảm xuống vấn đề đường dẫn Hamilton-NP nếu bạn xem mỗi ma trận là một đỉnh và vẽ một cạnh đạo giữa các ma trận có thể nhân lên. Tôi giải quyết điều này bằng cách đơn giản là brute-buộc vấn đề nhưng điều này rõ ràng là rất chậm. Tôi đã tự hỏi nếu có bất kỳ tối ưu hóa thông minh cho trường hợp cụ thể của vấn đề này.

Answer 1

1. Tạo nút cho mỗi chiều dài thứ nguyên. Tức là, nếu có ma trận kích thước (m, n), thì m và n sẽ là đỉnh trong biểu đồ.

2. Đối với mọi ma trận có kích thước (m, n), kết nối các nút m và n với cạnh được chỉ đạo (có thể có nhiều cạnh giữa hai nút).

3. Bây giờ, tìm một đường mòn eular sẽ cung cấp thứ tự nhân.

Xem http://en.wikipedia.org/wiki/Euler_path để tìm đường mòn Eularian. Độ phức tạp là khá gần với tuyến tính (O (nlog^3n loglogn) trong đó n là số cạnh = số ma trận).

Answer 2

Tạo ma trận tương thích (hãy gọi nó là CM) chẳng hạn như CM [x, y] = 1 nếu ma trận x có thể được multuplied bởi y, 0 nếu không. nếu yếu tố quyết định (CM) <> 0 có một đơn đặt hàng.

Nó chỉ là một trực giác, tôi xin lỗi nếu tôi sai (tiếc là tôi không thể tìm thấy một bằng chứng vững chắc).