C# 求多点间距离和最短?(是距离和最短不是最短距离)

.Net技术 码拜 9年前 (2016-06-05) 2173次浏览
1:假设XY坐标系中有5个点ABCDE,位置随机,起点与终点也随机但相同,如假设A是起点,终点也是A,相似A-B B-C C-D D-E E-A 等  ;
2:分别获取每条线段的距离,然后相加,使之得到的最终距离最短;
3:给出这五个点的排列顺序?           谢谢。
备注:是求各段距离和的最小值,不是最短距离  !
解决方案

10

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

30

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

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

10

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

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明C# 求多点间距离和最短?(是距离和最短不是最短距离)
喜欢 (0)
[1034331897@qq.com]
分享 (0)