根据以前的排序进行排序
我试图根据“排序映射”对ID列表进行排序，排列映射是一个(ID1, ID2, timestamp)元组数组，它确定哪些ID应在其他ID之前排序。 这是规则：
ID1应在ID2之前排序。 (C, A, 1/1/1900), (C, B, 1/1/2000)则B在A之前排序。 (A, B, 1/1/1950), (B, C, 1/1/1980), (C, A, 1/1/1900) 。 时间戳可以用来中断循环，在循环中删除旧时间戳的记录，直到循环消失 例如：给定排序图(C, A, 1/1/1900), (C, B, 1/1/2000)和列表(A, B, C, D)进行排序，排序的输出将是(C, B, A, D) 。
通过将这些规则转化为算法，我感到难以置信。 这是我迄今为止的：
从数据库中获取最新的排序图。 每一对唯一的ID最多只能得到一条记录。
从排序映射中删除循环。 怎么样？ 或者更容易忽略周期作为步骤4的一部分？
在内存中转换排序图以获得最佳性能。 例如，构建一个散列表，其关键是排序映射中的每个唯一ID，这样我就可以快速找到包含特定ID的所有排序映射行。
使用通用二进制排序库使用自定义比较函数对ID的数组进行排序，该函数接受任何两个ID ID1和ID2参数。 比较功能：
一个。 使用步骤3中的散列表查找包含ID1或ID2所有排序映射条目。
湾 如果我在排序图中已经有一个包含ID1和ID2的记录，请停止 - 我们知道哪一个应该是第一个！
C。 如果在排序图中找不到ID1和ID2，那么它就是一条平行线。 返回确定性的任意结果（例如，较低的ID获胜）。
d。 如果一个ID在分类图中，但另一个不在，则停止。 找到的应该先排序。
即 如果我们到达这里，这两个ID都在分类图中，但在分类图中没有可用的直接比较。 怎么办？
性能不是一个大问题，因为排序映射的最大大小不超过20K行，并且排序的最大ID数小于30。
有想法？
FWIW，我们将使用.NET的List<T>.Sort(Comparison<T>)在C＃中进行排序，但底层算法显然是语言和平台不可知的。
如果您很好奇，下面是该算法的真实需求：
我们公司为送货司机构建移动应用程序，每天访问他们负责的100-150个地区中的大约20个地点。 每天的位置列表是根据每个位置的库存动态分配的。 库存数量少的地点会获得新库存，而尚未访问足够库存的地点。
驾驶员可以以任何顺序自由地访问地点，但他们通常每天都会采用类似的路线（例如，当早上交通轻时访问城镇南部的地点，然后在交通加重时访问城镇北部的地点南）。
我们选择不使用自动确定最有效驾驶路线的第三方路线软件。 相反，我们发现让驾驶员选择路线会更好，因为路由软件很难满足约束条件，例如“该大楼的装货码头通常在7AM之前才是免费的”，或者“需要签署收货收据的人早点离开星期五“，这对交付时间表有很大影响。
无论如何，我们希望使用驾驶员的历史选项按照驾驶员上次访问相同位置的顺序对每天的行程进行排序。 这将使驾驶员每天都能根据自己的喜好精心安排行程，而不需要手动重新安排时间表，除非出现异常情况。 这会每天为驾驶员节省一两分钟，随着时间的推移累计。
每个历史行程实际上都是这样的列表（ID1，ID2，ID3，...，IDN，时间戳），但作为存储数百个过去时间表的替代方案，我认为分解每个N机历史行程成对机器。 这意味着我必须存储至多N * N-1个元组，因为更新的排序总是将旧排序从排序映射中排除。 如果这是一个不好的简化，让我知道。 ;-)
你在找什么叫做拓扑排序。 使用该搜索词可以找到非常好的资源。
您的特定领域有一个复杂因素：周期（因为司机在一段时间内表现不一致）。 你说得对，因为你需要打破依赖循环，否则拓扑排序会失败。
你还需要打破所有长度大于2的周期。
让我们把你的ID映射看成一个图：ID（位置）是节点。 地图中的条目是边缘（从地点ID1到地点ID2）。 一个简单的方法可以做到这一点：
while true
allCycles = getListOfAllCycles();
if (allCycles.length == 0) break;
breakNode = chooseBreakNode(allCycles); //defined later
deleteBreakNodeFrom(allCycles);
chooseBreakNode:
chose the node which has been driven to the least //node is not important
if ambiguous: chose the node in the dependency graph which is present in the highest number of cycles //breaks multiple cycles at once
if ambiguous: chose the node which is in the longest cycle
if ambiguous: pick an arbitrary node
可能我没有得到chooseBreakNode很对。 这是一种启发式的方式，您可以调整您的需求。
我会提出一种替代方法，但是如果我误解了业务需求，请告诉我。
有一个类似于（DriverId，LocationId，Priority）的表格来存储每个驱动程序的相对位置优先级。
无论何时您需要处理已完成的行程，请从列表底部开始（最后一次访问的位置），然后针对每个位置运行以下算法，并列出该列表：
处理完列表后，将优先级重新标准化为1,2,3 ...（通过使最低优先级= 1，最低优先级= 2等等）
然后，当您需要订购新的行程时，您只需按照相应的优先级值为该司机订购位置。
你有没有考虑过这种方法？
编辑：添加下面每条评论的示例代码。
给出4条历史路线：ABCD（最新），ACBE，CBDF，CBDFA（最古老），我将如何整理新的行程ABCDEF？
static Dictionary<string, int> Priorities = new Dictionary<string, int>();
static void Main(string[] args)
{
var itineraries = new string[][]{
new string[] { "C", "B", "D", "F", "A" },
new string[] { "C", "B", "D", "F" },
new string[] { "A", "C", "B", "E" },
new string[] { "A", "B", "C", "D" } };
//process past itineraries
foreach (var itinerary in itineraries)
ProcessItinerary(itinerary);
//sort new itinerary
string[] newItinerary = { "A", "B", "C", "D", "E", "F" };
string[] sortedItinerary = newItinerary.OrderByDescending(
x => Priorities.ContainsKey(x) ? Priorities[x] : 1).ToArray();
Console.WriteLine(String.Concat(sortedItinerary));
Console.ReadKey();
}
static void ProcessItinerary(string[] itinerary)
{
itinerary.Reverse().Aggregate((below, above) =>
{
int priBelow = Priorities.ContainsKey(below) ?
Priorities[below] : Priorities[below] = 1;
if (!(Priorities.ContainsKey(above) &&
Priorities[above] > priBelow))
Priorities[above] = priBelow + 1;
return above;
});
//normalize priorities
// (note: running in reverse so that if priorities tie,
// the older location has higher priority)
int i = Priorities.Count;
foreach (var pair in Priorities.OrderByDescending(x => x.Value))
Priorities[pair.Key] = i--;
}
这将打印出： ABCDFE
上一篇: sorting based on previous sorts
下一篇: Reverse Engineering?