最短路径算法:接送乘客到目的地
这是一个典型的旅行商问题(Traveling Salesman Problem,TSP)。
以下是一种简单的贪心算法:
-
计算出六个点之间的距离(A到A'的距离,A到B'的距离等等)。
-
选择一个起点(比如A),然后选择离它最近的点(假设是B),把它标记为已经访问过的点。
-
然后再选择离B最近的点(假设是C),把它标记为已经访问过的点。
-
重复这个过程直到所有的点都被访问过为止。
-
最后回到起点。
这个算法的时间复杂度是O(n^2),其中n是点的个数。虽然它不一定能找到最优解,但是通常情况下它能得到一个不错的近似解。
原文地址: https://www.cveoy.top/t/topic/oW13 著作权归作者所有。请勿转载和采集!