算法实际应用集（上）
2019-06-04 本文已影响2人
beiq
使用笛卡尔算法进行sku组合
需求
对商品规格进行排列组合，电商的sku商品组合
功能截图，对商品规格进行组合排列
image
image
image
图中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直接返回
}
}
快递员配送距离问题
需求
比如美团啊饿了么，或者是电商类的平台，需要配送餐饮和商品，这时候快递员送餐员手里有多个订单，这时候要告诉他应该以最优的路线进行配送
[图片上传失败...(image-ed52b-1559636263098)]
这是几个送餐点，这个需求就是找出最优化路线。
核心代码
/**
* 定义一个最小堆对象
*/
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")
最少找零问题
需求
其实这个需求是我假想的，因为现实中比如我在地铁站购买饮料，很少投入大面额的一百去一瓶饮料，基本上比较接近，但是如果真的投入了一百，这时候机器给我吐出来90个硬币我就崩溃了。所以，我更希望它以50,20，这样的最佳相加结果给我，如果在这个机器已经有这个功能了，那是我没用到，如果没有我想应该加个，不过现在大部分人使用扫码支付了。
核心代码 贪心算法
function MinCoinChange(coins) {
var coins = coins;
this.makeChange = function (amount) {
var change = [],total = 0;
for(var i = coins.length; i >= 0; i--) {
var coin = coins[i];
while(total + coin <= amount) {
change.push(coin);
total += coin;
}
}
return change;
};
}
//机器能够输出的钱币面额种类[1,5,10,20,50，100]
let typeMoney = [1,5,10,20,50，100]
var minCoinChange = new MinCoinChange(typeMoney);
// 投入的钱面额
let maxMoney = 100
console.log(minCoinChange.makeChange(maxMoney))
//代码核心思维就是从最大的开始拿，并且对结果累加，去和剩下的小面额的相加，直到和maxMoney的数额相等为止。
程序本身还需要一些完善，比如这段代码里还要对现有各种类型钱币个数做个实时统计，所以钱币类型也是动态的，如果没有100的就重新从50开始计算.
