一个最佳路径的问题
区域内有很多不规则的点，要求4个点为一组组成一个路线后删除，路线利用最佳。
PS：地图内任意一点为起点。问了好多人…
15 回复
function gendata(n, x, y) {
var data = [];
for (var i = 0; i < n; i++) {
data.push({
x: Math.ceil(Math.random() * x),
y: Math.ceil(Math.random() * y)
});
}
return data;
}
function gencombine(n, m) {
var combine = [];
if (m > n) return combine;
var stack = [];
var first = []
for (var i = 0; i < m; i++) {
stack[i] = i;
first[i] = i;
}
combine.push(first);
var last = [];
var end = n - m;
for (var i = 0; i < m; i++) {
last[i] = end + i;
}
var pos = m - 1;
var lastm = m - 1;
var temp;
while (true) {
if (stack[pos] < last[pos]) {
stack[pos]++;
temp = stack[pos];
pos++;
if (pos <= lastm) {
stack[pos] = temp;
}
} else {
pos--;
if (pos < 0) break;
}
if (pos > lastm) {
var tmp = [];
for (var i = 0; i < m; i++) {
tmp[i] = stack[i];
}
combine.push(tmp);
pos = lastm;
}
}
return combine;
}
var num = 20;
var X = 50;
var Y = 50;
var data = gendata(num, X, Y);
var combine = gencombine(num, 4);
function caldist(c) {
var temp = [];
for (var i = 0; i < c.length; i++) {
temp[i] = data[c[i]];
}
temp.sort(function(a, b){
if (a.x > b.x) {
return 1;
} else if (a.x == b.x) {
if (a.y > b.y) {
return 1;
} else {
return -1;
}
} else {
return -1;
}
});
var val = 0;
var first = temp[0];
for (var m = 1; m < temp.length; m++) {
var next = temp[m];
var xx = next.x - first.x;
var yy = next.y - first.y;
val = xx * xx + yy * yy;
first = next;
}
return val;
}
var min_value = caldist(combine[0]);
var min_index = 0;
for (var i = 1; i < combine.length; i++) {
var val = caldist(combine[i]);
if (val < min_value) {
min_value = val;
min_index = i;
}
}
console.log(min_value);
console.log(min_index);
console.log(combine[min_index]);
var c = combine[min_index];
for (var i = 0; i < c.length; i++) {
console.log(data[c[i]]);
}
没明白你的意思，我感觉可能就是随便取四个点，找到最短路径的那个组合。
如果是这个意思，在数据量不大的前提下，可以把所有组合都遍历出来，然后比欧氏距离。
搞了两个小时，卡在排列组合上了。。。最后用栈解决了，感觉比较乱，不是很满意，也不知道对错。
没事，我以后碰到类似问题也能用的，不过只适合小规模问题求解，大规模靠穷举计算量是瓶颈。
function gencombine(n, m) 可以用来生成任何n取m的组合，是通用的，等下我单独开一贴和大家交流下，看看有没有更好的接法。
可以讲下具体是解决什么问题的么？我估计这类问题都是什么面试搞的，一般做最短距离都应该有起点和终点的，这个却没有。
不是大神，我不太用q，我经常来这里的。
拼车感觉比这个问题要复杂得多，可能是NP完全问题，解这种问题用穷举就无解了，可以用近似解法求近似最优解，还可以借鉴游戏寻路，把主路径先规划好，分支朝主路径靠，这样计算量就少了很多。拼车也不能用欧氏距离来比较，必须要有道路信息的。
