Solving the traveling salesman problem using the nearest neighbor algorithm in a single LINQ query?

Question

Considering

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

Is there a single LINQ query that returns the shortest salesman route using the nearest neighbor algorithm as List<int>indices cities?

Answer 1

I do not think that you can do everything in one request, some parts of the algorithms should be implemented separately.

Here brute force is realized, which checks all the permutations of cities and returns the shortest path that visits all 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 extension method is Permutationsdefined 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;
    }
}

, , ... , , , .

EDIT: oops, , MinBy; MoreLinq

Answer 2

Nearest Neighbor LINQ, :

var nearestNeighTour = cities.Skip(1).Aggregate(
new List<int>() { 0 },
(list, curr) =>
{
    var lastCity = cities[list.Last()];
    var minDist = Enumerable.Range(0, cities.Count).Where(i => !list.Contains(i)).Min(cityIdx => distance(lastCity, cities[cityIdx]));
    var minDistCityIdx = Enumerable.Range(0,cities.Count).Where(i => !list.Contains(i)).First(cityIdx => minDist == distance(lastCity, cities[cityIdx]));
    list.Add(minDistCityIdx );
    return list;
});

, , for-loops