C# 求多点间距离和最短？（是距离和最短不是最短距离）

码拜

8年 ago

1：假设XY坐标系中有5个点ABCDE，位置随机，起点与终点也随机但相同，如假设A是起点，终点也是A，相似A-B B-C C-D D-E E-A 等  ；
2：分别获取每条线段的距离，然后相加，使之得到的最终距离最短；
3：给出这五个点的排列顺序？           谢谢。
备注：是求各段距离和的最小值，不是最短距离  !

解决方案

5个点可以用穷举。
假如是一般性解答，请搜索“旅行售货员问题”。

利用穷举法把全部排列顺序列举出来，在比较距离总和

private List<List<Point>> ABCDE(Point pp, params Point[] ps)
{
    if (ps.Length != 4)
        throw new ArgumentOutOfRangeException();
    var s = ps.ToList();
    List<List<Point>> result = new List<List<Point>>();
    foreach (var p0 in s)
    {
        var s1 = s.Where(p => p != p0);
        foreach (var p1 in s1)
        {
            var s2 = s1.Where(p => p != p1);
            foreach (var p2 in s2)
            {
                var s3 = s2.Where(p => p != p2);
                foreach (var p3 in s3)
                {
                    var s4 = s3.Where(p => p != p3);
                    result.Add(new List<Point> { pp, p0, p1, p2, p3, pp });
                }
            }                    
        }
    }
    return result;
}

调用

Point p1 = new Point();
Point p2 = new Point(0,1);
Point p3 = new Point(1,2);
Point p4 = new Point(2,1);
Point p5 = new Point(2,0);
var arr = ABCDE(p1, p2, p3, p4, p5);
List<Point> r = new List<Point>();
double length = double.MaxValue;
foreach (var item in arr)
{
    double tmp = 0;
    for (int i = 0; i < 5; i++)
    {
        tmp += Math.Sqrt(Math.Pow((item[i + 1].X - item[i].X), 2) + Math.Pow((item[i + 1].Y - item[i].Y), 2));
    }
    Console.Write(string.Join(" ", item.Select(p => p.ToString()))+"--");
    Console.WriteLine(tmp);
    if (length > tmp)
    {
        length = tmp;
        r = item;
    }
}
Console.WriteLine("距离总和最短方案：");
Console.Write(string.Join(" ", r.Select(p => p.ToString())) + "--");
Console.WriteLine(length);

结果

{X=0,Y=0} {X=0,Y=1} {X=1,Y=2} {X=2,Y=1} {X=2,Y=0} {X=0,Y=0}--6.82842712474619
{X=0,Y=0} {X=0,Y=1} {X=1,Y=2} {X=2,Y=0} {X=2,Y=1} {X=0,Y=0}--7.88634951737267
{X=0,Y=0} {X=0,Y=1} {X=2,Y=1} {X=1,Y=2} {X=2,Y=0} {X=0,Y=0}--8.65028153987289
{X=0,Y=0} {X=0,Y=1} {X=2,Y=1} {X=2,Y=0} {X=1,Y=2} {X=0,Y=0}--8.47213595499958
{X=0,Y=0} {X=0,Y=1} {X=2,Y=0} {X=1,Y=2} {X=2,Y=1} {X=0,Y=0}--9.12241749487247
{X=0,Y=0} {X=0,Y=1} {X=2,Y=0} {X=2,Y=1} {X=1,Y=2} {X=0,Y=0}--7.88634951737267
{X=0,Y=0} {X=1,Y=2} {X=0,Y=1} {X=2,Y=1} {X=2,Y=0} {X=0,Y=0}--8.65028153987289
{X=0,Y=0} {X=1,Y=2} {X=0,Y=1} {X=2,Y=0} {X=2,Y=1} {X=0,Y=0}--9.12241749487247
{X=0,Y=0} {X=1,Y=2} {X=2,Y=1} {X=0,Y=1} {X=2,Y=0} {X=0,Y=0}--9.88634951737268
{X=0,Y=0} {X=1,Y=2} {X=2,Y=1} {X=2,Y=0} {X=0,Y=1} {X=0,Y=0}--7.88634951737267
{X=0,Y=0} {X=1,Y=2} {X=2,Y=0} {X=0,Y=1} {X=2,Y=1} {X=0,Y=0}--10.9442719099992
{X=0,Y=0} {X=1,Y=2} {X=2,Y=0} {X=2,Y=1} {X=0,Y=1} {X=0,Y=0}--8.47213595499958
{X=0,Y=0} {X=2,Y=1} {X=0,Y=1} {X=1,Y=2} {X=2,Y=0} {X=0,Y=0}--9.88634951737268
{X=0,Y=0} {X=2,Y=1} {X=0,Y=1} {X=2,Y=0} {X=1,Y=2} {X=0,Y=0}--10.9442719099992
{X=0,Y=0} {X=2,Y=1} {X=1,Y=2} {X=0,Y=1} {X=2,Y=0} {X=0,Y=0}--9.30056307974577
{X=0,Y=0} {X=2,Y=1} {X=1,Y=2} {X=2,Y=0} {X=0,Y=1} {X=0,Y=0}--9.12241749487247
{X=0,Y=0} {X=2,Y=1} {X=2,Y=0} {X=0,Y=1} {X=1,Y=2} {X=0,Y=0}--9.12241749487247
{X=0,Y=0} {X=2,Y=1} {X=2,Y=0} {X=1,Y=2} {X=0,Y=1} {X=0,Y=0}--7.88634951737267
{X=0,Y=0} {X=2,Y=0} {X=0,Y=1} {X=1,Y=2} {X=2,Y=1} {X=0,Y=0}--9.30056307974577
{X=0,Y=0} {X=2,Y=0} {X=0,Y=1} {X=2,Y=1} {X=1,Y=2} {X=0,Y=0}--9.88634951737268
{X=0,Y=0} {X=2,Y=0} {X=1,Y=2} {X=0,Y=1} {X=2,Y=1} {X=0,Y=0}--9.88634951737268
{X=0,Y=0} {X=2,Y=0} {X=1,Y=2} {X=2,Y=1} {X=0,Y=1} {X=0,Y=0}--8.65028153987289
{X=0,Y=0} {X=2,Y=0} {X=2,Y=1} {X=0,Y=1} {X=1,Y=2} {X=0,Y=0}--8.65028153987289
{X=0,Y=0} {X=2,Y=0} {X=2,Y=1} {X=1,Y=2} {X=0,Y=1} {X=0,Y=0}--6.82842712474619
距离总和最短方案：
{X=0,Y=0} {X=0,Y=1} {X=1,Y=2} {X=2,Y=1} {X=2,Y=0} {X=0,Y=0}--6.82842712474619

这是个NP问题，所以精确解只能是枚举全部的线路求最小值，否则要考虑效率的话只能求出近似的解