算法实际应用集

图中16和9是商品的分类id，分类id和商品id用竖杆分隔，为了后续根据id去查抄回显使用。有了这些组合的结果就可以做后续一些列操作。

核心代码，使用笛卡尔乘积，递归调用组合

function doExchange(doubleArrays) {
    var len = doubleArrays.length;
    if (len >= 2) {
        var arr1 = doubleArrays[0];
        var arr2 = doubleArrays[1];
        var len1 = doubleArrays[0].length;
        var len2 = doubleArrays[1].length;
        var newlen = len1 * len2;
        var temp = new Array(newlen);
        var index = 0;
        for (var i = 0; i < len1; i++) {
            for (var j = 0; j < len2; j++) {
                temp[index] = arr1[i] + "," + arr2[j];
                index++;
            }
        }
        //先把前两个数组进行组合
        var newArray = new Array(len - 1);
        newArray[0] = temp;

        if (len > 2) {
            var _count = 1;
            for (var i = 2; i < len; i++) {
                newArray[_count] = doubleArrays[i];
                _count++;
            }
        }
        //创建新数组，把前两项组合后数组作为新数组第一项，从原数组第二项开始，剩余未组合的值放进新数组，递归调用新数组进行组合
        return this.doExchange(newArray);
    } else {
        return doubleArrays[0];
        //长度小于2直接返回
    }
}
复制代码

需求

比如美团啊饿了么，或者是电商类的平台，需要配送餐饮和商品，这时候快递员送餐员手里有多个订单，这时候要告诉他应该以最优的路线进行配送

这是几个送餐点，这个需求就是找出最优化路线。

核心代码

/**
 * 定义一个最小堆对象
 */
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")
复制代码

最短距离的参考链接