通过 Kotlin 中整个点的最短路径

Question

我是 kotlin 的初学者，我正在用 kotlin 开发算法。我的目标是找到通过所有点的最短路径。目前我的算法试图找到从一个点到另一个点的最短距离，但我无法改进它。注意：MapDataPoint 是一个带有坐标（纬度和经度）的对象，以及一个由 string

表示的状态

 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)

}

this是图形表示，可以看出不是最短路径

Answer 1

您的问题是 traveling salesman problem 的变体。你只是不想return到起点终点。

我必须告诉你，没有已知的 'fast' 算法可以最佳地解决这个问题。但是很多方法找到好的解决方案还是挺快的。

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

通过 Kotlin 中整个点的最短路径

the shortest path through the entire point in Kotlin

sorting

algorithm

path

kotlin