求最大值算法,该怎么解决

求最大值算法
题目是：
图中有M个节点，任意两个节点都互相连接，节点与节点之间的权重各不相同。
现在给定数字n(n<m)，求图中哪n个节点之间的权重之和最大。

举例：如果有a,b,c,d 4个节点，任意一个节点与其他3个节点都连接，ab=1,ac=2,ad=3,bc=2,bd=3,cd=1,求哪3个节点的权重和最大？

这个问题是否可以转换成图论中的最大流问题？
求算法，谢谢！

[解决办法]
最大团问题。NPC。
[解决办法]

探讨

引用:
直接遍历从m个节点中取出n个节点的所有情况，求出最大值。


求的是节点之间的权重之和最大，并非是节点本身的值最大。
能给出具体思路吗？谢谢！

[解决办法]
m选n的问题n!/(m-n)! 种可能.如果暴力搜索的话,就先得到所有的组合情况,有Comban(m,n)的现成算法.

如果点的数量大,用遗传算法,可以减少遍历次数.可以得到相对最优解.

[解决办法]
感觉是没错的.有错希望指出.
给定的i,j 两点

划分i,j为内部已记录的点.
(内部点要求,对任意不同的两点m,n,都标志了i - m - n -j和为最大值时的路径,
)
逐个添加其他还没记录的点.
记录新加点x的要求是:
1,遍选所有内部标志的i - m - n -j路径,选取i -m -x -n-j最大值时的路径作为
i - x - j和 的路径.
至所有点都记录为内部点为止

(记录时一般只记录 i - x ,x - j 中x相邻的,)
需要空间为n*n复杂度


[解决办法]
今天一直nc，请无视我说的话，刚发现我题目意思理解错了。。。我回去补补最大团。不过如果用暴力的话，就是穷举所有组合即可。
[解决办法]
从任意个节点发，把所有走N步的情况遍历到，n(m1..mm),n-1(m1...n-1,n+1...mm),....1
第一个节点foreach(node tn in m)
第二个节点foreach(node tn-1 in m)
if(tn-1==tn)
{
continue;
}
[解决办法]
贪心算法
假设前n个点就是满足的点，
计算并保存每个点的权值为此点与其他n-1个点的连线的权值之和
设点K为剩下的m-n个点中的一个，L为n中的一个，
计算用K点取代L点时K点的权值，重复计算n中的所有点，用K取代与L权值差最大的那个L点
遍历m-n中的点重复上面操作
时间复杂度为O（n*(n-1)+n*(n-1)*(m-n)）<O(m^3)

查看更多 下一篇