Created
October 30, 2023 13:51
-
-
Save maksmakuta/c52425e01cbbb88133f665b2ab4f4186 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import kotlin.math.pow | |
| import kotlin.math.sqrt | |
| import kotlin.random.Random | |
| import kotlin.time.measureTime | |
| data class City( | |
| val name : String, | |
| val x : Double, | |
| val y : Double | |
| ){ | |
| fun dist(o : City) : Double{ | |
| val deltaX = x - o.x | |
| val deltaY = y - o.y | |
| return sqrt(deltaX.pow(2) + deltaY.pow(2)) | |
| } | |
| } | |
| fun dist(list: List<City>) : Double{ | |
| var dist = list.first().dist(list.last()) | |
| for(i in 1 ..< list.size){ | |
| dist += list[i].dist(list[i-1]) | |
| } | |
| return dist | |
| } | |
| fun fact(n: Int): Long { | |
| var result: Long = 1 | |
| for (i in 1..n) { | |
| result *= i | |
| } | |
| return result | |
| } | |
| fun backtracking(input : List<City>) : Pair<List<City>,Double>{ | |
| var curr = 0 | |
| val total = fact(input.size) | |
| var list = listOf<City>() | |
| var dist = Double.MAX_VALUE | |
| input.permutations { | |
| if(Random.nextInt(10) == 1){ | |
| print("$curr/$total\r") | |
| } | |
| val sdist = dist(it) | |
| if(dist > sdist){ | |
| dist = sdist | |
| list = it | |
| } | |
| curr++ | |
| } | |
| return Pair(list,dist) | |
| } | |
| fun <T> List<T>.permutations(task : (List<T>) -> Unit){ | |
| if (size <= 1) { | |
| task(this) | |
| return | |
| } | |
| val indices = IntArray(size) { it } | |
| task(this) | |
| while (true) { | |
| var i = size - 2 | |
| while (i >= 0 && indices[i] > indices[i + 1]) | |
| i-- | |
| if (i == -1) | |
| break | |
| var j = size - 1 | |
| while (indices[j] < indices[i]) | |
| j-- | |
| // Swap elements | |
| val temp = indices[i] | |
| indices[i] = indices[j] | |
| indices[j] = temp | |
| var left = i + 1 | |
| var right = size - 1 | |
| while (left < right) { | |
| val temp2 = indices[left] | |
| indices[left] = indices[right] | |
| indices[right] = temp2 | |
| left++ | |
| right-- | |
| } | |
| val permutation = indices.map { this[it] } | |
| task(permutation) | |
| } | |
| } | |
| fun main() { | |
| val cities = listOf( | |
| City("Kyiv",50.0,15.0), | |
| City("Lutsk",45.0,15.0), | |
| City("Lviv",45.0,99.0), | |
| City("Rivne",79.0,13.0), | |
| City("Ternopil",15.0,32.0), | |
| City("Zhutomur",33.0,17.0), | |
| //City("Cherkasy",22.0,89.0), | |
| //City("Donetsk",3.0,59.0), | |
| //City("Harkiv",44.0,0.0), | |
| //City("Odesa",1.0,90.0), | |
| //City("Chernihiv",65.0,100.0), | |
| //City("Sumy",3.0,7.0), | |
| ) | |
| val t = measureTime { | |
| val (path, dist) = backtracking(cities) | |
| println("Distance : $dist") | |
| println("Path : ${path.joinToString(" - ") { it.name }}") | |
| } | |
| println("Time : $t") | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment