如何避免不必要的计算，寻找最大独立集？
如何避免不必要的计算，寻找最大独立集？
提问于 2013-09-04 16:22:25
我编写了一个算法，以求图的最大独立集。根据定义，独立集是“一个集S，使得图的每个边至少有一个端点不在S中，而不位于S中的每个顶点在S中至少有一个近邻”。
该图是一个无向图，如下所示：
节点: 1,2,3,4,5,6,7边缘: 1-2,2-3,3-4,4-5,5-6,6-7,1-5
以下是我的实现：
FindMIS fms= new FindMIS(network);
public class FindMIS {
INetwork network;
public FindMIS(INetwork network) {
this.network = network;
ArrayList<INode> nodes = new ArrayList<>();
nodes.addAll(network.getNodesList());
Iterator<INode> iter = nodes.iterator();
ArrayList<INode> IS = new ArrayList<>();
while (iter.hasNext()) {
INode node=iter.next();
visitNode(node, IS, nodes);
}
}
private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode>
previousCandidates) {
ArrayList<INode> IS=new ArrayList<>();
IS.addAll(previousIS);
ArrayList<INode> candidates = new ArrayList<>();
candidates.addAll(previousCandidates);
//System.out.println(node);
ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node);
for (INode n : previousCandidates) {
if (neighbor.contains(n)) {
candidates.remove(n);
}
}
IS.add(node);
candidates.remove(node);
Iterator<INode> iter = candidates.iterator();
while (iter.hasNext()) {
visitNode(iter.next(), IS, candidates);
}
if (candidates.size()==0){
Iterator<INode> iter2=IS.iterator();
System.out.print("output:{" );
while(iter2.hasNext()){
System.out.print(iter2.next().getid());
}
System.out.println("}");
}
}
} 产出如下：
output:{1 3 6 }
output:{1 4 6 }
output:{1 6 3 }
output:{1 6 4 }
output:{2 4 6 }
output:{2 4 7 }
output:{2 5 7 }
output:{2 6 4 }
output:{2 7 4 }
output:{2 7 5 }
output:{3 1 6 }
output:{3 5 7 }
output:{3 6 1 }
output:{3 7 5 }
output:{4 1 6 }
output:{4 2 6 }
output:{4 2 7 }
output:{4 6 1 }
output:{4 6 2 }
output:{4 7 2 }
output:{5 2 7 }
output:{5 3 7 }
output:{5 7 2 }
output:{5 7 3 }
output:{6 1 3 }
output:{6 1 4 }
output:{6 2 4 }
output:{6 3 1 }
output:{6 4 1 }
output:{6 4 2 }
output:{7 2 4 }
output:{7 2 5 }
output:{7 3 5 }
output:{7 4 2 }
output:{7 5 2 }
output:{7 5 3 }
You can realize that there are some redundant sets like {1,3,6} and {1,6,3}. The final result must be:
output:{1 3 6}
output:{1 4 6}
output:{2 4 6}
output:{2 4 7}
output:{2 5 7}
output:{3 5 7}
I am trying to figure out a way to avoid unnecessary computation.
I appreciate for any idea.更新:1 :在Darryl的回复之后，我更改了我的visitNode方法如下:它成功了。我仍然有一些问题，我的算法，使其更加可读性和可移植性。当我完成的时候，我会贴出最后的版本。感谢所有的社区。如果有人有更好的想法去寻找图中的最大独立集，而不仅仅是寻找所有的节点，我真的很乐意读到。
private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode>
previousCandidates) {
ArrayList<INode> IS=new ArrayList<>();
IS.addAll(previousIS);
ArrayList<INode> candidates = new ArrayList<>();
candidates.addAll(previousCandidates);
//System.out.println(node);
ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node);
for (INode n : previousCandidates) {
if (neighbor.contains(n)) {
candidates.remove(n);
}
}
IS.add(node);
candidates.remove(node);
Iterator<INode> iter = candidates.iterator();
while (iter.hasNext()) {
INode nextnode=iter.next();
if (node.getid() < nextnode.getid())
visitNode(nextnode, IS, candidates);
}
if (candidates.size()==0){
Iterator<INode> iter2=IS.iterator();
System.out.print("output:{" );
while(iter2.hasNext()){
System.out.print(iter2.next().getid() +" ");
}
System.out.println("}");
}
}}
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-09-04 17:16:32
看起来你在进行n平方迭代，所以这就是为什么你要得到{1，3，6}，{1，6，3}，{3，6，1}，.基本上是一个可接受的集合的每个可能的组合。
我认为您需要重写迭代，以便只访问比当前节点更大的节点。
即。您将得到{1，3，6}，但是{1，6，3}是不可接受的，因为6> 3。
您可能必须删除Iterator并使用ArrayList的索引方法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18619071
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号