Tek bir LINQ sorgusunda en yakın komşu algoritması kullanarak satıcı problemi çözümü için çözüm?

Question

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

cities indekslerinin bir List<int> olarak en yakın komşu algoritması tarafından seyyar satıcı en kısa rota döndüren bir tek LINQ sorgusu var

Verilen?

Answer 1

Her şeyi tek bir sorguda yapabileceğinizi düşünmüyorum, algoritmaların bazı bölümleri ayrı ayrı uygulanmalıdır.

Permutations uzatma yöntemi olarak tanımlanır

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

şu: Of

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

İşte

tüm şehir permütasyon inceler ve tüm şehirleri ziyaret kısa yolu döndüren bir kaba kuvvet uygulaması var Elbette bu sorunu çözmek için çok daha iyi yaklaşımlar vardır, ancak bu çalışır ... Çoğu tek bir sorguda, ayrı ayrı uygulanan tek parçalar, eldeki sorunlara özgü değildir ve diğer görevler için yeniden kullanılabilir.

DÜZENLEME: oops, Ben sadece standart olmayan MinBy yöntemini kullandım; Bulabileceğiniz o in the MoreLinq project

Answer 2

Sadece tek LINQ sorgusunda Yakın Komşu algoritması gerekiyorsa, bu şekilde yapabilirsiniz:

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

Ben