球球排序最优解
一、相应游戏可微信搜索 球球排序
二、效果图
三、实现代码
<!DOCTYPE html><html lang="en">
<head>
<meta charset="UTF-8">
<title>球球排序最优解</title>
<style>
.mt20 {margin-top: 20px;}
.boll {width:50px;height:50px;border-radius: 50%;display: inline-block;margin-right:10px;position:relative}
.bollNum {width:20px;height:20px;text-align:center;line-height: 20px;position:absolute;top:0;right:0;border-radius: 50%;background: #FF00FF;}
.contain{width:52px;height:210px;border: 1px solid #C0C0C0;margin-right:20px;float:left;display: flex;flex-direction: column-reverse;}
.active{border: 2px solid #FF00FF;}
.bgeee{background: #eeeeee;}
.btn{width: 160px;height: 30px;text-align: center;line-height: 30px;border: 1px solid #eeeeee;background: #00FF00;position: absolute;top: 140px;left: 600px;}
.btn:hover{cursor: pointer;color:#fff;}
.t110{top:110px;}
.bg0000FF {background: #0000FF;}
.box{width:1000px;height:350px;background: #fff;position:absolute;top:150px;left:200px;padding:30px;border:10px solid #eee;}
.box_contain{width:100%;height:70px;}
.close{width:30px;height:30px;text-align:center;line-height:30px;position:absolute;top:0;right:0;border-radius:50%;background:#FF0000;}
.l800{left: 800px;}
.l1000{left: 1000px;}
.w60{width:60px;}
</style>
</head>
<body>
<div>相应游戏可微信搜索 球球排序</div>
<div>最好用谷歌浏览器按F12，打开调试，找到console模块，查看当前计算状态</div>
<div>依赖的vue.js文件为线上的，可下载到本地，切换依赖</div>
<div id="mvvm" class="mt20">
<div>
管子数量：<input type="text" v-model="pipeNum">
空管子数量：<input type="text" v-model="emptyNum">
最大步数：<input type="text" v-model="maxStepSet">
最大结果数量：<input type="text" v-model="maxNum">
遍历开始数：<input type="text" v-model="startIndex">
</div>
<div class="mt20">
<div v-for="(item, index) in colorArr" class="boll" :style="{background: item.name}" @click="bollClick(index)" :key="index">
<div class="bollNum">{{item.value}}</div>
</div>
</div>
<div class="mt20">
<div class="contain" :class="{'active': activeNum == index, 'bgeee': index > pipeNum}" v-for="index of totalNum" @click="containClick(index)" :key="index">
<div v-for="item in containArr[index-1]" class="boll" :style="{background: colorStoreArr[item-1]}" :key="item"></div>
</div>
</div>
<div class="btn" @click="startClick(2)" title="直接算出最少的步数，耗时">从最少两步开始计算</div>
<div class="btn l800" @click="startClick(1)" title="可减少计算的次数">从最大步数开始计算</div>
<div class="btn l1000 w60 bg0000FF" @click="reset">重置</div>
<div>
结果：
<div>步数：{{resArr.length?steps: ''}}</div>
路径：点击可动画展示解法
<div v-for="item in resArr" @click="animate(item)">
{{item}}
</div>
</div>
<div v-if="isShow" class="box">
<div class="box_contain">
<div class="boll" :style="{background: colorStoreArr[index_ani-1], transform: 'translate(' + activeX + 'px)'}" v-show="isShowActive"></div>
</div>
<div class="contain" :class="{'active': activeNum_ani == index}" v-for="index of totalNum_ani" :key="index">
<div v-for="item in arr[index-1]" class="boll" :style="{background: colorStoreArr[item-1]}" :key="item"></div>
</div>
<div class="close" @click="close">X</div>
</div>
</div>
<script></script>
<!-- <script></script> -->
<script>
var vm = new Vue({
el: '#mvvm',
data: {
pipeNum: 3,
emptyNum: 2,
colorArr: [],
colorStoreArr: ["#EE1111", "#FCFC9D", "#77FF77", "#0029CC", "#00FFFF", "#FF99FF", "#990099", "#88CE20", "#999999"],
containArr:[],
activeNum: 1,
startIndex: 0,
maxNum: 1,
maxStepSet: 30,
maxStep: 2,
isFirst: true,
resNum: 0,
loadObj: {},
arr: [],
isShow: false,
activeNum_ani: 1,
totalNum_ani: 5,
arrCopy: [],
index_ani: 1,
isShowActive: true,
activeX: 0,
resArr: [],
steps: 0
},
created: function () {
var self = this
self.colorStoreArr.forEach(function(item) {
var obj = {}
obj.name = [item]
obj.value = 4
self.colorArr.push(obj)
})
},
computed: {
totalNum: function() {
var tmpVal = parseInt(this.pipeNum) + parseInt(this.emptyNum)
return tmpVal
}
},
methods: {
isPlainObject(obj) {
return Object.prototype.toString.call(obj) === '[object Object]';
},
isArray(obj) {
return Object.prototype.toString.call(obj) === '[object Array]';
},
copy(obj, deep) {
var self = this
if (obj === null || typeof obj !== "object") {
return obj
}
var i, target = Array.isArray(obj) ? [] : {}, value;
for (i in obj) {
value = obj[i]
if (deep && (self.isArray(value) || self.isPlainObject(value))) {
target[i] = self.copy(value, true);
} else {
target[i] = value;
}
}
return target
},
// 判断数组行的数量是否满员，且子成员都相等
isSame(arr) {
if (arr.length != 4) {
return false
}
return arr.every(function(value, index, arr) {
return value === arr[0]
})
},
// 判断数组行的子成员从0开始就相等，后期不做移动 如[[1,1,1]]
isHalfSame(arr, val) {
if (!arr.length || arr.length === 4) {
return false
}
return arr.every(function(value, index, arr) {
return val? (value === val) : (value === arr[0])
})
},
// 二重数组按长度及值大小排序
sortLen(arr1, arr2) {
if (arr1.length < arr2.length) {
return 1;
} else if (arr1.length > arr2.length) {
return -1;
}
var num1 = parseInt(arr1.join("") || 0)
var num2 = parseInt(arr2.join("") || 0)
if(num1 < num2) {
return 1
} else if (num1 > num2) {
return -1;
} else {
return 0
}
},
// 判断是否结束
isOver(arr) {
let res = true
for (var i = 0; i < arr.length; i++) {
if (arr[i].length) {
if (arr[i].length !== 4) {
res = false;
break;
} else {
var tmpRes = arr[i].every(function(curVal, index, array) {
return curVal === array[0]
})
if (!tmpRes) {
res = false;
break;
}
}
}
}
return res
},
// 验证重复元素，有重复返回元素值；否则返回false
repeatArr(arr) {
var hash = {};
var tmpArr = []
for(var i in arr) {
if(hash[arr[i]]) {
tmpArr.push(arr[i]);
}
// 不存在该元素，则赋值为true，可以赋任意值，相应的修改if判断条件即可
hash[arr[i]] = true;
}
if(tmpArr.length) {
return tmpArr
} else {
return false;
}
},
// 是否死循环
isDead (arr) {
var self = this
let res = true
let tmpArr = []
// 将数组的最后一项，重新组成一个数组
for (var i = 0; i < arr.length; i++) {
// 有空数组直接跳出循环，返回false
if(!arr[i].length) {
res = false;
break;
}
tmpArr.push(arr[i][arr[i].length - 1])
}
// 无空数组
if (res) {
// 最后一项数组都无重复
let repeatArrRes = self.repeatArr(tmpArr)
if (!repeatArrRes) {
return res = true
} else {
for (var i = 0; i < repeatArrRes.length; i++) {
var tmpRes = arr.some(function(item, index, array) {
return (item[item.length - 1] == repeatArrRes[i]) && (array[index].length < 4)
})
if (tmpRes) {
res = false;
break;
}
}
}
}
return res
},
factorial(arr, circle, id) {
var self = this
// 备份数组，不更改原来的
var copyArr = self.copy(arr, true)
circle = circle || 0
circle += 1
if (self.resNum >= self.maxNum) {
return
}
if(self.isDead(copyArr)) {
console.log('isDead(copyArr)=======')
return
}
if(self.isOver(copyArr)) {
console.log('isOver(copyArr)=======')
self.steps = circle - 1
self.resArr.push(id)
self.resNum += 1
return
}
// 第一次从第几行开始遍历
let startI = self.isFirst? parseInt(self.startIndex): 0
for (var i = startI; i < copyArr.length; i++) {
self.isFirst = false
// []不做处理
if (!copyArr[i].length) {
continue
}
// 已完成不做处理，如[1,1,1,1]
if (self.isSame(copyArr[i])) {
continue
}
// console.log("circle - i====" + circle + '-' + i)
for (var j = 0; j < copyArr.length; j++) {
if (i == j) {
continue
}
let copyArrJ = self.copy(copyArr, true)
var arrI = copyArrJ[i]
var arrJ = copyArrJ[j]
// 满员不做接收项
if(arrJ.length == 4) {
continue
}
// 最后一项不相等 且 arrJ不为空数组 直接跳过
if (arrI[arrI.length - 1] !=arrJ[arrJ.length - 1] && arrJ.length) {
continue
}
let isHalfSameI = self.isHalfSame(copyArr[i])
// 如果copyArr[i]是isHalfSame，copyArr[j]是[]不做移动，直接跳过
if (isHalfSameI && !arrJ.length) {
continue
}
// 如果copyArr[i]是isHalfSame，copyArr[j]是isHalfSame，且i个数大于j,直接跳过
if (isHalfSameI && self.isHalfSame(arrJ) && (arrI.length > arrJ.length)) {
continue
}
if(id) {
let tmpArr = id.split('+')
let lastArr = tmpArr[tmpArr.length - 1].split('-')
// A > B后 不能再 B > A
if (lastArr[0] == (j + 1) && lastArr[1] == (i + 1)) {
continue
}
// 超出最大步数要求
if (tmpArr.length > (self.maxStep - 1)) {
console.log('超出最大步数===' + self.maxStep + ' id==' + id)
continue
}
}
console.log("circle -- i+1 -- j+1====" + circle + '--' + (i + 1) + "--" + (j + 1))
var popVal
popVal = arrI.pop()
arrJ.push(popVal)
// 已存在当前情况，且循环步数比当前少，直接跳过 忽略第二重数组的排序
var tmpArrJ1 = self.copy(copyArrJ, true)
tmpArrJ1.sort(self.sortLen)
var loadItem = self.loadObj[JSON.stringify(tmpArrJ1)]
if (loadItem && loadItem <= circle) {
continue
} else {
var tmpArrJ2 = self.copy(copyArrJ, true)
tmpArrJ2.sort(self.sortLen)
self.loadObj[JSON.stringify(tmpArrJ2)] = circle
}
var tmpId
tmpId = id? (id + '+' + (i + 1) + '-' + (j + 1)): ((i + 1) + '-' + (j + 1))
self.factorial(self.copy(copyArrJ, true), circle, tmpId)
}
}
},
containClick(index) {
var self = this
if (self.activeNum == index && self.containArr[index - 1] && self.containArr[index - 1].length) {
var popVal = self.containArr[index - 1].pop()
self.colorArr[popVal - 1].value += 1
} else {
if (index > self.pipeNum) {
return
}
self.activeNum = index
}
},
bollClick(index) {
var self = this
if (!self.colorArr[index].value || (self.containArr[self.activeNum-1] && self.containArr[self.activeNum-1].length >= 4)) {
return
}
self.colorArr[index].value -= 1
if (self.isArray(self.containArr[self.activeNum-1])) {
self.containArr[self.activeNum - 1].push(parseInt(index) + 1)
} else {
self.containArr[self.activeNum - 1] = []
self.containArr[self.activeNum - 1].push(parseInt(index) + 1)
}
},
start() {
var self = this
console.log('start==============')
// console.log(JSON.stringify(self.colorArr))
// console.log(JSON.stringify(self.containArr))
self.resArr = []
self.resNum = 0
self.isFirst = true
self.loadObj = {}
var isColorArrOk = self.colorArr.every(function(item, index) {
return item.value == 4 || item.value == 0
})
var isContainArrOk = self.containArr.every(function(item, index) {
return item.length == 4
})
if(isColorArrOk && isContainArrOk && self.containArr.length == self.pipeNum) {
var arr = self.copy(self.containArr, true)
for (var i = 0; i < self.emptyNum; i++) {
arr.push([])
}
self.arrCopy = self.copy(arr, true)
self.factorial(arr)
console.log('resArr========maxStep=======================' + self.maxStep)
console.log(JSON.stringify(self.resArr))
return self.resArr
} else {
alert('数据不对，请重新选择')
}
},
startClick(index) {
var self = this
self.maxStep = 2
if (index == 1) {
self.maxStep = self.maxStepSet
}
self.loop()
},
loop () {
var self = this
var resArr = self.start()
if(!resArr.length && self.maxStep < self.maxStepSet) {
self.maxStep += 1
self.loop()
}
},
reset () {
var self = this
self.containArr = []
self.colorArr.forEach(function(item) {
item.value = 4
})
self.resArr = []
self.resNum = 0
self.isFirst = true
self.loadObj = {}
},
animate(key) {
var self = this
self.arr = self.copy(self.arrCopy, true)
self.totalNum_ani = self.arr.length
self.isShow = true
var tmpArr = key.split("+")
var timer_step = null
var i = 0
function step() {
window.clearTimeout(timer_step)
if (i >= tmpArr.length) {
return
}
var currentArr = tmpArr[i].split("-")
i += 1
self.index_ani = self.arr[parseInt(currentArr[0]) - 1].pop()
self.activeNum_ani = parseInt(currentArr[0])
self.activeX = 75 * (parseInt(currentArr[0]) - 1)
self.isShowActive = true
var resX = 75 * (parseInt(currentArr[1]) - 1)
var rate = 50 / 1500 * (resX - self.activeX) // 每50毫秒移动量,移动1秒到达
var timer = null;
function move () {
window.clearTimeout(timer)
if (self.activeX >= resX) {
setTimeout(function() {
self.arr[parseInt(currentArr[1]) - 1].push(self.index_ani)
self.isShowActive = false
},50)
return
}
self.activeX += rate
timer = window.setTimeout(move,50)
}
move()
timer_step = window.setTimeout(step, 3000)
}
step()
},
close() {
this.isShow = false
}
}
});
</script>
</body>
</html>
四、名词说明
管子数量 》》》 颜色种类的数量，如29关是 7
最大步数 》》》 达到设置的值，往后的情况直接跳过，太大可能不是最优解，太小可能找不到解
最大结果数量 》》》 最优解的数量或最大步之内结果的数量，建议取 1
遍历开始数 》》》 第一次从哪根管子开始计算，合理利用此参数可大大缩短计算时间，如29关从0计算要三十多分钟，从1计算只要一分钟
从最少两步开始计算 》》》 允许的步数从2步开始一直算到最大步数，可直接找到最少步数值，但计算多，耗时长
从最大步数开始计算 》》》 直接允许最大步数的解法，计算量减少，但可能错过最优解
以上是 球球排序最优解 的全部内容， 来源链接： utcz.com/a/36756.html
