旅行售货员问题分支界限法
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* Created by saishangmingzhu on 2018/12/13.
* 旅行售货员问题
*/
public class TravellingSalesmanProblem {
//图
private int[][] pointIndex=new int[][]{
{0,30,6,4},
{30,0,5,10},
{6,5,0,20},
{4,10,20,0}};
public static void main(String[] arg){
new TravellingSalesmanProblem().branchAndBoundMethod();
}
/**
* 分支界限法-优先队列式
* 优先队列式求解时，到达第一个没有子结点的活结点时，即为最优解
*/
public void branchAndBoundMethod() {
List<Point> pointList=new ArrayList<>();
pointList.add(new Point(0,"1"));
pointList.add(new Point(1,"2"));
pointList.add(new Point(2,"3"));
pointList.add(new Point(3,"4"));
Node root=new Node();
root.point=pointList.get(0);
root.childPointList.addAll(pointList);
root.childPointList.remove(root.point);
Node minNode=new Node();
minNode.value=Integer.MAX_VALUE;
List<Node> currentLiveNodeList=new ArrayList<>();
currentLiveNodeList.add(root);
while (currentLiveNodeList.size()>0) {
Node liveNode = currentLiveNodeList.get(0);
List<Point> childPointList = liveNode.childPointList;
for (Point childPoint : childPointList) {
int value=pointIndex[childPoint.index][liveNode.point.index];
if (value!=0) {
Node childNode = new Node();
childNode.parentNode=liveNode;
childNode.point = childPoint;
childNode.childPointList.addAll(childPointList);
childNode.childPointList.remove(childPoint);
childNode.value = liveNode.value + value;
if (childNode.childPointList.size() == 0 ) {
if (pointIndex[0][childPoint.index] != 0) {
childNode.value += pointIndex[0][childPoint.index];
if (childNode.value<minNode.value){
minNode.value=childNode.value;
minNode.point=childNode.point;
minNode.parentNode=childNode.parentNode;
}
} else {
continue;
}
}
currentLiveNodeList.add(childNode);
}
}
currentLiveNodeList.remove(liveNode);
Collections.sort(currentLiveNodeList, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o2.value-o1.value;
}
});
}
System.out.println(minNode.value);
getParents(minNode);
}
private void getParents(Node node){
if (node==null){
return;
}
getParents(node.parentNode);
System.out.println(node.point.name);
}
class Node{
private Node parentNode;
private Point point;
private List<Node> childNodeList=new ArrayList<>();
private List<Point> childPointList=new ArrayList<>();
private int value;
}
class Point{
private int index;
private String name;
public Point(int index, String name) {
this.index = index;
this.name = name;
}
}
}
©著作权归作者所有：来自51CTO博客作者塞上名猪的原创作品，如需转载，请注明出处，否则将追究法律责任