Торговый продавец со случайным начальным решением, алгоритм оптимизации, возвращающий неожиданный результат

Question

Я знаю, что коммивояжёр хорошо известен, но мне нужна помощь в том, почему мой алгоритм оптимизации возвращает неожиданный результат.Я создал первоначальное решение, выбрав города в случайном порядке.Я также создал класс с конструктором с матрицей расстояний и начальным решением в качестве параметров.Алгоритм оптимизации очень прост;он меняет местами два города и проверяет, было ли увеличено расстояние маршрута, и если оно улучшилось, лучшее решение должно быть обновлено.Это продолжается в течение 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
    }

}

Answer 1

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, которое должно звучать в голове всякими предупреждающими звонками), или скопировать список (которыйподтолкнул вас к правильному ответу)