找到另一棵樹上的一棵樹的節點

Question

我的問題是： 考慮兩棵樹P和R.我需要匹配P的最深可能級別上的節點和樹R最深可能級別上的節點。這意味着，樹中的所有節點都像從最一般到最具體的分層關係。應找到樹P與樹R最具體的匹配。 需要最優化的方法。

例如，讓我們有一個審閱者面板。每個評論者都有他自己的興趣點，從一般興趣到特定的喜歡從能源到沼氣工廠。現在有一篇文章要與評論者的興趣相匹配。將找到與論文類別最具特定匹配的評論者。每篇論文也有從最普通類別到完全特定類別的類別樹。

Answer 1

編輯：深度差異

1. 決定你要多少重視，給他們的「相似性」在他們的深度，與匹配的節點固定表達。使用它可以得到一個評分函數s（x，y）= a *（ - | depth（x） - depth（y）|）+（1-a）*（similarity（x，y））。 （相似性（x，y）可以是x和y的任何函數 - 例如，如果x和y是字符串，它可以是它們最長公共子序列的長度。）
2. （概念上）爲每個節點創建一個頂點樹1，樹2中每個節點的頂​​點，以及每對頂點（x，y）的邊，第一棵樹中的x和第二棵中的y。將此邊的權重設置爲s（x，y）。
3. 你現在有一個bipartite maximum weighted matching problem，又名作業問題。應用匈牙利算法在O（n^3）時間內找到最優解。

Answer 2

您可以使用Trie解決它，其中根具有最普遍的類別，其子類具有更具體的類別，子類具有越來越多的特定類別。您需要從根開始找到最長的匹配。