营销型网站建设要求,app软件开发软件,新媒体运营公司排名,东莞市市场监督管理局官网1. 辅助函数
Node算子用来存储搜索树的状态。其中level等于path的长度#xff0c;path是当前节点已经访问过的vertex清单#xff0c;bound则是当前的lb。 这里的bound函数是一种启发式方法#xff0c;等于当前路径的总长度#xff0c;再加上往后走两步的最小值。
struct …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[i1]] 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_boundminimum([adj_mat[r,i] for i in setdiff(p,r)])endreturn _bound
end;2. 分枝定界代码
这里用priorityQueue存储节点用Queue也是一样的。 分枝条件为boundub往下搜索所有没有探访过的节点使用函数setdiff(1:n,v.path)。当然这里可以尝试将搜索范围缩小比如仅搜索最近的一些节点不过就不保证最优性了。 当搜索到leveln-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.boundublevel v.level1b 0for i in setdiff(1:n,v.path)path [v.path;i]if leveln-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问题当点数增多时使用bb的算法性能会急速下降。
