在一个LINQ查询中使用最近邻算法求解旅行推销员问题

本文关键字：近邻 最近 算法 问题 旅行推销员 一个 查询 LINQ | 更新日期: 2023-09-27 18:09:28

给定

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

是否存在通过最近邻算法返回旅行推销员最短路线作为cities的索引的List<int>的单个LINQ查询？

在一个LINQ查询中使用最近邻算法求解旅行推销员问题

我不认为你可以在一个查询中完成所有事情，算法的某些部分必须单独实现。

这里有一个蛮力实现，它检查所有城市的排列，并返回访问所有城市的最短路径：

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

Permutations扩展方法定义如下：

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

当然，有更好的方法来解决这个问题，但这个方法有效。。。大部分都在一个查询中，唯一单独实现的部分并不是针对手头的问题的，可以重复用于其他任务。

编辑：哎呀，我刚刚意识到我也使用了非标准的MinBy方法；您可以在MoreLinq项目

中找到它

如果你只需要在一个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循环更可读

相关文章：