我想在具有 n 个节点的树中找到两条路径，以便这两条路径没有任何公共节点，并且这两条路径的长度相乘得到最大值。任何人都可以帮助我如何解决这个问题？
问问题
782 次
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 回答