如何避免不必要的计算找到最大的独立集？(How to avoid unnecessary computations finding maximum independent sets?)

我编写了一个算法来查找图的最大独立集。根据定义，独立集合是“集合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 Gerrow的回复之后，我改变了我的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("}"); } }

}

I coded an algorithm to find maximal independent sets of a graph. By definition an independent set is "a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S"

The graph is an undirected graph as shown below:

Nodes : 1,2,3,4,5,6,7 Edges : 1-2,2-3,3-4,4-5,5-6,6-7,1-5

And here is my implementation:

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("}"); } } }

The output is below:

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.

UPDATE :1 : After Darryl Gerrow's reply, I changed my visitNode method as follows: It worked. I have still some issues with my algorithm to make it more readable and portable. I will post the final version whenever I finished. Thanks for all community. If anyone have better idea to find maximal independent sets in a graph other than just looking for all nodes, I really appreciate to read about.

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("}"); } }

}

最满意答案

看起来你正在做一个n平方的迭代，这就是为什么你得到{1,3,6}，{1,6,3}，{3,6,1}，......基本上每一个可接受的组合的可能组合。

我认为您需要重新编写迭代，以便只访问比当前节点更大的节点。

即。你会得到{1,3,6}，但是{1,6,3}是不可接受的，因为6> 3。

您可能必须删除Iterator并使用ArrayList的索引方法。

It looks like you're doing an n-squared iteration, so that's why you're getting {1, 3, 6}, {1, 6, 3}, {3, 6, 1}, .... essentially every possible combination of an acceptable set.

I think you need to re-write the iteration so that you only visit larger nodes than the current node.

ie. you would get {1, 3, 6}, but {1, 6, 3} would not be acceptable because 6 > 3.

You may have to drop the Iterator and use the index methods of the ArrayList.

更多推荐