快递小哥在送快递时，需要考虑优先顺序的问题，在由多个派送点构成的网络中，规划好派送顺序，既省时又省力。因此，最优路线问题就出来了。
如下图所示，我们从A点出发，计划要到B、C、D、E、F五个派送点，最后返回到A点。
地图草图
从A出发，走过B、C、D、E、F五个点的顺序组合如下图所示，一共有5! = 120种，我们需要在这120种顺序组合中找到最省时省力的结果。
解空间树示意图
我们可以依次计算120种每个组合情况的耗费情况，然后依次进行比较，但是，当我们问题中所要涉及的节点增多时，我们计算的复杂度就会指数级增长。为了优化，我们采用了优先队列式分支限界算法。
我们使用无向带权图G=(V，E)描述整个路径网络，结点代表派送点，连线上的数字代表点与点之间的路径长度（或者耗费值）。
路径网络
我们采用带权邻接矩阵map[][]记录无向带权图。map[i][j]等于路径的长度，-1表示路径不可通INF。
// 定义不可达路径值 -1
const INF = -1
// 带权邻接矩阵map[][]记录无向带权图
var map = [
[ -1, 8, 6,12,14,32],
[ 8, -1, 8,30, 6,20],
[ 6, 8, -1, 8, 5, 4],
[12,30, 8, -1,20,12],
[14, 6, 5,20, -1, 4],
[32,20, 4,12, 4, -1],
]
-
我们用数组x_current[]表示解向量，也就是记录当前路径的节点顺序数组。初始值为:x = [0,1,2,3,4,5]
-
我们用数组xBest[]表示最优解向量，也就是记录最优路径的节点顺序数组。初始值为：xBest[] = [0,0,0,0,0,0]
-
我们用cost表示当前已走过的路径耗费，初始值为0。
-
我们用costBest表示最优路径耗费，初始值为-1。
-
我们用heap_min表示最小优先队列，当前已走过的路径耗费值（TSPNode.cost）越小，越优先即处在堆的顶部。
代码详解
A、B、C、D、E、F六个节点分别用序号0、1、2、3、4、5代替。
最小堆heapMin
最小堆的性质就是：堆中的最小元素始终处在堆的顶部。本代码中为了TSP求解需要，以TSPNode的cost属性值的大小作为最小堆的比较操作。
- adjust：维持最小堆性质
- push：向堆中插入一个元素，本例中TSPNode
- pop：弹出堆顶元素，即当前堆中最小的元素
- empty：检测堆是否为空
/**
* 定义一个最小堆对象
*/
var heapMin = function () {
this.set = [];
}
/**
* 调整堆使其满足最小堆性质
*/
heapMin.prototype.adjust = function (index) {
let len = this.set.length
let l = index * 2 + 1
let r = index * 2 + 2
let min = index
let node = null
if (l <= len -1 && this.set[min].cost > this.set[l].cost) {
min = l
}
if (r <= len -1 && this.set[min].cost > this.set[r].cost) {
min = r
}
if (min != index) {
node = this.set[index];
this.set[index] = this.set[min]
this.set[min] = node
this.adjust(min)
}
}
/**
* 插入一个元素
*/
heapMin.prototype.push = function (node) {
this.set.push(node)
for (let i = Math.floor(this.set.length / 2); i >= 0; i--) {
this.adjust(i)
}
}
/**
* 移除最小元素
*/
heapMin.prototype.pop = function () {
let node
node = this.set.shift()
this.adjust(0)
return node
}
/**
* 获取当前堆大小
*/
heapMin.prototype.size = function () {
return this.set.length
}
/**
* 堆是否为空
*/
heapMin.prototype.empty = function () {
return this.set.length === 0 ? true : false
}
解空间树节点TSPNode
- x[]：记录当前解节点序号数组
- cost：记录从开始节点到此节点的路径耗费值
- index：记录当前节点在解向量数组中的索引值
扩展子节点
当前节点cNode的解向量数组中从cNode.index(cIndex = cNode.index)往后的节点都是未遍历的节点，因此
// 遍历cNode.x[]
for(let j = cIndex; j < num; j++) {
// ...
}
遍历过程中，判断是否可以到达每个节点，即：
map[cNode.x[cIndex-1]][cNode.x[j]] != INF
如果可以到达，计算到达每个节点的路径耗费值cost，如果cost大于当前最优路径耗费值costBest，那么就不需要进行扩展，不加入最小堆中，这样一来就可以大大提搜索速率。
// 利用当前节点在其解向量中的索引获得上一个节点即cIndex-1的序号，如果x[cIndex-1]节点与x[j]节点有边相连
if (map[cNode.x[cIndex-1]][cNode.x[j]] != INF) {
// 计算到达此节点的路径耗费
let cost = cNode.cost + map[cNode.x[cIndex-1]][cNode.x[j]]
// 对于那些路径耗费大于当前最优路径耗费的子节点，不需要扩展（也称为剪掉），即不加入最小堆中。当前路径耗费更小即cost < this.costBest，加入最小堆中
if (this.costBest === INF || cost < this.costBest) {
// 当前走过的路径耗费， 节点层数+1
let node = new TSPNode(cost, cIndex +1)
// 复制之前的解向量
for (let i = 0; i < num; i++) {
node.x[i] = cNode.x[I]
}
// 更新当前节点解向量
let tmp = node.x[cIndex]
node.x[cIndex] = node.x[j]
node.x[j] = tmp
// 加入最小堆中
heap_min.push(node)
}// end if
}// end if
完整代码
/**
* 定义一个最小堆对象
*/
var heapMin = function () {
this.set = [];
}
/**
* 调整堆使其满足最小堆性质
*/
heapMin.prototype.adjust = function (index) {
let len = this.set.length
let l = index * 2 + 1
let r = index * 2 + 2
let min = index
let node = null
if (l <= len -1 && this.set[min].cost > this.set[l].cost) {
min = l
}
if (r <= len -1 && this.set[min].cost > this.set[r].cost) {
min = r
}
if (min != index) {
node = this.set[index];
this.set[index] = this.set[min]
this.set[min] = node
this.adjust(min)
}
}
/**
* 插入一个元素
*/
heapMin.prototype.push = function (node) {
this.set.push(node)
for (let i = Math.floor(this.set.length / 2); i >= 0; i--) {
this.adjust(i)
}
}
/**
* 移除最小元素
*/
heapMin.prototype.pop = function () {
let node
node = this.set.shift()
this.adjust(0)
return node
}
/**
* 获取当前堆大小
*/
heapMin.prototype.size = function () {
return this.set.length
}
/**
* 堆是否为空
*/
heapMin.prototype.empty = function () {
return this.set.length === 0 ? true : false
}
// 定义不可达路径值 -1
const INF = -1
// TSP解空间树节点
function TSPNode (cost, index) {
// 节点解向量
this.x = []
// 当前走过的路径耗费值
this.cost = cost
// 当前节点在其解向量中的index
this.index = index
}
/**
* TSP对象
* map: 地图，采用邻接矩阵的方式表示无向图G
*/
function TSP (map) {
// 检查地图数组合法性 n*n数组
if (map === undefined || !Array.isArray(map) || map.length < 0 || !Array.isArray(map[0]) || map.length != map[0].length) {
return console.error('map非法！')
}
// 赋值地图数组
this.map = map
// 节点数量
this.number = map.length
// 当前最优路径耗费
this.costBest = INF
// 最优解向量数组
this.xBest = []
}
/**
* 计算最佳路径
* 返回值：cost，最佳路径耗费；routine，路径
*/
TSP.prototype.getBestRoutine = function () {
// 暂存地图数组
let map = this.map
// 暂存节点数量
let num = this.number
// 创建一个最小堆
let heap_min = new heapMin()
// 创建初始节点，因为从节点0出发，所以 cost=0，index=1
let startNode = new TSPNode(0, 1)
// 初始化解向量，数组中存储的是节点的序号，对应map中的索引，如：[0,1,...,n]
for (let i = 0 ; i < num; i++) {
startNode.x[i] = I
}
// 加入最小堆
heap_min.push(startNode)
// 开始搜索
while (!heap_min.empty()) {
// 取出当前节点
var cNode = heap_min.pop()
// 当前节点id
var cIndex = cNode.index
// 搜索至倒数第二个节点时停止
if (cIndex === num) {
// 当前点可到达，并且当前点可以到达初始点
if (map[cIndex-2][cNode.x[cIndex-1]] != INF && map[cNode.x[cIndex-1]][0] != INF) {
// 找到一个最优解，进行记录
if (this.costBest === INF || cNode.cost + map[cNode.x[cIndex-1]][0] < this.costBest) {
this.costBest = cNode.cost + map[cNode.x[cIndex-1]][0]
// 复制最优解向量
for (let i=0; i < num; i++) {
this.xBest[i] = cNode.x[I]
}
}
continue
}
}
// 判断当前节点是否满足限界条件，如果不满足就不需要进行扩展
if (this.costBest !== INF && cNode.cost >= this.costBest) {
continue
}
// 没有到达叶子节点，扩展子节点，对于那些路径耗费大于当前最优路径耗费的子节点，不需要扩展（也称为剪掉），即不加入最小堆中
for(let j = cIndex; j < num; j++) {
// 利用当前节点在其解向量中的索引获得上一个节点即cIndex-1的序号，如果x[cIndex-1]节点与x[j]节点有边相连
if (map[cNode.x[cIndex-1]][cNode.x[j]] != INF) {
// 计算到达此节点的路径耗费
let cost = cNode.cost + map[cNode.x[cIndex-1]][cNode.x[j]]
// 对于那些路径耗费大于当前最优路径耗费的子节点，不需要扩展（也称为剪掉），即不加入最小堆中。当前路径耗费更小即cost < this.costBest，加入最小堆中
if (this.costBest === INF || cost < this.costBest) {
// 当前走过的路径耗费， 节点层数+1
let node = new TSPNode(cost, cIndex +1)
// 复制之前的解向量
for (let i = 0; i < num; i++) {
node.x[i] = cNode.x[I]
}
// 更新当前节点解向量
let tmp = node.x[cIndex]
node.x[cIndex] = node.x[j]
node.x[j] = tmp
// 加入最小堆中
heap_min.push(node)
}// end if
}// end if
}// end for 扩展子节点
}// end while 搜索
// 返回最优解向量
return {
cost: this.costBest,
routine:this.xBest.join('-->')
}
}
/**
* map 地图数组
* -1 : 表示不可达INF
**/
var map = [
[ -1, 8, 6,12,14,32],
[ 8, -1, 8,30, 6,20],
[ 6, 8, -1, 8, 5, 4],
[12,30, 8, -1,20,12],
[14, 6, 5,20, -1, 4],
[32,20, 4,12, 4, -1],
]
// 创建一个TSP对象
var beginTime, endTime, res
var tsp = new TSP(map)
beginTime = new Date()
res = tsp.getBestRoutine()
endTime = new Date()
console.log("cost: "+ res.cost +"\r\nroutine: " + res.routine+"\r\nexecute time:" + (endTime-beginTime) + "ms")
测试结果：
cost: 42
routine: "0-->1-->4-->5-->2-->3"
execute time: 1ms
算法复杂度
时间复杂度
根据排列组合，n个节点总共可以有n!种情况，在最坏的情况下，也就是对每种情况都进行遍历，那么总共需要进行n!次，因此时间复杂度为O(n!)。
空间复杂度
解向量数组x[]占用空间为O(n)，在最坏的情况下，解空间树节点为O(n!)。因此算法的空间复杂度为O(n*n!)。
网友评论