Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * User: Martin
- * Date: 06.06.2014
- * Time: 14:59
- */
- case class Edge(from: Int, to: Int, weight: Double) extends Ordered[Edge] {
- override def compare(that: Edge): Int = weight.compareTo(that.weight)
- def reverse = Edge(to = from, from = to, weight = weight)
- }
- class NNHeuristic(val allLocations: List[Location], val constraints: List[PrecedenceConstraint]) {
- def makeCompleteGraph(ls: List[Location]) = {
- for (x <- ls; y <- ls; if x.getCityId != y.getCityId) yield Edge(x.getCityId, y.getCityId, x.distanceTo(y))
- }
- def findFailingConstraints(tour: Seq[Location]): Seq[PrecedenceConstraint] = {
- for {pc <- this.constraints
- first = pc.getFirst
- second = pc.getSecond
- i = tour.indexWhere(_.getCityId == first)
- j = tour.indexWhere(_.getCityId == second)
- if i != -1 && j != -1 && i >= j} yield new PrecedenceConstraint(first, second)
- }
- def nearestNeighborTour(tour: Vector[Location], edgesNotTaken: Set[Edge], relevantLocations: Map[Int, Location]): Vector[Location] = {
- if (tour.containsSlice(relevantLocations.values.toSeq)) {
- tour
- }
- else {
- val lastId = tour.head.getCityId
- val nextEdgeCandidates = edgesNotTaken.filter(edge => edge.from == lastId)
- val nextEdge = nextEdgeCandidates.filter(edge => relevantLocations.keySet.contains(edge.to)).toSeq.sorted.head
- val nextNode = relevantLocations(nextEdge.to)
- val newTour = tour :+ nextNode
- val failingConstraints = findFailingConstraints(newTour)
- if (failingConstraints.size == 0) {
- nearestNeighborTour(newTour, edgesNotTaken - nextEdge, relevantLocations - nextNode.getCityId)
- }
- else {
- val pc = failingConstraints.head
- val firstIndex = newTour.indexWhere(_.getCityId == pc.getFirst)
- val secondIndex = newTour.indexWhere(_.getCityId == pc.getSecond)
- val tourSwapped = newTour.updated(firstIndex, allLocations(pc.getSecond)).updated(secondIndex, allLocations(pc.getFirst))
- nearestNeighborTour(tourSwapped, edgesNotTaken - nextEdge, relevantLocations - nextNode.getCityId)
- }
- }
- }
- }
- object Main {
- def calcObjectiveValue(solution: Seq[Location]): Double = {
- var sumDistance: Double = 0
- var last: Location = null
- import scala.collection.JavaConversions._
- for (c <- solution) {
- if (last != null && c != null) {
- sumDistance += last.distanceTo(c)
- }
- last = c
- }
- if (last != null && (solution.get(0) ne last)) {
- sumDistance += last.distanceTo(solution.get(0))
- }
- sumDistance
- }
- def main(args: Array[String]) {
- val tspInstance = new TspLibReader("C:\\Users\\Martin\\Desktop\\asd2\\public_instances\\0001").readInstance()
- import scala.collection.JavaConverters._
- val nodeMap = tspInstance.getAllLocations.asScala.map {
- case (a, b) => (a.intValue(), b)
- }.toMap
- val start = System.nanoTime
- val nodes = tspInstance.getAllLocations.asScala.values.toList
- val constraints = tspInstance.getConstraints.asScala.toList
- val nn = new NNHeuristic(nodes, constraints)
- val tour = nn.nearestNeighborTour(Vector(nodeMap(2)), nn.makeCompleteGraph(nodes).toSet, nodeMap - 2)
- val end = System.nanoTime
- println(tour.map(_.getCityId))
- println(calcObjectiveValue(tour))
- println("t = " + (end - start) / 1e6 + " ms")
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement