一个最佳路径的问题
发布于 3 年前 作者 fangker 3209 次浏览 来自 问答

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

15 回复

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

@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

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

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

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

@coordcn 谢谢你的帮助,现在不需要解决这个问题了,百度工程师估计都是靠大量数据模板做成的,麻烦你敲了那么多代码浪费了那么多时间。辛苦了。

@fangker

没事,我以后碰到类似问题也能用的,不过只适合小规模问题求解,大规模靠穷举计算量是瓶颈。

function gencombine(n, m) 可以用来生成任何n取m的组合,是通用的,等下我单独开一贴和大家交流下,看看有没有更好的接法。

可以讲下具体是解决什么问题的么?我估计这类问题都是什么面试搞的,一般做最短距离都应该有起点和终点的,这个却没有。

@coordcn 这是我在模拟一个城市内拼车的订单生成

@coordcn 方便留下个q么大神

@fangker

不是大神,我不太用q,我经常来这里的。

拼车感觉比这个问题要复杂得多,可能是NP完全问题,解这种问题用穷举就无解了,可以用近似解法求近似最优解,还可以借鉴游戏寻路,把主路径先规划好,分支朝主路径靠,这样计算量就少了很多。拼车也不能用欧氏距离来比较,必须要有道路信息的。

@coordcn 好的呢,有些问题要请教,信息又比较敏感,拼车这种东西,生成订单有必要使用内存数据库么?

@fangker

这个东西我不懂的,看看网上有没有其他人的方案,建议先求得近似最优解,然后逐步优化。

主要还是计算量和最优解之间的平衡,能放内存中当然是最好的,查找迅速嘛。

回到顶部