我知道旅行推销员是众所周知的,但我需要一些帮助来解释为什么我的优化算法会返回意外的结果。我通过随机顺序选择城市来创建初始解决方案。我还创建了一个带有构造函数的类,其中包含距离矩阵和初始解决方案作为参数。优化算法非常简单;它交换两个城市并检查路线距离是否有所改善,如果改进了,则应更新最佳解决方案。这持续了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
,这应该会发出你头上的各种警告铃声),或者复制清单(这会让你朝着正确的答案)