旅行推销员问题，2-opt算法C#实现

Question

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

- TAB

---

TSP问题有一个3/2 OPT的解决方案，因此如果你关注性能，那么这将是更好的选择（我没有代码，但可以告诉你算法，或者你可以在Vijay Vazirani的第二章中阅读它）。 - Aditya

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<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;
            }
        }
    }
}

- user24359

---

+1 鼓励你提供了一个几乎可行的实现。 - Mahesh Velaga

@Issac：不完全是这样。当你发布这个帖子时，我也正在实现2-opt算法。我使用“几乎”这个词是指这个解决方案对我的目的有多接近。对于造成的困惑，我表示抱歉。 - Mahesh Velaga

有用的代码 - 感谢，但警告：在单城市和双城市情况下，.GenerateMutations() 失败（返回 null）。 - ChrisJJ

Answer 2

你对TSP的解决方案永远不可能是完美的。这里没有代码，但是下面是如何进行2-Opt的步骤，它并不太难：

1. 你需要创建一个名为Stop的类，该类具有Next、Prev和City属性，还可能有Stops属性，只返回包含Next和Prev的数组。
2. 当你将它们连接在一起时，我们称之为Tour。Tour具有Stop属性(任何一个站点都可以)，以及AllStops属性，其getter只是遍历所有站点并返回它们。
3. 你需要一个方法，该方法接受一个Tour对象并返回其成本。让我们称之为Tour.Cost()。
4. 你需要Tour.Clone()方法，该方法只是遍历所有站点并逐个克隆它们。
5. 你需要一个生成两个边缘交换的Tour集合的方法。将其称为Tour.PossibleMutations()。
6. 从NN解决方案开始。
7. 对它调用PossibleMutations()。
8. 对所有结果调用Cost()并选择具有最低成本的结果。
9. 重复此过程，直到成本不再降低为止。

- user24359

---

如果你要暴力破解，为什么不找到最优解呢！ - Aryabhatta

@Moron - 我不确定最小生成树和2-opt之间的关系。你是说你使用MST前序遍历，然后应用2-opt，还是有其他更多的操作？ - user24359

我的错。我一直以为2-opt是指在最优解的两倍范围内，这种情况下MST是有效的。我已经删除了我的回答。 - Aryabhatta

哈哈，你把自己的名字从“白痴”改成了“阿耳雅巴塔”，看起来我只是个傻瓜。 - user24359

Answer 3

如果问题是欧几里得距离，而您希望算法产生的解决方案在最优解的3/2之内，则需要使用克里斯托菲德算法。ACO和GA没有保证的成本。

- Micromega