寻找一棵树上最少的呼叫次数

我在一次采访中被问到了这个问题，并在分配的时间内努力回答它。尽管如此，我认为这是一个有趣的问题，而我之前从未见过。寻找一棵树上最少的呼叫次数

假设你有一棵树，根可以打电话给他们每个孩子，当孩子接到电话时，他可以打电话给他的每个孩子等。问题是每个电话都必须完成在很多轮次中，我们需要尽量减少拨打电话所需的轮次数。例如，假设您有以下树：

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

寻找一棵树上最少的呼叫次数

回答

相关问题