最近公共祖先優化

我有包含元素[0至Ñ - 1]一個基本的陣列，其中每個元素是具有索引總是指向前面所述陣列中的位置的結構。最近公共祖先優化

在一個點上，作爲一個更大的算法的一部分，我想找到的節點X和之後的任何節點之間的特定ç最低的共同祖先。

int LCA(a, b) { 
    while (a != b) { 
     if (a > b) { 
      a = nodes[a].parent; 
     } else { 
      b = nodes[b].parent; 
     } 
    } 
    return a; 
} 

for (y = x + 1; y < n; ++y) { 
    if (LCA(x, y) == c) { 
     //other code 
    } 
}

上面的代碼實際上是僞代碼。通過使用生成的查找表，我設法略微提高了LCA（）的性能。事情是這樣的：

int LCA(a, b) { 
    if (lookup[a, b]) { 
     return lookup[a, b]; 
    } 
    oa = a; ob = b; 
    while (a != b) { 
     if (a > b) { 
      a = nodes[a].parent; 
     } else { 
      b = nodes[b].parent; 
     } 
    } 
    lookup[oa, ob] = a; 
    lookup[ob, oa] = a; 
    return a; 
}

我知道有可能是一個辦法可以讓某種專門的LCA（）函數，也就是更換所有上面的代碼以某種方式專門它，所以它是相當快。但我沒有想到任何有趣的事情。

我已經嘗試看看我是否可以簡單地通過查看LCA(c, y) == LCA(x, y)做Ç和Y之間的LCA檢查，但當然，這是不準確的。

要重新上限：X總是小於Y。 C總是小於X（因此Y）。父母的指數總是比他們的孩子低（因此它是有序的）。

節點知道他們的深度有幫助嗎？

此代碼佔整個算法的CPU時間的80％，總共需要大約4分鐘。對此的解決方案可以輕鬆地改進整個算法。謝謝！

來源

2013-09-25 Mike Weir

屬於[codereview.se]或者[cs.se] – millimoose

另外，說實話，我的直覺告訴我，這樣做會很好 - 它已經是次線性時間。我很驚訝查找表沒有什麼幫助，這看起來像是備忘錄的主要候選人。有一件事可能會在線性時間以下采用這種方法，那麼在您將元素插入此數據結構時將構建查找表，但這可能會帶來'O（n^2）'內存開銷，使插入速度變慢，而且似乎像這樣做不是微不足道的。（假設你用「lookup table」來表示「hashtable」，如果你不這樣做，我會用一個）。 – millimoose

記憶不一定有幫助，它取決於你真正得到什麼查詢。您應該使用更高效的LCA算法。可以通過一些預處理來回答'O（1）'中的查詢。 – IVlad

的x和y的LCA會隨着x的發生和y在樹的euler tour（*）的發生之間的最小高度的節點。要在O(1)時間內找到此項，您需要使用this method來解決RMQ problem。

（*）：您的旅程需要稍作修改才能使用。您每次回到數組時都必須在數組中添加一個值（從遞歸調用返回給子組）。對於維基樹，它應該是這樣的：

1 2 3 4 5 6 7 8 9 10 11 
1 2 6 2 4 2 1 3 1 5 1

注意，有沒有點有葉子出現兩次（雖然它不會影響正確性）。

因此，例如，RMQ(2, 5)將與最小高度的節點出這些：

2 3 4 5 6 7 8 9 10 
2 6 2 4 2 1 3 1 5

哪個節點1。

這不是您可以採取的唯一有效間隔。這也是有效的利用2最後一次出現：

6 7 8 9 10 
2 1 3 1 5

這也將返回1爲LCA。

這樣，您可以在預處理花費的線性時間在恆定時間內回答LCA查詢。

來源

2013-09-25 21:10:53 IVlad

最近公共祖先優化

回答

相關問題