Может ли кто-нибудь дать мне образец кода алгоритма 2-opt для задачи коммивояжера. На данный момент я использую ближайшего соседа, чтобы найти путь, но этот метод далек от совершенства, и после некоторых исследований я нашел алгоритм с двумя вариантами, который исправил бы этот путь до приемлемого уровня. Я нашел несколько примеров приложений, но без исходного кода.
задача коммивояжера, 2-опционный алгоритм реализация c #
comment
Существует решение 3/2 OPT для TSP, поэтому, если вы смотрите на производительность, это будет лучше (нет, у меня нет кода, но я могу сказать алгоритм, или вы можете прочитать его в главе 2 vijay vazirani)
- person Aditya   schedule 21.05.2013
Ответы (3)
Мне стало скучно и я написал это. Он выглядит так, как будто работает, но я еще не тестировал его как следует. Он предполагает неравенство треугольника, все ребра существуют и тому подобное. Во многом это работает так же, как и тот ответ, который я изложил. Он печатает каждую итерацию; последний - оптимизированный 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;
}
}
}
}
person
Community
schedule
29.05.2010
+1 за выдачу почти работающей реализации
- person Mahesh Velaga; 05.01.2011
@ Иссак: Не совсем. Когда вы разместили это, я также реализовал 2-opt. С этим
almost
я имел в виду, насколько это решение было бы подходящим для моей цели. Извините за путаницу.
- person Mahesh Velaga; 09.07.2011
Полезный код - спасибо, но ПРЕДУПРЕЖДЕНИЕ: .GenerateMutations () не работает (возвращает null) в случаях с одним и двумя городами.
- person ChrisJJ; 28.09.2011
Что ж, ваше решение TSP всегда будет далеко не идеальным. Нет кода, но вот как сделать 2-Opt. Это не так уж и плохо:
- Вам нужен класс с именем Stop, у которого есть свойства Next, Prev и City, и, возможно, свойство Stops, которое просто возвращает массив, содержащий Next и Prev.
- Когда вы свяжете их вместе, мы назовем это Туром. Tour имеет свойство Stop (подойдет любая из остановок) и свойство AllStops, геттер которого просто проходит остановки и возвращает их.
- Вам нужен метод, который берет тур и возвращает его стоимость. Назовем это Tour.Cost ().
- Вам нужен Tour.Clone (), который просто обходит остановки и клонирует их по отдельности.
- Вам нужен метод, который генерирует набор маршрутов с переключением двух ребер. Назовите этот Tour.PossibleMutations ()
- Начните с вашего решения NN
- Вызовите на нем PossibleMutations ()
- Позвоните Cost () по всем из них и выберите тот, у которого самый низкий результат.
- Повторяйте, пока стоимость не снизится
person
Community
schedule
28.05.2010
Если вы собираетесь брутфорс, почему бы не найти оптимальное!
- person ; 28.05.2010
@Moron - Я не уверен, что понимаю взаимосвязь между минимальными остовными деревьями и 2-опт. Вы говорите, что используете предварительный заказ MST, а затем применяете 2-opt или что-то еще?
- person ; 28.05.2010
Моя вина. Я думал, что 2-opt означает в два раза больше оптимального, и в этом случае MST работает. Я удалил свой ответ.
- person ; 28.05.2010
ха-ха, ты сменил имя с Морон на Арьябхатта и похоже я просто придурок
- person ; 02.07.2011
Если проблема заключается в евклидовом расстоянии, и вы хотите, чтобы стоимость решения, полученного с помощью алгоритма, находилась в пределах 3/2 от оптимума, тогда вам нужен алгоритм Кристофидеса. У ACO и GA нет гарантированной стоимости.
person
Gigamegs
schedule
12.03.2011