一个最佳路径的问题
发布于 1 天前 作者 fangker 276 次浏览 来自 问答

区域内有很多不规则的点,要求4个点为一组组成一个路线后删除,路线利用最佳。QQ图片20160405194631.png PS:地图内任意一点为起点。问了好多人…

8 回复

路线利用最佳 是什么意思?四个点的连接路线最短?

@leapon 类似于迪杰斯特拉那样的单源路径最短,可是我又只需要4个点

任意选择一点为起点,然后计算距离最近的一点,依次循环下去?

@enmoon 那样可能最后剩下了城东一个城西一个,城北一个,城南一个

换一个思路,求一条线连接所有的点最短,然后四个一组打开就可以了.

最小生成树,然后全部一起删除可好

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]]);
}

@fangker

没明白你的意思,我感觉可能就是随便取四个点,找到最短路径的那个组合。

如果是这个意思,在数据量不大的前提下,可以把所有组合都遍历出来,然后比欧氏距离。

搞了两个小时,卡在排列组合上了。。。最后用栈解决了,感觉比较乱,不是很满意,也不知道对错。

回到顶部