我知道旅行推销员是众所周知的,但是我需要一些关于为什么我的优化算法返回意外结果的帮助。我通过随机选择城市来创建初始解决方案。我还用距离矩阵和初始解作为参数创建了一个带有构造函数的类。优化算法非常简单;它会交换两个城市,并检查路线距离是否有所改善,如果有所改善,则应更新最佳解决方案。进行6次迭代。问题是,即使不满足覆盖条件,最好的解决方案似乎也已被更新和覆盖。我将添加一张图像,显示测试运行的结果。
变量bestSolution
似乎已被覆盖,但bestDistance
没有被覆盖。我必须具有某种隧道愿景,因为即使代码非常简单,我也无法弄清楚这一点。有人可以为为什么bestSolution
被覆盖并返回意外结果而鸣叫吗?
下面的代码示例:
package RandomMethod
import GreedyHeuristic
import java.util.*
fun main(args: Array<String>) {
/*A B C*/
val distances = arrayOf(/*A*/ intArrayOf(0, 2, 7),
/*B*/ intArrayOf(2, 0, 9),
/*C*/ intArrayOf(7, 9, 0))
val initalSolution = findRandomRoute(distances)
println("Initial solution: $initalSolution")
println("Total distance: ${findTotalDistance(distances, initalSolution)}\n")
val optimizedSolution = GreedyHeuristic(distances, initalSolution).optimize()
println("\nOptimized solution with Greedy Heuristic: $optimizedSolution")
println("Total distance: ${findTotalDistance(distances, optimizedSolution)}")
}
fun areAllCitiesVisited(isCityVisited: Array<Boolean>): Boolean {
for (visited in isCityVisited) {
if (!visited) return false
}
return true
}
fun findTotalDistance(distances: Array<IntArray>, orderToBeVisited: MutableList<Int>): Int {
var totalDistance = 0
for (i in 0..orderToBeVisited.size - 2) {
val fromCityIndex = orderToBeVisited.get(i)
val toCityIndex = orderToBeVisited.get(i + 1)
totalDistance += distances[fromCityIndex].get(toCityIndex)
}
return totalDistance
}
fun findRandomRoute(distances: Array<IntArray>): MutableList<Int> {
val visitedCities: Array<Boolean> = Array(distances.size, {i -> false})
// Find starting city index. 0 = A, 1 = B, 2 = C .... N = X
var currentCity = Random().nextInt(distances.size)
val orderToBeVisited: MutableList<Int> = mutableListOf(currentCity)
visitedCities[currentCity] = true
while (!areAllCitiesVisited(visitedCities)) {
currentCity = Random().nextInt(distances.size)
if (!visitedCities[currentCity]) {
orderToBeVisited.add(currentCity)
visitedCities[currentCity] = true
}
}
return orderToBeVisited
}
和用于优化的类:
import java.util.*
class GreedyHeuristic(distances: Array<IntArray>, initialSoltion: MutableList<Int>) {
val mInitialSolution: MutableList<Int> = initialSoltion
val mDistances: Array<IntArray> = distances
fun optimize(): MutableList<Int> {
var bestSolution = mInitialSolution
var newSolution = mInitialSolution
var bestDistance = findTotalDistance(mDistances, bestSolution)
var i = 0
while (i <= 5) {
println("best distance at start of loop: $bestDistance")
var cityIndex1 = Integer.MAX_VALUE
var cityIndex2 = Integer.MAX_VALUE
while (cityIndex1 == cityIndex2) {
cityIndex1 = Random().nextInt(mInitialSolution.size)
cityIndex2 = Random().nextInt(mInitialSolution.size)
}
val temp = newSolution.get(cityIndex1)
newSolution.set(cityIndex1, newSolution.get(cityIndex2))
newSolution.set(cityIndex2, temp)
val newDistance: Int = findTotalDistance(mDistances, newSolution)
println("new distance: $newDistance\n")
if (newDistance < bestDistance) {
println("New values gived to solution and distance")
bestSolution = newSolution
bestDistance = newDistance
}
i++
}
println("The distance of the best solution ${findTotalDistance(mDistances, bestSolution)}")
return bestSolution
}
fun findTotalDistance(distances: Array<IntArray>, orderToBeVisited: MutableList<Int>): Int {
var totalDistance = 0
for (i in 0..orderToBeVisited.size - 2) {
val fromCityIndex = orderToBeVisited.get(i)
val toCityIndex = orderToBeVisited.get(i + 1)
totalDistance += distances[fromCityIndex].get(toCityIndex)
}
return totalDistance
}
}
最佳答案
除非您特别要求,否则Kotlin(通常是JVM语言)不会复制值。这意味着,当您执行此操作时:
var bestSolution = mInitialSolution
var newSolution = mInitialSolution
您不是将
bestSolution
和newSolution
设置为分开mInitialSolution
的副本,而是使它们指向相同的MutableList
,因此使一个变量变异另一个变量。这就是说:您的问题不是bestSolution
被覆盖,而是您每次修改newSolution
时都无意中对其进行了修改。然后,您无需重复创建新列表就可以将
newSolution
重复用于while
循环的每个迭代。这导致我们两件事:newSolution
仍然是bestSolution
的别名,所以修改前者也会修改后者。 bestSolution = newSolution
不执行任何操作。 如评论中所述,最简单的方法是策略性地使用
.toMutableList()
,这将强制复制列表。您可以通过在顶部进行以下更改来实现此目的:var bestSolution = mInitialSolution.toMutableList()
var newSolution = mInitialSolution.toMutableList()
然后在循环中:
bestSolution = newSolution.toMutableList()
顺便说一句:通常,您应该返回并接受
List
而不是MutableList
,除非您特别希望它成为要就地进行更改的函数的约定的一部分。在这种特殊情况下,它可能迫使您要么做一些棘手的事情(例如,不安全地将mInitialSolution
投射到MutableList
,这会在您的脑海中发出各种各样的警钟声),或者复制该列表(这会使您向往正确的答案)关于kotlin - 具有随机初始解的旅行商,优化算法返回意外结果,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52356630/