problema del vendedor ambulante, algoritmo 2-opt implementación C#

Question

¿Puede alguien darme una muestra del código del algoritmo 2-opt para el problema del vendedor ambulante? Por ahora estoy usando el vecino más cercano para encontrar el camino, pero este método está lejos de ser perfecto, y después de algunas investigaciones encontré el algoritmo 2-opt que corregiría ese camino hasta el nivel aceptable. Encontré algunas aplicaciones de muestra pero sin código fuente.

Answer 1

Así que me aburrí y lo escribí. Es parece como funciona, pero no lo he probado muy a fondo. Asume la desigualdad del triángulo, existen todos los bordes, ese tipo de cosas. Funciona en gran medida como la respuesta que describí. Imprime cada iteración; el último es el 2-optimizado.

Estoy seguro de que se puede mejorar en un trillón de maneras.

using System; 
using System.Collections.Generic; 
using System.Linq; 


namespace TSP 
{ 
    internal static class Program 
    { 
     private static void Main(string[] args) 
     { 
      //create an initial tour out of nearest neighbors 
      var stops = Enumerable.Range(1, 10) 
            .Select(i => new Stop(new City(i))) 
            .NearestNeighbors() 
            .ToList(); 

      //create next pointers between them 
      stops.Connect(true); 

      //wrap in a tour object 
      Tour startingTour = new Tour(stops); 

      //the actual algorithm 
      while (true) 
      { 
       Console.WriteLine(startingTour); 
       var newTour = startingTour.GenerateMutations() 
              .MinBy(tour => tour.Cost()); 
       if (newTour.Cost() < startingTour.Cost()) startingTour = newTour; 
       else break; 
      } 

      Console.ReadLine(); 
     } 


     private class City 
     { 
      private static Random rand = new Random(); 


      public City(int cityName) 
      { 
       X = rand.NextDouble() * 100; 
       Y = rand.NextDouble() * 100; 
       CityName = cityName; 
      } 


      public double X { get; private set; } 

      public double Y { get; private set; } 

      public int CityName { get; private set; } 
     } 


     private class Stop 
     { 
      public Stop(City city) 
      { 
       City = city; 
      } 


      public Stop Next { get; set; } 

      public City City { get; set; } 


      public Stop Clone() 
      { 
       return new Stop(City); 
      } 


      public static double Distance(Stop first, Stop other) 
      { 
       return Math.Sqrt(
        Math.Pow(first.City.X - other.City.X, 2) + 
        Math.Pow(first.City.Y - other.City.Y, 2)); 
      } 


      //list of nodes, including this one, that we can get to 
      public IEnumerable<Stop> CanGetTo() 
      { 
       var current = this; 
       while (true) 
       { 
        yield return current; 
        current = current.Next; 
        if (current == this) break; 
       } 
      } 


      public override bool Equals(object obj) 
      { 
       return City == ((Stop)obj).City; 
      } 


      public override int GetHashCode() 
      { 
       return City.GetHashCode(); 
      } 


      public override string ToString() 
      { 
       return City.CityName.ToString(); 
      } 
     } 


     private class Tour 
     { 
      public Tour(IEnumerable<Stop> stops) 
      { 
       Anchor = stops.First(); 
      } 


      //the set of tours we can make with 2-opt out of this one 
      public IEnumerable<Tour> GenerateMutations() 
      { 
       for (Stop stop = Anchor; stop.Next != Anchor; stop = stop.Next) 
       { 
        //skip the next one, since you can't swap with that 
        Stop current = stop.Next.Next; 
        while (current != Anchor) 
        { 
         yield return CloneWithSwap(stop.City, current.City); 
         current = current.Next; 
        } 
       } 
      } 


      public Stop Anchor { get; set; } 


      public Tour CloneWithSwap(City firstCity, City secondCity) 
      { 
       Stop firstFrom = null, secondFrom = null; 
       var stops = UnconnectedClones(); 
       stops.Connect(true); 

       foreach (Stop stop in stops) 
       { 
        if (stop.City == firstCity) firstFrom = stop; 

        if (stop.City == secondCity) secondFrom = stop; 
       } 

       //the swap part 
       var firstTo = firstFrom.Next; 
       var secondTo = secondFrom.Next; 

       //reverse all of the links between the swaps 
       firstTo.CanGetTo() 
         .TakeWhile(stop => stop != secondTo) 
         .Reverse() 
         .Connect(false); 

       firstTo.Next = secondTo; 
       firstFrom.Next = secondFrom; 

       var tour = new Tour(stops); 
       return tour; 
      } 


      public IList<Stop> UnconnectedClones() 
      { 
       return Cycle().Select(stop => stop.Clone()).ToList(); 
      } 


      public double Cost() 
      { 
       return Cycle().Aggregate(
        0.0, 
        (sum, stop) => 
        sum + Stop.Distance(stop, stop.Next)); 
      } 


      private IEnumerable<Stop> Cycle() 
      { 
       return Anchor.CanGetTo(); 
      } 


      public override string ToString() 
      { 
       string path = String.Join(
        "->", 
        Cycle().Select(stop => stop.ToString()).ToArray()); 
       return String.Format("Cost: {0}, Path:{1}", Cost(), path); 
      } 

     } 


     //take an ordered list of nodes and set their next properties 
     private static void Connect(this IEnumerable<Stop> stops, bool loop) 
     { 
      Stop prev = null, first = null; 
      foreach (var stop in stops) 
      { 
       if (first == null) first = stop; 
       if (prev != null) prev.Next = stop; 
       prev = stop; 
      } 

      if (loop) 
      { 
       prev.Next = first; 
      } 
     } 


     //T with the smallest func(T) 
     private static T MinBy<T, TComparable>(
      this IEnumerable<T> xs, 
      Func<T, TComparable> func) 
      where TComparable : IComparable<TComparable> 
     { 
      return xs.DefaultIfEmpty().Aggregate(
       (maxSoFar, elem) => 
       func(elem).CompareTo(func(maxSoFar)) > 0 ? maxSoFar : elem); 
     } 


     //return an ordered nearest neighbor set 
     private static IEnumerable<Stop> NearestNeighbors(this IEnumerable<Stop> stops) 
     { 
      var stopsLeft = stops.ToList(); 
      for (var stop = stopsLeft.First(); 
       stop != null; 
       stop = stopsLeft.MinBy(s => Stop.Distance(stop, s))) 
      { 
       stopsLeft.Remove(stop); 
       yield return stop; 
      } 
     } 
    } 
} 

Answer 2

Bueno, su solución para TSP siempre estará lejos de ser perfecta. Sin código, pero he aquí cómo hacer para 2-Opt. No es tan malo:

1. Necesita una clase llamada Stop que tenga una propiedad Next, Prev y City, y probablemente una propiedad Stops que solo devuelva la matriz que contiene Next y Prev.
2. Cuando los vincules, lo llamaremos Tour. Tour tiene una propiedad Stop (cualquiera de las paradas lo hará), y una propiedad AllStops, cuyo comprador solo camina por las paradas y las devuelve
3. Necesita un método que realice un recorrido y le devuelva el costo. Vamos a llamar a eso Tour.Cost().
4. Necesita Tour.Clone(), que simplemente recorre las paradas y las clona individualmente
5. Necesita un método que genere el conjunto de recorridos con dos bordes conmutados. Llame a este Tour.PossibleMutations()
6. de inicio con su solución NN
7. PossibleMutations de llamada() sobre ella
8. Costo de llamada() en todos ellos y tomar el uno con el resultado más bajo
9. Repita hasta que el costo no baja

Answer 3

Si el problema es la distancia euclidiana y desea que el coste de la solución producida por el algoritmo está dentro de 3/2 de la óptima, entonces quieren que el algoritmo de christofides. ACO y GA no tienen un costo garantizado.