2 opt算法运行结果不一致且无路径优化效果的问题排查求助

存在的核心问题 #

• 基准距离未更新：主逻辑中currentDistanceEfficiency始终为初始输入的路径距离，找到更优路径后没有更新为最新的更小距离，导致后续优化判断条件几乎无法触发
• 外层循环逻辑错误：外层迭代循环末尾直接强制将hasImproved设为false，即使本轮找到更优路径，也不会开启下一轮迭代，仅能完成单次遍历优化
• 最优值赋值逻辑倒置：找到更优的newDistance后，将bestDistanceAvailable赋值为旧的currentDistanceEfficiency而非新的更优距离，数值更新完全错误

修正后的代码 #

2-opt主逻辑修正版 #

var newDistance = CLLocationDistance()
var newRoute = Array<Int>()
var routeHolder = Array<Array<Int>>()
var distanceHolder = Array<CLLocationDistance>()
var preExistingRoute = routeToProcess
var currentBestDistance = currentDistanceEfficiency // 重命名避免歧义
var hasImproved: Bool

repeat {
    hasImproved = false // 每次迭代前先标记为无优化
    for i in 1..<preExistingRoute.count - 1 {
        for k in (i + 1)..<preExistingRoute.count {
            newRoute = twoOptSwapActions(routeToAlter: preExistingRoute, iIndex: i, kIndex: k)
            let distanceElements = twoOptDistanceCalculation(listOfIndices: newRoute)
            newDistance = calculateTotalDistance(distanceToCalculate: distanceElements)

            if newDistance < currentBestDistance {
                preExistingRoute = newRoute
                currentBestDistance = newDistance // 更新基准距离为最新最优值
                routeHolder.append(newRoute)
                distanceHolder.append(newDistance)
                hasImproved = true // 标记本轮有优化，开启下一轮迭代
            }
        }
    }
} while hasImproved // 只要本轮有优化就继续迭代

return (routeHolder, distanceHolder)

2-opt交换逻辑（原有逻辑可正常使用，无错误） #

var firstHalf = Array<Int>()
var secondHalf = Array<Int>()
var completedCorrection = Array<Int>()

firstHalf = Array(routeToAlter[0...(iIndex - 1)])
completedCorrection.append(contentsOf: firstHalf)
secondHalf = Array(routeToAlter[(iIndex)...kIndex])
completedCorrection.append(contentsOf: secondHalf.reversed())
if kIndex != routeToAlter.count - 1 {
    completedCorrection.append(contentsOf: routeToAlter[kIndex + 1 ... routeToAlter.count - 1])
}
return completedCorrection

额外优化建议 #

• 可先保存本轮遍历的全局最优解，双层循环全部跑完再更新当前路径，避免中途更新路径导致后续索引判断出错，进一步提升优化效率
• 针对长路径可加入提前终止逻辑，连续多轮优化幅度小于阈值时直接终止，减少不必要的计算

内容的提问来源于stack exchange，提问作者AR1412