Tôi đã xem this question và sau đó đọc khoảng Tarjan's least common ancestors algorithm. Tôi chưa bao giờ gặp bất kỳ ứng dụng nào của thuật toán LCA trước đây.Các ứng dụng thực tế của thuật toán tổ tiên chung thấp nhất là gì?
Thuật toán LCA thường được sử dụng ở đâu?
Không biết nơi nó được sử dụng, nhưng tôi có một vài ý tưởng, nơi nó có thể được sử dụng:
máy tính đồ họa: thường cảnh 3D được chia thành khối mà tạo thành một cấu trúc cây. Nếu bạn có một đối tượng được chứa trong hai khối đó, thuật toán LCA sẽ cho bạn khối nhỏ nhất có khối lớn hơn.
phân tích gens để tìm ra mối quan hệ giữa các loài và tổ tiên chung thấp nhất của họ
thuật toán hợp nhất của các hệ thống kiểm soát phiên bản
cảm ơn! kiểm soát phiên bản -> ba cách hợp nhất: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Lazer
Nó cũng hữu ích cho một số loại xử lý chuỗi khi tìm kiếm các từ gốc cho các hậu tố khác nhau. –
Trong trình biên dịch, LCA của hai khối cơ bản là một nơi bạn có thể đặt một tính toán để nó có sẵn cho cả hai. Điều này có thể hữu ích cho việc loại bỏ các biểu thức con chung, hoặc chèn phi-nút để chuyển đổi SSA. Mặc dù vậy, các thuật toán này được phát triển tốt và được tối ưu hóa cao, vì vậy bản thân LCA có thể khó nhìn thấy, ví dụ: SSA và PRE
cảm ơn @Doug Currie – Lazer
Tôi vừa viết một bài đăng blog về cách thực hiện thuật toán của riêng mình. đến một tập hợp các nút với chiều dài tùy ý) cho một cây phân loại trong bối cảnh khổng lồ metagenomics:
Chúc mừng,
Pablo
không gian cấu trúc dữ liệu cây trong khoa học máy tính, hậu tố cây cho dây trong sinh học tính toán, vv Quên các chi tiết, xin lỗi, nhưng nó chắc chắn hữu ích. – polygenelubricants