穿过Kotlin整个点的最短路径

Question

我是kotlin的初学者，我正在kotlin开发一个算法。我的目标是找到通过所有点的最短路径。目前，我的算法正试图找到从一点到另一点的最短距离，但我无法改进。注意：MapDataPoint是一个具有坐标(纬度和经度(的对象，状态由字符串表示

fun findClosestPoint(latLng: LatLng, points: List<MapDataPoint>): MapDataPoint {

var latestClosestPoint: MapDataPoint? = null
points.forEach { latestPoint->
if (latestPoint.status == "present") {
latestClosestPoint = latestPoint
points.forEach { point ->
if (point.status == "present") {
val differenceLatestLng: Double = kotlin.math.abs(latestClosestPoint!!.lng - latLng.longitude)
val differenceLatestLat: Double = kotlin.math.abs(latestClosestPoint!!.lat - latLng.latitude)
val differenceActuelLng: Double = kotlin.math.abs(point.lng - latLng.longitude)
val differenceActuelLat: Double = kotlin.math.abs(point.lat - latLng.latitude)
if (differenceActuelLat < differenceLatestLat && differenceActuelLng < differenceLatestLng) {
latestClosestPoint = point
}
}
}
return latestClosestPoint!!
}
}
return latestClosestPoint!!
}

fun displayEpurationPath(mapDatapoint: List<MapDataPoint>) {

val locationComponent = mapboxMap?.locationComponent?.lastKnownLocation
val latLng = LatLng(locationComponent!!.latitude, locationComponent.longitude)
var newCoordinate: LatLng? = null
val points: MutableList<MapDataPoint> = mapDatapoint.toMutableList()
var sortedList: MutableList<MapDataPoint> = mutableListOf()
val list: MutableList<MapDataPoint> = emptyList<MapDataPoint>().toMutableList()

while (points.isNotEmpty() && !manageStatusListPoint(points)) {
val point: MapDataPoint = if (newCoordinate == null) {
findClosestPoint(latLng, points)
} else {
findClosestPoint(newCoordinate, points)
}
newCoordinate = LatLng(point.lat, point.lng)
sortedList.add(point)
points.remove(point)
}

这是图形表示，我们可以看出它不是最短路径

Answer 1

您的问题是旅行推销员问题的变体。你只是不想在最后回到起点。

我必须告诉你，目前还没有"快速"算法可以最优地解决这个问题。但是很多方法很快就能找到好的解决方案。

寻找解决方案的常见方法是回溯、遗传算法。。。