2017华为软挑——贪心随机搜索

1. 概述

这一篇文章中讲述了针对本年赛题的一些传统方法，但是这些方法在实际的操作过程中都出现收敛速度缓慢、容易陷入局部最优等情况，导致了无法很快和准确到达“最优”解。但是有些时候最简单原始的方式也是最管用的方式，直接采用贪心和随机结合的算法也能获得意想不到的效果。

这篇文章中介绍的贪心加随机的算法思想便是： 1. 贪心准则 ：对于原始输入的数据时刻定会呈现一个初始解的，那就是与消费节点相连的节点。那么从这些节点开始搜索采用贪心的方式是能够实现下次迭代的结果比上一次的结果更优的，因而这里设置的贪心的准则就是在满足题意需求的情况下，使得总的代价下降。 2. 随机选择的策略 ：这里对于固有的初始解，要对其进行变换使用到的策略就是随机策略。那么随机的策略就包括：随机的删除节点、随机的添加节点、随机的替换节点。下面便是对这些想法的解释： 随机删除节点：在现有的可行解的集合中随机选取一个点将其删除出可行解，再计算当前解的可行性和代价。如果删除之后的解仍然是可行解那么，并且代价减小了，那么接受该删除操作；如果删除之后的解变为不可行或者代价变大，那么则不接受该解。 随机添加节点：在现有可行解的集合的基础上对该集合之外点集中随机选择一个节点添加进来。如果添加之后的解代价减小了，那么接受该添加操作；如果添加之后的解代价变大，那么则不接受添加操作。 随机替换节点：在现有可行解的集合的基础上对该集合之外点集中随机选择一个节点随机替换当前解集合中的一个点。如果替换之后的解代价减小了，那么接受该替换操作；如果替换之后的解代价变大，那么则不接受替换操作。 大体的算法思想便是如上所诉。下面便是对其实现的具体编码。

2. 编码

void xjbs_search() { int flow(0), cost(-1); std::vector<int> cur_vec; // if(net_node_num > 600) { //方案1 for (int i=0; i<client_node_num; i++) { std::vector<SERVER_NODE> vec; int node_num = client_node[i].innode[0]; int temp_size(net_node[node_num].outnode.size()); //输出边 for (int j=0; j<temp_size; j++) { SERVER_NODE temp; temp.cost = net_edge[node_num][net_node[node_num].outnode[j]].bandcost; temp.node_id = net_node[node_num].outnode[j]; vec.push_back(temp); } temp_size = net_node[node_num].innode.size(); //输入边 for (int j = 0; j < temp_size; j++) { SERVER_NODE temp; temp.cost = net_edge[net_node[node_num].innode[j]][node_num].bandcost; temp.node_id = net_node[node_num].innode[j]; vec.push_back(temp); } std::sort(vec.begin(), vec.end(), sort_by_cost); //排序 int flow(client_node[i].bandwidth); int pos(0), cost(0); while ((flow > 0) && (pos<vec.size())) { int temp_flow = net_edge[node_num][vec[pos].node_id].bandwidth; if (flow > temp_flow) { flow -= temp_flow; cost += temp_flow*net_edge[node_num][vec[pos].node_id].bandcost; } else { cost += flow*net_edge[node_num][vec[pos].node_id].bandcost; flow -= flow; } ++pos; } if (cost > server_cost) { must_server.push_back(node_num); } } for (int i=0; i<client_node_num; i++) { if (!CheckIsServer(client_node[i].innode[0], must_server)) {forbid_server.push_back(client_node[i].innode[0]);} } //添加不是服务器的结点 if (0 == must_server.size()) { cur_vec = getserver_pos_by_outflow(client_node_num / 3); } else{ cur_vec = must_server; } flow = 0; cost = -1; my_search_init(cur_vec); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += must_server.size()*server_cost; cout << " cost = " << cost << " flow: " << flow << "/" << needed_flow << endl; //cheack_path(path); //得到流量不足的点 std::vector<SERVER_NODE> vec; //记录花费最多的路和他们的结点 get_maxcost_path(path, vec); //获得代价最大的结点 int cost_pre = cost; //上次运行得到的结果 while (vec.size() > 0) { //int node_num(vec[0].node_id); if (vec.size() > 2) { cur_vec.push_back(vec[0].node_id); cur_vec.push_back(vec[1].node_id); //cur_vec.push_back(vec[2].node_id); } //加速计算，每次加进来三个 else cur_vec.push_back(vec[0].node_id); flow = 0; cost = -1; my_search_init(cur_vec); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += cur_vec.size()*server_cost; cout << " cost = " << cost << " flow: " << flow << "/" << needed_flow << endl; if(flow >= needed_flow) { if(min_cost > cost) { min_cost = cost; min_path = path; min_server = cur_vec; } } //如果在这个时候就满足了条件，那么更新当前的最小权值和路径 vec.clear(); get_maxcost_path(path, vec); } if (min_path.size() != 0) { path = min_path; } std::vector<int> ser1 = cheack_path(path); //得到流量不足的点 if(ser1.size()>0) { //min_cost = MAXINT; for(unsigned int i=0; i<ser1.size(); i++) { if (ser1.size() - i - 1 > 2) { cur_vec.push_back(ser1[i]); cur_vec.push_back(ser1[++i]); //cur_vec.push_back(ser1[++i]); } //加速计算，每次加进来三个 else cur_vec.push_back(ser1[i]); //cur_vec.push_back(ser1[i]); flow = 0; cost = -1; my_search_init(cur_vec); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += cur_vec.size()*server_cost; cout << " cost = " << cost << " flow: " << flow << "/" << needed_flow << endl; if(flow >= needed_flow) { if(cost < min_cost) { min_path = path; min_cost = cost; min_server = cur_vec; } } } } //需要的流量还有没有满足的 cout << "temp min cost is: " << min_cost << "server num: " << min_server.size() << endl; } else { for (int i=0; i<client_node_num; i++) { cur_vec.push_back(client_node[i].innode[0]); } } std::vector<int> search_node; findnew_mincost(cur_vec, search_node); } //减小现在解的话费，cur_vec当前的服务器点集 void findnew_mincost(std::vector<int>& cur_vec, std::vector<int>& search_vec) { int flow = 0, cost = -1; std::vector<int> temp_server = cur_vec; int temp_min = min_cost; //记录操作的最小费用 std::vector<int> temp_min_server = temp_server; int delete_loop = 1; //先进行删除操作 while (true && delete_loop > 0) { int delete_node(-1); while (true) { delete_node = std::rand() % temp_server.size(); if (CheckIsServer(temp_server[delete_node], temp_server) && !CheckIsServer(temp_server[delete_node], must_server)) {break;} } int node = temp_server[delete_node]; //cout << "delete node: " << node << endl; temp_server.erase(temp_server.begin()+delete_node); flow = 0; cost = -1; my_search_init(temp_server); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += temp_server.size()*server_cost; //cout << "first delete node; cost = " << cost << " flow: " << flow << "/" << needed_flow << // "server num: " << temp_server.size() << endl; if (flow >= needed_flow) { if (temp_min > cost) { temp_min = cost; min_cost = cost; min_path = path; temp_min_server = temp_server; } } else { cout << "delete error" << endl; temp_server.push_back(node); --delete_loop; } } temp_server = temp_min_server; cout << "first delete node,cost :" << temp_min << " server num: " << temp_min_server.size() << endl; //进入主循环，开始删除、添加、替换操作 while (true) { temp_server = temp_min_server; //添加操作 int add_node(-1); while (true) { add_node = std::rand() % net_node_num; if (!CheckIsServer(add_node, temp_server)/* && !CheckIsServer(add_node, forbid_server)*/) { break; } } temp_server.push_back(add_node); //cout << "add node: " << add_node << endl; flow = 0; cost = -1; my_search_init(temp_server); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += temp_server.size()*server_cost; if (flow >= needed_flow) { if (temp_min > cost) { //cout << "add find better: " << cost << endl; temp_min = cost; min_cost = cost; min_path = path; temp_min_server = temp_server; } else{temp_server.pop_back();} } //temp_server.pop_back(); //删除操作 int delete_node(-1); while (true) { delete_node = std::rand() % temp_server.size(); if (CheckIsServer(temp_server[delete_node], temp_server) && !CheckIsServer(temp_server[delete_node], must_server)) { break; } } int node = temp_server[delete_node]; //cout << "delete node: " << node << endl; temp_server.erase(temp_server.begin() + delete_node); flow = 0; cost = -1; my_search_init(temp_server); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += temp_server.size()*server_cost; if (flow >= needed_flow) { if (temp_min > cost) { //cout << "delete find better: " << cost << endl; temp_min = cost; min_path = path; min_cost = cost; temp_min_server = temp_server; } else { temp_server.push_back(node); } //删除的点使得消费增加了 不删除 } else { //cout << "delete error" << endl; temp_server.push_back(node); } //删除的点导致流量不满足，不删除 //temp_server.push_back(node); clock_t temp_end = clock(); //替换操作 if (((double)(temp_end - start) / CLOCKS_PER_SEC) < 30 || !(net_node_num>400)) { int replace_node(-1); //替换过程中加进来的点 while (true) { replace_node = std::rand() % net_node_num; if (!CheckIsServer(replace_node, temp_server) /*&& !CheckIsServer(replace_node, forbid_server)*/) { break; } } int replace_pos(-1); while (true) { replace_pos = std::rand() % temp_server.size(); if (CheckIsServer(temp_server[replace_pos], temp_server) && !CheckIsServer(temp_server[replace_pos], must_server)) { break; } } int replace_temp = temp_server[replace_pos]; temp_server.erase(temp_server.begin()+replace_pos); temp_server.push_back(replace_node); //cout << "replace node: " << replace_temp << "====>" << replace_node << endl; flow = 0; cost = -1; my_search_init(temp_server); cost = MinCostFlow(net_node_num, (net_node_num + 1), flow); cost += temp_server.size()*server_cost; if (flow >= needed_flow) { if (temp_min > cost) { //cout << "replace find better: " << cost << endl; temp_min = cost; min_cost = cost; min_path = path; temp_min_server = temp_server; } //else{temp_server.pop_back(); temp_server.push_back(replace_temp); } } //else{temp_server.pop_back(); temp_server.push_back(replace_temp);} } //时间限制 temp_end = clock(); if (((double)(temp_end - start) / CLOCKS_PER_SEC) > search_time) return; } } //现在已经得到了一个可行解，将路径按照代价的大小排序 std::vector<int> sortcost_path(std::vector<std::vector<int> >& m_path) { if (m_path.size() <= 0) { cout << "input path is null" << endl; std::abort(); } int flow[1020]; //统计每个消费节点的流量 int cost[1020]; for (int i = 0; i < net_node_num; i++) { flow[i] = 0; cost[i] = 0; } for (unsigned int i = 0; i < m_path.size(); i++) { flow[m_path[i][0]] += m_path[i][m_path[i].size() - 2]; //累加该节点的流量 cost[m_path[i][0]] += m_path[i][m_path[i].size() - 1]; //累加该节点的花费 } std::vector<int> temp1; std::vector<SERVER_NODE> vec; //计算流量不足的点需要的流量多少 for (int i = 0; i<client_node_num; i++) { if (0 != cost[client_node[i].innode[0]]) { cout << "cost bigger than server cost: " << client_node[i].innode[0] << "; " << cost[client_node[i].innode[0]] << " / " << server_cost << endl; SERVER_NODE temp; temp.cost = cost[client_node[i].innode[0]]; temp.node_id = client_node[i].innode[0]; vec.push_back(temp); } } sort(vec.begin(), vec.end(), sort_by_cost_down); //按照跑出来的代价对点进行排序 int temp_size(vec.size()); for (int i=0; i<temp_size; i++) { temp1.push_back(vec[i].node_id); } return temp1; } //得到当前路径中消耗最大的点 void get_maxcost_path(std::vector<std::vector<int> >& m_path, std::vector<SERVER_NODE>& vec) { if (m_path.size() <= 0) { cout << "input path is null" << endl; std::abort(); } int flow[1020]; //统计每个消费节点的流量 int cost[1020]; for (int i = 0; i < net_node_num; i++) { flow[i] = 0; cost[i] = 0; } for (unsigned int i = 0; i < m_path.size(); i++) { flow[m_path[i][0]] += m_path[i][m_path[i].size() - 2]; //累加该节点的流量 cost[m_path[i][0]] += m_path[i][m_path[i].size() - 1]; //累加该节点的花费 } std::vector<int> temp = min_server; //计算流量不足的点需要的流量多少 for (int i = 0; i<client_node_num; i++) { if (cost[client_node[i].innode[0]] > server_cost) { //cout << "cost bigger than server cost: " << client_node[i].innode[0] << "; " << cost[client_node[i].innode[0]] << // " / " << server_cost << endl; SERVER_NODE temp; temp.cost = cost[client_node[i].innode[0]]; temp.node_id = client_node[i].innode[0]; vec.push_back(temp); } } sort(vec.begin(), vec.end(), sort_by_cost_down); //按照跑出来的代价对点进行排序 } //检查路劲中需要的流量的多少，返回需要增加流量的点 std::vector<int> cheack_path(std::vector<std::vector<int> > m_path) { if(m_path.size()<=0) { cout << "input path is null" << endl; std::abort(); } int flow[1005]; //统计每个消费节点的流量 for(int i=0; i<net_node_num; i++) flow[i] = 0; for(unsigned int i=0; i<m_path.size(); i++) { flow[m_path[i][0]] += m_path[i][m_path[i].size()-2]; } std::vector<int> temp1 = min_server; std::vector<SERVER_NODE> vec; //计算流量不足的点需要的流量多少 for(int i=0; i<client_node_num; i++) { if((flow[client_node[i].innode[0]] - client_node[i].bandwidth) != 0) { cout << "node: "<< client_node[i].innode[0] << " need add flow: " << (client_node[i].bandwidth-flow[client_node[i].innode[0]]) << endl; SERVER_NODE temp; temp.cost = client_node[i].bandwidth-flow[client_node[i].innode[0]]; temp.node_id = client_node[i].innode[0]; vec.push_back(temp); } } sort(vec.begin(), vec.end(), sort_by_cost_down); //按照跑出来的代价对点进行排序 for(unsigned int i=0; i<vec.size(); i++) { temp1.push_back(vec[i].node_id); } return temp1; }