运筹系列83：使用分枝定界求解tsp问题

1. 辅助函数

Node算子用来存储搜索树的状态。其中level等于path的长度，path是当前节点已经访问过的vertex清单，bound则是当前的lb。
这里的bound函数是一种启发式方法，等于当前路径的总长度，再加上往后走两步的最小值。

struct Nodelevel::Intpath::Vector{Int64} bound::Int
endfunction totaldist(adj_mat::Array{Int64,2},t::Vector{Int64} )n = length(t)sum([adj_mat[t[i],t[i+1]] for i in 1:n-1])+adj_mat[t[n],t[1]] 
endfunction bound(adj_mat::Array{Int64,2}, path::Vector{Int64} )_bound = 0n = size(adj_mat)[1]determined, last = path[1:end-1], path[end]remain = setdiff(1:n,path)for i in 1:length(path)-1;_bound += adj_mat[path[i],path[i + 1]];end_bound += minimum([adj_mat[last,i] for i in remain])p = [path[1];remain]for r in remain_bound+=minimum([adj_mat[r,i] for i in setdiff(p,r)])endreturn _bound
end;

2. 分枝定界代码

这里用priorityQueue存储节点，用Queue也是一样的。
分枝条件为bound<ub，往下搜索所有没有探访过的节点，使用函数setdiff(1:n,v.path)。当然这里可以尝试将搜索范围缩小，比如仅搜索最近的一些节点，不过就不保证最优性了。
当搜索到level==n-1时，获得一个可行解，并且停止往下探索。此时如果路径长度比ub还短，则更新ub。

function solve(adj_mat::Array{Int64,2},ub::Int64 = 10^9)optimal_tour = Vector{Int64}()optimal_length = 0n = size(adj_mat)[1]PQ = PriorityQueue{Node,Int}()path = Vector{Int64}([1])v = Node(1,path,bound(adj_mat,path))enqueue!(PQ,v,v.bound) while length(PQ)>0v = dequeue!(PQ)if v.bound<ublevel = v.level+1b = 0for i in setdiff(1:n,v.path)path = [v.path;i]if level==n-1 #终止条件push!(path,setdiff(1:n,path)[1])_len = totaldist(adj_mat,path)if _len < ubub = _lenoptimal_length = _lenoptimal_tour = pathendelse # 进行分叉b = bound(adj_mat,path)if b < ub # 分枝条件enqueue!(PQ,Node(level,path,b),b)endendendendendoptimal_tour,optimal_length
end
solve([0 14 4 10 20;14 0 7  8  7;4  5  0  7  16;11 7 9 0 2;18 7 17 4 0])

输出([1, 4, 5, 2, 3], 30)。
TSP时一个NPhard问题，当点数增多时，使用b&b的算法性能会急速下降。