#include <stdio.h> #include <string> #include <iostream> #include <algorithm> #include <iterator> #include <cstdlib> #include <queue> #include "bb_algorithm.h" namespace bb { BranchBound::BranchBound(TspGraph& graph, std::vector<NodeType>& nodes_info) :m_graph(graph), m_nodes_info(nodes_info) { n = nodes_info.size(); } int BranchBound::process(std::vector<int>& result_list) {//最小费用分支定界代码,寻找最短旅行 //bestTour[1:n]存储最短旅行路径 std::priority_queue<HeapNode> liveNodeMinHeap; //costOfMinOutEdge[i]表示顶点i的最小出边 int *minCostOutEdge = new int[n + 1]; int sumOfMinCostOutEdges = 0; for (int i = 0; i < n; ++i) { int minCost = -1; for (int j = 0; j < n; ++j) if (m_graph[i][j] != -1 && (minCost == -1 || minCost > m_graph[i][j])) minCost = m_graph[i][j]; if (minCost == -1) return -1; minCostOutEdge[i] = minCost; sumOfMinCostOutEdges += minCost; } //初始E-节点的根 HeapNode eNode; eNode.lowerCost = sumOfMinCostOutEdges; eNode.currentCost = 0; eNode.restMinCost = sumOfMinCostOutEdges; eNode.s = 0; eNode.currentTour = new int[n]; //初始化排列为[1,2,3,...,n,1] for (int i = 0; i < n; ++i) eNode.currentTour[i] = i; int bestCostSoFar = -1; //当前最佳旅行耗费 int *currentTour = eNode.currentTour; //搜索排列树 while (eNode.s < n - 1) { currentTour = eNode.currentTour; if (eNode.s == n - 2) {//叶结点的父节点 //检查是否为当前最优旅行 if (m_graph[currentTour[n - 2]][currentTour[n - 1]] != -1 && m_graph[currentTour[n - 1]][0] != -1 && (bestCostSoFar == -1 || eNode.currentCost + m_graph[currentTour[n - 2]][currentTour[n - 1]] + m_graph[currentTour[n - 1]][0] < bestCostSoFar)) {//发现最优旅行,加入小根堆 bestCostSoFar = eNode.currentCost + m_graph[currentTour[n - 2]][currentTour[n - 1]] + m_graph[currentTour[n - 1]][0]; eNode.currentCost = bestCostSoFar; eNode.lowerCost = bestCostSoFar; eNode.s++; liveNodeMinHeap.push(eNode); } else { delete[] eNode.currentTour; //舍弃非最优的叶结点的父节点,释放内存 eNode.currentTour = nullptr; } } else {//生成子节点 for(int i = eNode.s + 1; i < n; ++i) if (m_graph[currentTour[eNode.s]][currentTour[i]] != -1) {//子节点可行 int currentCost = eNode.currentCost + m_graph[currentTour[eNode.s]][currentTour[i]]; int restMinCost = eNode.restMinCost - minCostOutEdge[currentTour[eNode.s]]; int leastCostPossible = currentCost + restMinCost; if (bestCostSoFar == -1 || leastCostPossible < bestCostSoFar) {//子树可能有更优的叶结点,把当前子树的根放入小根堆 HeapNode hNode; hNode.lowerCost = leastCostPossible; hNode.currentCost = currentCost; hNode.restMinCost = restMinCost; hNode.s = eNode.s + 1; hNode.currentTour = new int[n]; std::copy(currentTour, currentTour + n, hNode.currentTour); std::swap(hNode.currentTour[hNode.s], hNode.currentTour[i]); liveNodeMinHeap.push(hNode); } } //完成节点扩展,释放内存 delete[] eNode.currentTour; eNode.currentTour = nullptr; } if (liveNodeMinHeap.empty()) break; //取下一个E-节点 eNode = liveNodeMinHeap.top(); liveNodeMinHeap.pop(); } if (bestCostSoFar == -1) return -1; //复制到bestTour for (int i=0; i < n; i++) result_list.push_back(eNode.currentTour[i]); //释放小根堆中剩余元素的currentTour数组内存***虽然小根堆析构, //但是currentTour是new的内存,依然存在,故必须手动释放 while (true) { delete[] eNode.currentTour; if (liveNodeMinHeap.empty()) break; //取下一个E-节点 eNode = liveNodeMinHeap.top(); liveNodeMinHeap.pop(); } return bestCostSoFar; } }
#ifndef _BB_ALGORITHM_H_ #define _BB_ALGORITHM_H_ namespace bb { struct HeapNode { int lowerCost; //当前节点往后排列,整个回路所能取得的总耗费的下限 int currentCost; //从根到当前节点的当前排列的耗费 int restMinCost; //从当前节点到最后一个节点,每个节点的最小出边的耗费之和 int s; //从根节点到当前节点的路径为[0:s] int* currentTour; //从根节点到当前节点的路径(排列) //算术运算时的类型转换 operator int() { return lowerCost; } //重载大于号运算符,用于小根堆比较 bool operator<(const HeapNode &right) const { return lowerCost > right.lowerCost; } }; class BranchBound { public: BranchBound(TspGraph& graph, std::vector<NodeType>& nodes_info); int process(std::vector<int>& result_list); private: Graph& m_graph; std::vector<NodeType>& m_nodes_info; int n; }; } #endif
相关推荐
分支定界法是一种搜索与迭代的方法,选择不同的分支变量和子问题进行分支。对于两个变量的整数规划问题,使用网格的方法有时更为简单。 [1] 通常,把全部可行解空间反复地分割为越来越小的子集,称为分支;并且对每...
分支定界法例题
最优化方法的整数规划的分支定界方法 整数线性规划的求解 求解整数规划的割平面法 整数规划的分支定界法
该.m文件使用分支定界法来求解TSP问题
pythonpython解决TSP问题以及采用分支定界法解决TSP问题并对比python解决TSP问题以及采用分支定界法解决TSP问题并对比python解决TSP问题以及采用分支定界法解决TSP问题并对比python解决TSP问题以及采用分支定界法...
分支定界法的matlab程序,有详细注释
分支定界伪代码.txt
整数线性规划分支定界法,可求解纯整数规划和混合整数规划
分支定界法python实现,一个例子,可以供研究学习用
分支定界法、割平面法、隐式枚举法的整数规划matlab源代码.zip
该rar包中包含了个人设计出的分支定界法-旅行商(TSP)问题算法开发,其中开发语言为JAVA,请各位小伙伴下载下来后不要随便传发,谢谢支持!
用Matlab实现求解混合整数规划的分支定界法。还不是很完善,可以在上面修改。
运用matlab软件,使用分支定界法编程,求解整数规划问题。
用分支定界算法求以下问题: 某公司于乙城市的销售点急需一批成品,该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座城市,互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的...
分支定界法MATLAB程序及详细过程,老师让做的作业,有需要的可以看看
0-1整数 分支定界 matlab 采用分支定界方法和matlab自带优化工具求解
数学建模-整数规划-分支定界法的MATLAB实现。对于数学建模很有帮助,祝大家在建模中取得好成绩。程序已经经过调试,可以运行
利用MATLAB实现了分支定界法,内有三个.m文件,含有中文注释。
运筹学上机实验,用Matlab实现分支定界法求解整数线性规划问题。
分支定界算法实现