Solution to travelling salesman problem using nearest neighbour algorithm in one LINQ query?

Question

Given

List<Point> cities = /* ... */ ;
double distance(Point a, Point b) { /* ... */ };

is there a single LINQ query that returns the travelling salesman shortest route by nearest neighbour algorithm as a List<int> of the indices of cities?

Answer 1

I don't think you can do everything in a single query, some parts of the algorithms will have to be implemented separately.

Here's a brute-force implementation that examines all city permutations and returns the shortest path that visits all the cities:

var bestPath =
   cities.Permutations()
      .MinBy(
        steps => steps.Aggregate(
                    new { Sum = 0, Previous = default(Point) },
                    (acc, c) =>
                        new
                        {
                            Sum = acc.Sum + (acc.Previous != null ? Distance(c, acc.Previous) : 0 ),
                            Previous = c
                        },
                    acc => acc.Sum));

The Permutations extension method is defined as follows:

public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
{
    var query =
        from item in source
        from others in source.SkipOnce(item).Permutations()
        select new[] { item }.Concat(others);
    return query.DefaultIfEmpty(Enumerable.Empty<T>());
}

public static IEnumerable<T> SkipOnce<T>(this IEnumerable<T> source, T itemToSkip)
{
    bool skipped = false;
    var comparer = EqualityComparer<T>.Default;
    foreach (var item in source)
    {
        if (!skipped && comparer.Equals(item, itemToSkip))
            skipped = true;
        else
            yield return item;
    }
}

Of course there are much better approaches to solve this problem, but this one works... Most of it is in a single query, the only parts that are implemented separately are not specific to the problem at hand and can be reused for other tasks.

EDIT: oops, I just realized I also used the non-standard MinBy method; you can find it in the MoreLinq project