作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
给定
List<Point> cities = /* ... */ ;
double distance(Point a, Point b) { /* ... */ };
是否有单个 LINQ 查询通过最近邻算法返回旅行推销员最短路线作为 List<int>
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;
}
}
当然有很多更好的方法来解决这个问题,但是这个是有效的......大部分是在一个查询中,单独实现的唯一部分并不特定于手头的问题并且可以重用用于其他任务。
编辑:糟糕,我刚刚意识到我还使用了非标准的 MinBy
方法;你可以找到它in the MoreLinq project
关于c# - 在一个 LINQ 查询中使用最近邻算法解决旅行商问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7538622/
我正在制作一个应用程序,我在其中为每个国家/地区分配不同的值并根据该值执行某些操作。喜欢: Argentina 3 Australia 7 USA 23 要选择国家/地区,我需要使用用户当前所在的国家
这里是一般 Node mongodb 问题。 我有这个功能: static addSpaceToCreator = ( userId, spaceId, callback ) => {
Linux 中的 tcp 数据路径是否有很好的概述(2.6,如果路径实际不同则不是 2.4)?在 tcp/ip 堆栈处理的不同阶段,数据包在哪里? 数据包如何打包到tcp段,然后是ip数据包。它是如何
我是一名优秀的程序员,十分优秀!