旅行商问题，2-opt算法c＃实现

有人可以给我一个2-opt算法的代码样本，用于旅行商问题。 现在我使用最近邻居找到路径，但这种方法远非完美，经过一些研究后我发现2-opt算法可以将该路径纠正到可接受的水平。 我发现了一些示例应用程序，但没有源代码。

Answer 1

所以我感到无聊并写下来。 它看起来很有效，但我还没有彻底测试过。 它假设三角不等式，所有边都存在，那种东西。 它的工作方式很像我概述的答案。 它打印每次迭代; 最后一个是2优化的。

我相信它可以通过无数种方式得到改善。

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 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 stops) { Anchor = stops.First(); } //the set of tours we can make with 2-opt out of this one public IEnumerable 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 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 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 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( this IEnumerable xs, Func func) where TComparable : IComparable { return xs.DefaultIfEmpty().Aggregate( (maxSoFar, elem) => func(elem).CompareTo(func(maxSoFar)) > 0 ? maxSoFar : elem); } //return an ordered nearest neighbor set private static IEnumerable NearestNeighbors(this IEnumerable 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

那么，你对TSP的解决方案总是远非完美。 没有代码，但这里是如何进行2-Opt。 这不是太糟糕：

1. 你需要一个名为Stop的类，它有一个Next，Prev和City属性，可能还有一个Stops属性，只返回包含Next和Prev的数组。
2. 当你把它们连接在一起时，我们称之为巡回赛。 Tour有一个Stop属性（任何一个站点都可以）和一个AllStops属性，其getter只是走了一段路并返回它们
3. 您需要一种方法来进行巡视并返回其成本。 我们称之为Tour.Cost（）。
4. 你需要Tour.Clone（），它只是走了一段路并单独克隆它们
5. 您需要一种方法来生成具有两个边切换的游览集。 调用此Tour.PossibleMutations（）
6. 从您的NN解决方案开始
7. 在它上面调用PossibleMutations（）
8. 在所有这些上调用Cost（）并获取结果最低的那个
9. 重复，直到成本没有下降

Answer 3

如果问题是欧几里德距离，并且您希望算法产生的解决方案的成本在最佳值的3/2之内，那么您需要Christofides算法。 ACO和GA没有保证的费用。