走一堆二维平面的点,如何实现最小路径?
public static List<int> nextpoint(List currentlist, int currentpoint)//当前list,当前点
{
double distence;
double minidistence;
for (int i = 0; i < currentlist.Count; i++)//去掉第一个点的新list
{
distence = Math.Pow((currentlist[i].Track.Start_X - currentlist[currentpoint].Track.Start_X), 2.0) + Math.Pow((currentlist[i].Track.Start_Y - currentlist[currentpoint].Track.Start_Y), 2.0);
Distencelist.Add(distence);
}
minidistence = Distencelist.Min();//获取list中的最小值
List<int> minilist = new List<int>();
int minIndex = Distencelist.IndexOf(minidistence);//获取最小值的索引集合
for (int i = minIndex - 1; i < Distencelist.Count; i++)
{
if (Distencelist[i] == minIndex)
{
minilist.Add(i);
}
}
List<int> index = new List<int>();
for (int i = 0; i < minilist.Count; i++)
{
index.Add(currentlist[minilist[i]].originalIndex);
}
return index;//原始list的顺序
}
1、先定一个起始点A;
2、计算出起始点A与其他点的距离,比较出距离最短的那个点B;
3、再用点B与其他点(除点A)比较找出距离最短的点C;但是如果存在D,F点BF,BD距离和BC距离一样如何确定下一个点?
4、循环操作直到最后一个点,无需比较,直接找到还没有排序的点,追加在最后即可。
5、然后将所有点循环定为起始点,将每一种点排序组合都加到数组A中,并将这种排序组合所有点连线计算出长度加到数组B中;
6、找出数组B中值最小的下标,到数组A中找对应的点排列组合,这个排序结果就是最短路线点的排序。
这种必然要递归
否则回溯会非常麻烦
尤其有环路的时候容易造成死循环
算法本身有很多,基本归类在“图论”里,大体上上一般常见的狄克斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法
你可以自己选择
ps:实践上我们现在很多情况已不需要自己写了,如果条件允许我们很多情况是直接上图数据库,比如neo4j。毕竟我们都归类到图了,那不用图查询工具反而用关系数据库弄不划算啊