Soluzione al problema del commesso viaggiatore utilizzando l'algoritmo adiacente più vicino in una query LINQ?

Question

Dato

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

c'è una singola query LINQ che restituisce il commesso viaggiatore percorso più breve da un algoritmo vicino più prossimo come List<int> degli indici di cities?

Answer 1

Non penso che si possa fare tutto in una singola query, alcune parti degli algoritmi dovranno essere implementate separatamente.

Ecco un'implementazione di forza bruta che prende in esame tutte le permutazioni della città e restituisce il percorso più breve che visita tutte le città:

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

Il metodo Permutations interno è definito come segue:

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

Di Certo, ci sono degli approcci molto migliori per risolvere questo problema, ma questo funziona ... La maggior parte si trova in una singola query, le uniche parti che sono implementate separatamente non sono specifiche del problema in questione e possono essere riutilizzate per altre attività.

MODIFICA: oops, ho appena realizzato che ho utilizzato anche il metodo non standard MinBy; lo si può trovare in the MoreLinq project

Answer 2

Se avete solo bisogno algoritmo vicino più vicino, in una singola query LINQ, si può fare in questo modo:

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

Anche se penso che sia più leggibile utilizzando per-loop