在一个LINQ查询中使用最近邻算法解决旅行商问题? [英] Solution to travelling salesman problem using nearest neighbour algorithm in one LINQ query?
问题描述
给予
List<Point> cities = /* ... */ ;
double distance(Point a, Point b) { /* ... */ };
是否有一个LINQ查询通过最近邻算法返回旅行推销员最短路线作为cities
索引的List<int>
?
is there a single LINQ query that returns the travelling salesman shortest route by nearest neighbour algorithm as a List<int>
of the indices of cities
?
推荐答案
我认为您无法在单个查询中完成所有操作,算法的某些部分将必须单独实现.
I don't think you can do everything in a single query, some parts of the algorithms will have to be implemented separately.
这是一个蛮力实施,它检查所有城市排列并返回访问所有城市的最短路径:
Here's a brute-force implementation that examines all city permutations and returns the shortest path that visits all the cities:
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;
}
}
当然,有更好的方法可以解决此问题,但是这种方法可以工作...大部分都在单个查询中,只有单独实现的部分并不特定于手头的问题,可以重用完成其他任务.
Of course there are much better approaches to solve this problem, but this one works... Most of it is in a single query, the only parts that are implemented separately are not specific to the problem at hand and can be reused for other tasks.
糟糕,我刚刚意识到我也使用了非标准的MinBy
方法;您可以在MoreLinq项目中
oops, I just realized I also used the non-standard MinBy
method; you can find it in the MoreLinq project
这篇关于在一个LINQ查询中使用最近邻算法解决旅行商问题?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!