我知道旅行推销员是众所周知的,但我需要一些帮助来了解为什么我的优化算法会返回意外结果。我通过随机选择城市创建了一个初始解决方案。我还创建了一个带有构造函数的类,该构造函数以距离矩阵和初始解作为参数。优化算法非常简单;它交换两个城市并检查路线距离是否已改善,如果已改善,则应更新最佳解决方案。这持续了 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
除非您特别希望它成为您的功能契约(Contract)的一部分,否则您将就地改变事物。在这种特殊情况下,它会迫使你要么做一些讨厌的事情(比如不安全的类型转换 mInitialSolution
到 MutableList
,这应该在你的脑海中敲响各种警钟),或者复制列表(这会'已将您推向正确的答案)
关于kotlin - 具有随机初始解的旅行推销员,优化算法返回意外结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52356630/