0

我想在具有 n 个节点的树中找到两条路径,以便这两条路径没有任何公共节点,并且这两条路径的长度相乘得到最大值。任何人都可以帮助我如何解决这个问题?

4

2 回答 2

2

首先,使用递归过程生成每个可能的唯一路径的列表。

你最终得到了 m 个可能的路径。

其次,设置一个 mxm 元素数组。

检查 m 路径中的每一个与所有其他 m-1 路径,并将相应长度的乘积存储到数组中。这样做检查两条路径是否有共同的节点。如果是,则存储 0。

第三,检查 mxm 数组中具有最大值的元素。

你还能做什么?这是非常暴力的,但如果没有更多关于树属性的信息,这是唯一的方法。

于 2013-01-06T21:05:39.690 回答
1

一些想法。如果有两个值 a 和 b 加起来为 n,则 a*b 的最大值是当 a == b 时(为简单起见,假设 n 是偶数)。如果有一条路径通过所有 n 个节点,则将其分成两个几乎相等的部分。对于偶数 n 的此类图,答案将是 (n^2) / 4,对于奇数 n,答案将是 (n-1)/2 * (n+1)/2 = (n^2 - 1) / 4。如果没有路径通过所有 n 个节点,您将不得不使用其他一些技术。但上限如上。

于 2013-01-07T00:23:29.307 回答