2017年三月底四月初跟实验室的小伙伴一起参加了华为的软件精英挑战赛，可惜实力不济，止步于赛区64强，还是倒数几名......
我们使用了模拟退火+spfa最大流最小费用算法，通过上百次迭代，获取近似解。
核心代码如下：
package com.cacheserverdeploy.deploy;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
public class Deploy {
/**
* 你需要完成的入口 <功能详细描述>
*
* @param graphContent
* 用例信息文件
* @return [参数说明] 输出结果信息
* @see [类、类#方法、类#成员]
*/
protected static final int INT_MAX = 300000000;
// protected static final int INT_MAX = Integer.MAX_VALUE;
protected static int nodeNum;
protected static int n;
protected static int consumersNum;
protected static int linksNum_undirected;
protected static int linksNum_directed;
protected static int superTID;
protected static int superSID;
protected static Link[] links;
protected static ConsumerNode[] consumers;
protected static int serverCost;
protected static int totalLinksNum;
protected static Link[] linksSuper;
protected static int index;
protected static int requiredFlow = 0;
protected static int[] degree;// 存储所有的点的度
protected static int[] nodeIndexByDegree;// 按度大小存储链路节点的ID
protected static MinCMaxF mcmf;
protected static long startTime;
protected static long stopTime;
/******************************************/
public static String[] deployServer(String[] graphContent) {
/** do your work here **/
startTime = System.currentTimeMillis();
// 获取输入文件第一行信息
String[] lineOne = graphContent[0].split(" ");
n = Integer.parseInt(lineOne[0]);
nodeNum = n;
// new linksNum = Integer.parseInt(lineOne[1]);
linksNum_undirected = Integer.parseInt(lineOne[1]);
linksNum_directed = 2 * linksNum_undirected;
consumersNum = Integer.parseInt(lineOne[2]);
degree = new int[nodeNum];
nodeIndexByDegree = new int[nodeNum];
// 获取输入文件的第二行有效信息
String lineTwo = graphContent[2];
serverCost = Integer.parseInt(lineTwo);
/********************* 两倍链路 ***************************/
// 链路数组
totalLinksNum = linksNum_directed + 2 * consumersNum + nodeNum;
links = new Link[linksNum_directed];
Link tmpLink;
for (int i = 0; i < linksNum_undirected; i++) {
String[] strs = graphContent[i + 4].split(" ");
int from = Integer.parseInt(strs[0]);
int to = Integer.parseInt(strs[1]);
int capibility = Integer.parseInt(strs[2]);
int costPerUnit = Integer.parseInt(strs[3]);
tmpLink = new Link(from, to, capibility, costPerUnit, 0);
links[2 * i] = tmpLink;
tmpLink = new Link(to, from, capibility, costPerUnit, 0);
links[2 * i + 1] = tmpLink;
}
linksSuper = new Link[totalLinksNum];
for (int i = 0; i < linksNum_directed; i++)
linksSuper[i] = links[i];
index = linksNum_directed;
// 设置度数组
setDegreeArr(degree, nodeIndexByDegree, links);
/*******************************************************/
/****************************/
// for (int i : maximunFront)
// System.out.print(i + " ");
// 消费节点
consumers = new ConsumerNode[consumersNum];
ConsumerNode tmpNode;
for (int i = 0; i < consumersNum; i++) {
String[] strs = graphContent[i + 5 + linksNum_undirected]
.split(" ");
int cID = Integer.parseInt(strs[0]);
int neighborID = Integer.parseInt(strs[1]);
int requiredBand = Integer.parseInt(strs[2]);
tmpNode = new ConsumerNode(cID, neighborID, requiredBand);
requiredFlow += requiredBand;
consumers[i] = tmpNode;
}
// 定义两个超级节点:超级源点，超级汇聚节点
superSID = nodeNum;
superTID = nodeNum + 1;
n = n + 2;
// 将消费节点加入及相关链路加入网络
for (int i = 0; i < consumersNum; i++) {
// 将消费节点链接到原网路中
Link tmpConsumerLink = new Link(consumers[i].getNeighborID(), n,
consumers[i].getRequiredBand(), 0, 0);
linksSuper[index++] = tmpConsumerLink;
// 指向超级汇聚节点,消费节点ID用n+i表示，汇聚节点用n+consumersNum表示
Link tmpConsumerLink2 = new Link(n, superTID,
consumers[i].getRequiredBand(), 0, 0);
linksSuper[index++] = tmpConsumerLink2;
n++;
}
/**********************************************************************************/
// System.out.println("n after add server:"+n);
// 生成node数组
// Node[] nodes = new Node[nodeNum];
// for (int i = 0; i < nodeNum; i++) {
// nodes[i] = new Node(i, 0);
// }
// nodes[nodeNum] = new Node(nodeNum, 0);
// nodes[nodeNum + 1] = new Node(nodeNum + 1, 0);
// // 消费节点node
// for (int i = 0; i < consumersNum; i++) {
// nodes[i + nodeNum + 2] = new Node(i + nodeNum + 2, 0);
// }
// // 服务器节点
// for (int i = 0; i < nodeNum; i++) {
// nodes[i + nodeNum + 2 + consumersNum] = new Node(i + nodeNum + 2
// + consumersNum, serverCost);
// // nodes[i + nodeNum + 2 + consumersNum] = new Node(i + nodeNum + 2
// // + consumersNum, 0);
// }
/****************************************/
// 调用模拟退火
SA.getSA();
/***************** PathListWithFlow()方式返回数据 *****************/
List<String> pathesList = mcmf.getPathListWithFlow();
String[] strResult = new String[pathesList.size() + 2];
strResult[0] = pathesList.size() + "";
strResult[1] = "";
for (int i = 0; i < pathesList.size(); i++) {
strResult[i + 2] = "";
String[] str = pathesList.get(i).split(" ");
int consumer = Integer.parseInt(str[str.length - 3]) - nodeNum - 2;
int flow = Integer.parseInt(str[str.length - 1]);
for (int j = 1; j < str.length - 3; j++)
strResult[i + 2] = strResult[i + 2] + str[j] + " ";
strResult[i + 2] = strResult[i + 2] + consumer + " " + flow;
}
/**************************************************************/
// for (String i : strResult)
// System.out.println("strResult:" + i);
/**************************************************************/
return strResult;
}
/*
* 度处理
*/
private static void setDegreeArr(int[] degree, int[] nodeIndexByDegree,
Link[] links) {
for (int i : degree) {
i = 0;
}
for (Link i : links) {
degree[i.getlStartID()]++;
degree[i.getlEndID()]++;
}
/***********************/
System.out.print("degree:");
for (int i : degree) {
System.out.print(i + " ");
}
System.out.println();
int[] degreeCopy = new int[degree.length];
int index = 0;
for (int i : degree) {
degreeCopy[index++] = i;
}
for (int i = 0; i < nodeIndexByDegree.length; i++) {
int maxIndex = 0;
for (int j = 0; j < degreeCopy.length; j++) {
if (degreeCopy[j] > degreeCopy[maxIndex]) {
maxIndex = j;
}
}
nodeIndexByDegree[i] = maxIndex;
degreeCopy[maxIndex] = -1;
}
/***********************/
System.out.print("sort by degree:");
for (int i : nodeIndexByDegree) {
System.out.print(i + " ");
}
System.out.println();
}
/*
* 插入服务器
*/
public static void insertServerLink(Link[] linksSuper, int[] target) {
/********************** 单倍链路 ***********************/
// index = linksNum_undirected + 2 * consumersNum;
/********************** 双倍链路 ***********************/
index = linksNum_directed + 2 * consumersNum;
for (int i = 0; i < nodeNum; i++) {
Link tmpServerLink = new Link(superSID, i, target[i], 0, 0);
linksSuper[index++] = tmpServerLink;
}
}
}
/*
* 最小费用最大流
*/
class MinCMaxF {
private final int INT_MAX = 300000000;
// private final int INT_MAX = Integer.MAX_VALUE;;
private int flow = 0;
private int cost = 0;
private int N;// 点的个数
private int E;// 边的个数
protected static Link[] linksDouble;
private Link[] links;
protected static List<Integer>[] G;
private boolean[] isInQueue;// 判断一个点是否在队列当中
// private Node[] nodes;
private List<Integer> costList = new ArrayList<Integer>();// 存储所有的最大刘路径上的cost集合
private List<Integer> flowList = new ArrayList<Integer>();// 每条路径上的flow
private boolean[] isScaned;
private int lastServerLinkID;
private int[] d;// 起点到d[i]的最短路径保存值
private int[] p;// 用来记录路径，保存是上一条弧
private int[] a;// 增广路径后的改进量
private boolean[] isServer;// 第i个节点否为服务器
private int s;
private int t;
// DFS输出路径与计算cost
private static List<String> pathListWithFlow = new ArrayList<String>();
private int miniFlow = INT_MAX;
public MinCMaxF(Link[] links, int n, int s, int t) {
super();
this.links = links;
this.E = links.length;// 初始化边的个数
this.N = n;// 节点个数
this.isScaned = new boolean[this.N];
this.s = s;
this.t = t;
init();// 将边添加进邻接表
minCostMaxFlow(s, t);
/*********************************/
// System.out.println("mincost:" + minCostMaxFlow(s, t));
// for (String l : pathesList) {
//
// System.out.println("path:" + l);
// }
/********************** 各链路占用的带宽 *************************/
// ArrayList<Integer> eachLinkInPath = new ArrayList<Integer>(0);
// LinkedHashMap<String, Integer> hashMap = new LinkedHashMap<String,
// Integer>();
// for (int i = 0; i < pathesList.size(); i++) {
// int bandCost = flowList.get(i);
// String[] strArray = pathesList.get(i).split(" ");
// String[] pathArr = new String[strArray.length - 2];
// for (int j = 0; j < pathArr.length - 1; j++) {
// pathArr[j] = strArray[j + 1];
// }
// pathArr[pathArr.length - 1] = Integer
// .parseInt(strArray[strArray.length - 2])
// - Deploy.nodeNum
// - 2 + "";
// for (int j = 0; j < pathArr.length - 1; j++) {
// if (hashMap.get(pathArr[j] + " " + pathArr[j + 1]) == null) {
// hashMap.put(pathArr[j] + " " + pathArr[j + 1], bandCost);
// } else {
// int sum = hashMap.get(pathArr[j] + " " + pathArr[j + 1])
// + bandCost;
// hashMap.put(pathArr[j] + " " + pathArr[j + 1], sum);
// }
// }
//
// }
// System.out.print("====================输出链路与对应的i占用的带宽");
// for (Entry<String, Integer> entry : hashMap.entrySet()) {
// System.out.println(entry.getKey() + " " + entry.getValue());
// }
/**********************************************************/
//
// for(int c : costList){
// System.out.println("cost:"+c);
// }
//
// for (int c : flowList) {
// System.out.println("flow:" + c);
// }
/************** 输出各个节点做接收到的流量之和 ****************/
// int[] flowSumEachConsumer = new int[Deploy.consumersNum];
// for (int i : flowSumEachConsumer)
// i = 0;
// int indexTmp = 0;
// for (String l : pathesList) {
// /*******************************/
// // System.out.println("path:" + l);
// String[] strArr = l.split(" ");
// int consumerID = Integer.parseInt(strArr[strArr.length - 2])
// - Deploy.nodeNum - 2;
// flowSumEachConsumer[consumerID] += flowList.get(indexTmp);
// indexTmp++;
// }
// for (int i = 0; i < flowSumEachConsumer.length; i++)
// System.out.println(i + " flowSum:" + flowSumEachConsumer[i]);
/********************************************************/
// System.out.println("flow:" + flow);
// System.out.println("required flow:" + Deploy.requiredFlow);
// 如果输出的流量不符合u要求,说明是算法失败
if (flow != Deploy.requiredFlow)
cost = INT_MAX;
// System.out.println("cost:" + cost);
}
private void init() {
this.linksDouble = new Link[this.E * 2];
this.G = new ArrayList[this.N];
this.isInQueue = new boolean[this.N];
for (int i = 0; i < this.N; i++) {
this.G[i] = new ArrayList<Integer>();
this.isInQueue[i] = false;
isScaned[i] = false;
this.lastServerLinkID = -1;
}
this.d = new int[this.N];
this.p = new int[this.N];
this.a = new int[this.N];
this.isServer = new boolean[this.N];
for (boolean i : this.isServer)
i = false;
// 将所有的边添加进来
for (int i = 0; i < E; i++) {
int from = this.links[i].getlStartID();
int to = this.links[i].getlEndID();
int cap = this.links[i].getlBand();
int flow = this.links[i].getFlow();
int cost = this.links[i].getlBCostPerUnit();
this.linksDouble[2 * i] = new Link(from, to, cap, cost, 0);
this.linksDouble[2 * i + 1] = new Link(to, from, 0, -cost, 0);
// 按照边的标号存储邻接信息
this.G[from].add(2 * i);
this.G[to].add(2 * i + 1);
}
}
/*
* 循环执行SPFA算法，直到SPFA算法返回值是false
*/
private void minCostMaxFlow(int s, int t) {
while (SPFA(s, t))
;
// cost
for (int i = 0; i < this.N; i++) {
if (isServer[i])
cost += Deploy.serverCost;
}
}
/*
* SPFA算法求解最大流最小费用流
*/
private boolean SPFA(int s, int t) {
for (int i = 0; i < this.N; i++) {
d[i] = INT_MAX;
this.isInQueue[i] = false;
}
d[s] = 0;
isInQueue[s] = true;
p[s] = 0;
a[s] = INT_MAX;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(s);
while (!q.isEmpty()) {
int u = (int) q.peek();
q.poll();
isInQueue[u] = false;
for (int i = 0; i < G[u].size(); i++) {
Link l = linksDouble[(int) G[u].get(i)];
if (l.getlBand() > l.getFlow()
&& d[l.getlEndID()] > d[u] + l.getlBCostPerUnit()) {// 满足增广要求
d[l.getlEndID()] = d[u] + l.getlBCostPerUnit();
p[l.getlEndID()] = (int) G[u].get(i);
a[l.getlEndID()] = (a[u] < (l.getlBand() - l.getFlow()) ? a[u]
: (l.getlBand() - l.getFlow()));
if (!isInQueue[l.getlEndID()]) {
isInQueue[l.getlEndID()] = true;
q.offer(l.getlEndID());
}
}
}
}
if (Math.abs(d[t] - INT_MAX) < 100000) {
return false;
}
int u = t;
/**************************************/
int front = 0;
while (u != s) {
// 更新正向边与反向边
linksDouble[p[u]].setFlow(linksDouble[p[u]].getFlow() + a[t]);
linksDouble[p[u] ^ 1].setFlow(linksDouble[p[u] ^ 1].getFlow()
- a[t]);
/****************************************/
front = u;
u = linksDouble[p[u]].getlStartID();
}
/**********************************************************/
if (!this.isServer[front]) {
this.isServer[front] = true;
}
cost = cost + d[t] * a[t];
flow = flow + a[t];
this.costList.add(d[t] * a[t]);
this.flowList.add(a[t]);
return true;
}
/*
* findPath算法
*/
protected static boolean findPath() {
Stack<Integer> pathStack = new Stack<Integer>();
Stack<Integer> nodeStack = new Stack<Integer>();
nodeStack.push(Deploy.superSID);
int u = Deploy.superSID;
int mFlow = Deploy.INT_MAX;
int front = u;
// 寻找一条从源点到汇点的路径
while (u != Deploy.superTID) {
for (int i = 0; i < G[u].size(); i++) {
int linkNum = G[u].get(i);
Link l = linksDouble[linkNum];
if (l.getFlow() <= 0)// 不要考虑负权重的边
continue;
if (l.getFlow() > 0) {// 链路上仍然有流量
mFlow = mFlow < l.getFlow() ? mFlow : l.getFlow();
u = l.getlEndID();
nodeStack.push(u);
pathStack.push(linkNum);
break;
}
}
if (u == front)
return false;
}
/************************************/
// 在路径中的每条边上都删除一个mFlow
while (!pathStack.isEmpty()) {
int linkNum = pathStack.pop();
linksDouble[linkNum]
.setFlow(linksDouble[linkNum].getFlow() - mFlow);
}
String tmpPath = "";
while (!nodeStack.isEmpty()) {
tmpPath = nodeStack.pop() + " " + tmpPath;
}
tmpPath = tmpPath + mFlow;
pathListWithFlow.add(tmpPath);
return true;
}
public List<Integer> getFlowList() {
return flowList;
}
public int getCost() {
return cost;
}
public List<String> getPathListWithFlow() {
return pathListWithFlow;
}
}
/*
* 实现模拟退火算法
*/
class SA {
private static final int INT_MAX = 300000000;
// private static final int T = 1000;// 初始化温度
private static int T;// 初始化温度
private static final double Tmin = 1e-8;// 温度的下界
private static final int K = 100;// 迭代的次数
private static final double delta = 0.98;// 温度的下降率
private static int[] serverInsert = new int[Deploy.nodeNum];
private static boolean[] hasBeenDeleted = new boolean[Deploy.nodeNum];
private static boolean[] hasBeenAdded = new boolean[Deploy.nodeNum];
/*
*
*/
public static void getSA() {
if(Deploy.nodeNum < 600){
T = 1000;
}else{
T = Deploy.consumersNum * Deploy.serverCost;
}
int costBest;
int isSamedCounter = 0;// 计数目前已经有多少次的结果是相同的
// 初始的服务器状态,全部直连消费节点的邻节点
for (int i = 0; i < Deploy.consumersNum; i++)
serverInsert[Deploy.consumers[i].getNeighborID()] = INT_MAX;
// 保存上一次的服务器部署方案
int[] backUp = Arrays.copyOf(serverInsert, Deploy.nodeNum);
// 保存最优的服务器部署方案
int[] bestDeploy = Arrays.copyOf(serverInsert, Deploy.nodeNum);
// 执行SPFA
for (int i = 0; i < Deploy.nodeNum; i++)
Deploy.insertServerLink(Deploy.linksSuper, serverInsert);
Deploy.mcmf = new MinCMaxF(Deploy.linksSuper, Deploy.n,
Deploy.superSID, Deploy.superTID);
// 得到最优解的初始解
costBest = Deploy.mcmf.getCost();
/**************************************************/
System.out.println("costBest:" + costBest);
isSamedCounter = 0;
int costLast = costBest;
int costTmp;
// 随机类
Random random = new Random();
// 迭代过程
// 迭代到找到最优或到时间为止
// 溫度变量
double t = T;
while (t > Tmin) {
//内部迭代
for (int i = 0; i < K; i++) {
Deploy.stopTime = System.currentTimeMillis();
//时间到了,就停止迭代
if (Deploy.stopTime - Deploy.startTime >= 86000){
break;
}
//删除服务器中可删除的度最小的
boolean deleteSuccess = deleteMinium();
boolean addSuccess;
//删除成功
if(deleteSuccess){
costTmp = Deploy.mcmf.getCost();
if(costTmp == INT_MAX){
serverInsert = Arrays.copyOf(backUp, Deploy.nodeNum);
// continue;
}
}else{
hasBeenDeleted = new boolean[Deploy.nodeNum];
}
if(!deleteSuccess){
// deleteSuccess = deleteMinium();
//如果删除读最小的服务器节点失败,则添加度最大的点做服务器
addSuccess = addMaximum();
if(addSuccess){
costTmp = Deploy.mcmf.getCost();
if(costTmp == INT_MAX){
serverInsert = Arrays.copyOf(backUp, Deploy.nodeNum);
// continue;
}
}
if(! addSuccess){
//如果添加度最大的点任然失败,则恢复访问控制hasBeenProcessed
hasBeenAdded = new boolean[Deploy.nodeNum];
// continue;
}
}
/*************************************************/
/**********************测试************************/
//
// for (int j = 0; j < Deploy.nodeNum; j++){
// if(serverInsert[j] == INT_MAX)
// System.out.print(j+" ");
// else{
// System.out.print(0+" ");
// }
// }
// System.out.println();
/*************************************************/
costTmp = Deploy.mcmf.getCost();
/*************************************/
// System.out.println("costTmp:" + costTmp);
// System.out.println("costLast:" + costLast);
// System.out.println("costBest:" + costBest);
if (costTmp < costLast) {
backUp = Arrays.copyOf(serverInsert, Deploy.nodeNum);
costLast = costTmp;
} else {
if (1 / (1 + Math.exp(-(costTmp - costLast) / T)) > random
.nextDouble()) {
// backUp = Arrays.copyOf(serverInsert, Deploy.nodeNum);
// costLast = costTmp;
} else {
serverInsert = Arrays.copyOf(backUp, Deploy.nodeNum);
}
}
}
System.out.println("costBest:" + costBest);
if (costLast < costBest) {
// backUp = Arrays.copyOf(serverInsert, Deploy.nodeNum);
bestDeploy = Arrays.copyOf(backUp, Deploy.nodeNum);
costBest = costLast;
isSamedCounter = 0;
}else{
isSamedCounter++;
}
if (isSamedCounter > 100) {
break;
}
if (Deploy.stopTime - Deploy.startTime >= 86000){
break;
}
// 温度下降
t *= delta;
}
// 执行最优方案
serverInsert = Arrays.copyOf(bestDeploy, Deploy.nodeNum);
for (int i = 0; i < Deploy.nodeNum; i++)
Deploy.insertServerLink(Deploy.linksSuper, serverInsert);
Deploy.mcmf = new MinCMaxF(Deploy.linksSuper, Deploy.n,
Deploy.superSID, Deploy.superTID);
/***************** 寻路,输出路径 ***********************/
while (MinCMaxF.findPath())
;
}
/*
* @para
*/
private static boolean deleteMinium() {
// 删除已有服务器中度最小的那个
/********************************************************/
// Long time1 = System.currentTimeMillis();
for (int i = Deploy.nodeNum - 1; i >= 0; i--) {
if (serverInsert[Deploy.nodeIndexByDegree[i]] == INT_MAX
&& !hasBeenDeleted[Deploy.nodeIndexByDegree[i]]) {//
serverInsert[Deploy.nodeIndexByDegree[i]] = 0;
hasBeenDeleted[Deploy.nodeIndexByDegree[i]] = true;
/*****************************************************/
// System.out.println("删除最小点:" + Deploy.nodeIndexByDegree[i]);
// SPFA
for (int j = 0; j < Deploy.nodeNum; j++)
Deploy.insertServerLink(Deploy.linksSuper, serverInsert);
Deploy.mcmf = new MinCMaxF(Deploy.linksSuper, Deploy.n,
Deploy.superSID, Deploy.superTID);
/********************************************************/
// Long time2 = System.currentTimeMillis();
// System.out.println("****************time2-time1:" + (time2 - time1));
return true;
}
}
return false;
}
private static boolean addMaximum() {
// 从剩余链路节点中选择一个度最大的节点作为服务器节点
/********************************************************/
// Long time1 = System.currentTimeMillis();
for (int i = 0; i < Deploy.nodeNum; i++) {
if (serverInsert[Deploy.nodeIndexByDegree[i]] == 0
&& !hasBeenAdded[Deploy.nodeIndexByDegree[i]]) {
serverInsert[Deploy.nodeIndexByDegree[i]] = INT_MAX;
hasBeenAdded[Deploy.nodeIndexByDegree[i]] = true;
/*****************************************************/
// System.out.println("添加最大点:" + Deploy.nodeIndexByDegree[i]);
// SPFA
for (int j = 0; j < Deploy.nodeNum; j++)
Deploy.insertServerLink(Deploy.linksSuper, serverInsert);
Deploy.mcmf = new MinCMaxF(Deploy.linksSuper, Deploy.n,
Deploy.superSID, Deploy.superTID);
/********************************************************/
// Long time2 = System.currentTimeMillis();
// System.out.println("****************time2-time1:" + (time2 - time1));
return true;
}
}
return false;
}
/*
*
*/
private static void setRandom(int min, int max, int n, HashSet<Integer> set) {
Random random = new Random();
for (int i = 0; i < n; i++) {
int ranInt = random.nextInt(max - min) + min;
if (!set.add(ranInt)) {
i--;
}
}
}
}