Rozwiązanie problemu komiwojażera przy użyciu algorytmu najbliższego sąsiada w jednym zapytaniu LINQ?

Question

Biorąc

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

istnieje pojedynczy kwerendy LINQ, która zwraca komiwojażera najkrótsza droga przez algorytm najbliższego sąsiada jako List<int> z indeksami cities?

Answer 1

Nie sądzę, że można zrobić wszystko w jednym zapytaniu, niektóre części algorytmów będą musiały zostać zaimplementowane osobno.

Oto realizacja brute-force, która analizuje wszystkie permutacje miasto i wraca najkrótszą ścieżkę, która odwiedza wszystkie miasta:

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

Sposób Permutations rozszerzenie jest zdefiniowany następująco:

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 Oczywiście istnieje wiele lepszych podejść do rozwiązania tego problemu, ale ten działa ... Większość jest w jednym zapytaniu, jedyne części, które są zaimplementowane osobno, nie są specyficzne dla problemu i mogą być ponownie wykorzystane do innych zadań.

EDYCJA: oops, Właśnie zdałem sobie sprawę, że również użyłem niestandardowej metody MinBy; można go znaleźć in the MoreLinq project

Answer 2

Jeśli wystarczy algorytm najbliższego sąsiada w jednej kwerendzie pojedynczego LINQ, można to zrobić w ten sposób:

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

Nawet jeśli myślę, że to bardziej czytelne przy użyciu for-pętle