分支定界法

#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