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