尋找一棵樹上最少的呼叫次數

我在一次採訪中被問到了這個問題，並在分配的時間內努力回答它。儘管如此，我認爲這是一個有趣的問題，而我之前從未見過。尋找一棵樹上最少的呼叫次數

假設你有一棵樹，根可以打電話給他們每個孩子，當孩子接到電話時，他可以打電話給他的每個孩子等。問題是每個電話都必須完成在很多輪次中，我們需要儘量減少撥打電話所需的輪次數。例如，假設您有以下樹：

A 
/\ 
/ \ 
B D 
| 
| 
C

一種解決方案是爲一個叫d在第一輪比賽，A到B鍵兩回合，和B調用C在第三輪。最佳的解決方案是A在第一輪呼叫B，A在第二輪呼叫D和B呼叫C.

請注意，A不能在同一回合中同時調用B和D，任何節點也不能在同一回合中調用多個子女。但是，具有不同父級的多個節點可以同時調用。例如，給定的樹：

 A 
    /| \ 
/| \ 
    B C D 
    /\  | 
/\  | 
E F  G

我們可以有一個序列（其中 - 分離發），如：

AB - BE，AD - BF，AC，DG

（A呼叫B第一輪，B調用E和A調用d第二，...）

我假設可以使用某種類型的動態編程，但我不確定要採用哪種方向。我最初的傾向是使用DFS以降序排列從根到葉的最長路徑，但是當它出現時到實際撥打電話的節點，我不知道我們如何能夠實現任何樹的最優性，而不是我們如何輸出最佳呼叫將會做出的路徑（即在第一個例子中，我們可以輸出

AB - BC，AD

來源

2014-10-04 Bob Jonas

貪心呢？ – Lrrr 2014-10-04 10:22:54

@AliAmiri我看不出我們如何貪婪地選擇最佳路徑。你能詳細說明嗎？ – 2014-10-04 10:26:11

每一輪和每個節點選擇一個有孩子的孩子。我認爲這會解決問題，但我不確定它是否有效？ – Lrrr 2014-10-04 10:34:15

我覺得像這樣可以得到最佳的解決方案：

假設每個「呼叫」的值的葉子是1
爲每個節點獲取所有他的孩子的呼叫值，並根據他們的「呼叫」值對它們進行排名
考慮排名o f'每個孩子'排名'
計算每個節點循環對他的孩子（在計算他們的排名之後）'呼叫'的值並且找到'呼叫'+'等級'的最大值
'calls'根節點的值就是答案

這是對樹木八九不離十動態規劃，你可以遞歸實現它是這樣的：

int f(node v) 
{ 
    int s = 0; 
    for each u in v.children 
    { 
     d[u] = f(u) 
    } 
    sort d and rank its values in r (r for the maximum u would be 1) 
    for each u in v.children 
    { 
     s = max(s, d[u] + r[u] + 1) 
    } 
    return s 
}

祝您好運！

來源

2014-10-04 10:38:13 MSH

你甚至會執行第1步？你如何「從樹葉開始......？」通常樹會作爲指向根的指針和指向其子節點的指針給出。 – 2014-10-04 10:41:11

是的，但你不需要按照這個順序來做！你可以從根開始遞歸地實現它。我描述了它的工作方式，但你不需要以這種方式看到它。在你的遞歸函數中，當你到達葉子時，返回1作爲例子。 – MSH 2014-10-04 10:43:46

好，但有兩件事情：葉子打0電話，而不是1;如果等級從1開始，那麼將'd [u] + r [u] + 1'改爲'd [u] + r [u]'。 – 2014-10-04 15:51:53

尋找一棵樹上最少的呼叫次數

回答

相關問題