problema commesso viaggiatore, algoritmo 2-opt C# implementazione

Question

Qualcuno può darmi un esempio di codice dell'algoritmo 2-opt per il problema del commesso viaggiatore. Per ora im utilizzando il vicino più vicino per trovare il percorso, ma questo metodo è tutt'altro che perfetto, e dopo alcune ricerche ho trovato algoritmo 2-opt che avrebbe corretto quel percorso al livello accettabile. Ho trovato alcune app di esempio ma senza codice sorgente.

Answer 1

Quindi mi sono annoiato e l'ho scritto. È sembra come funziona, ma non l'ho provato molto accuratamente. Assume la disuguaglianza triangolare, tutti i bordi esistono, quel genere di cose. Funziona in gran parte come la risposta che ho delineato. Stampa ogni iterazione; l'ultimo è il 2 ottimizzato.

Sono sicuro che può essere migliorato in diversi modi.

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

Bene, la soluzione per TSP sarà sempre lungi dall'essere perfetta. Nessun codice, ma ecco come andare su 2-Opt. Non è male:

1. È necessaria una classe denominata Arresta che ha una proprietà Avanti, Indietro e Città e probabilmente una proprietà Interrompi che restituisce solo l'array contenente Avanti e Indietro.
2. Quando li colleghi insieme, chiameremo un tour. Il tour ha una proprietà Stop (qualsiasi fermata lo farà), e una proprietà AllStops, il cui getter semplicemente cammina e li restituisce
3. Hai bisogno di un metodo che faccia un giro e ritorni il suo costo. Chiamiamo quel Tour.Cost().
4. È necessario Tour.Clone(), che esegue solo le fermate e le clona singolarmente.
5. È necessario un metodo che generi l'insieme di tour con due fronti commutati. Chiamare questo Tour.PossibleMutations()
6. Inizia con la soluzione NN
7. PossibleMutations call() su di esso
8. Costo chiamate() su ognuna di esse e prendere quella con il risultato più basso
9. Ripetere fino a quando il costo non va giù

Answer 3

Se il problema è la distanza euclidea e si desidera che il costo della soluzione prodotta dai algoritmo è nel 3/2 della ottimali poi si desidera l'algoritmo Christofides. ACO e GA non hanno un costo garantito.