¿Solución al problema del vendedor ambulante usando el algoritmo del vecino más cercano en una consulta LINQ?

Question

Dado

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

hay una sola consulta LINQ que devuelve el viajante ruta más corta por el algoritmo del vecino más cercano como List<int> de los índices de cities?

Answer 1

No creo que pueda hacer todo en una sola consulta, algunas partes de los algoritmos deberán implementarse por separado.

Aquí hay una aplicación de fuerza bruta que examina todas las permutaciones de la ciudad y devuelve el camino más corto que visita todas las ciudades:

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

El método Permutations extensión se define como sigue:

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

De Por supuesto, existen métodos mucho mejores para resolver este problema, pero este funciona ... La mayor parte se basa en una sola consulta, las únicas partes que se implementan por separado no son específicas del problema en cuestión y pueden reutilizarse para otras tareas.

EDITAR: oops, me acabo de dar cuenta de que también usé el método MinBy no estándar; usted lo puede encontrar in the MoreLinq project

Answer 2

Si sólo necesita más cercano algoritmo del vecino en una consulta LINQ sola, puede hacerlo de esta manera:

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

Aunque yo creo que es más fácil de leer usando para-bucles