7

我正在尝试根据“排序图”对 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)。时间戳可用于打破循环，将循环中的旧时间戳记录从排序映射中删除，直到循环消失
  • 如果排序图中不存在 ID，则将其排序在排序图中存在的任何 ID 之后

示例：给定排序图(C, A, 1/1/1900), (C, B, 1/1/2000)和(A, B, C, D)要排序的列表，排序后的输出将是(C, B, A, D)。

把这些规则变成算法让我很困惑。这是我到目前为止所拥有的：

  1. 从数据库中获取最新的排序图。对于每对唯一的 ID，我最多会获得一条记录。

  2. 从排序图中删除循环。如何？还是在第 4 步中简单地忽略循环是否更容易？

  3. 转换内存中的排序图以获得最佳性能。例如，构建一个哈希表，其键是排序映射中的每个唯一 ID，这样我就可以快速找到包含特定 ID 的所有排序映射行。

  4. 使用通用二进制排序库对我的 ID 数组进行排序，该库使用接受任何两个 IDID1和ID2参数的自定义比较函数。比较函数：

    一个。查找包含ID1或ID2使用第 3 步中的哈希表的所有排序映射条目。

    湾。如果我在排序图中已经有一条包含ID1和的记录ID2，请停下来——我们知道哪个应该是第一个！

    C。如果在排序图中既没有找到 ID1 也没有找到 ID2，则为平局。返回一个确定性的任意结果（例如，较低的 ID 获胜）。

    d。如果一个 ID 在排序图中但另一个不在，请停止。找到的应该首先排序。

    e. 如果我们到达这里，两个 ID 都在排序图中，但在排序图中没有直接比较可用。怎么办？

性能不是一个大问题，因为排序图的最大大小低于 20K 行，并且被排序的最大 ID 数低于 30。

有想法吗？

FWIW，我们将使用 .NETList<T>.Sort(Comparison<T>)在 C# 中进行排序，但底层算法显然与语言和平台无关。

如果你很好奇，这里是这个算法的现实需求：

我们公司为送货司机构建移动应用程序，他们每天访问他们负责的 100-150 个地点中的大约 20 个地点。每天的位置列表是根据每个位置的库存动态分配的。库存低的地点获得新库存的交付，而仍然有足够库存的地点不被访问。

司机可以按任何顺序自由地访问地点，但他们通常每天都会采取类似的路线（例如，早上交通不便时访问城镇南部的地点，然后在交通繁忙时访问城镇北部的地点南）。

我们选择不使用自动确定最有效行车路线的 3rd-party 路由软件。相反，我们发现让司机选择路线会更好，因为路线软件很难受到诸如“该建筑物的装卸码头通常仅在早上 7 点之前才有空”或“需要签署送货收据的人早早离开”等限制条件。星期五”，这对交货时间表有很大影响。

无论如何，我们希望使用司机的历史选择，按照司机上次访问相同地点的相同顺序对每天的行程进行排序。这将为驾驶员提供与他的喜好相匹配的每天精心安排的行程，除非在特殊情况下，否则他无需手动重新安排时间表。这将每天为驾驶员节省一两分钟，随着时间的推移而增加。

每个历史行程实际上都是这样的列表（ID1，ID2，ID3，...，IDN，时间戳），但作为存储数百个过去时间表的替代方案，我认为分解每个 N 机器历史行程会更容易成对机器。这意味着我最多必须存储 N*N-1 个元组，因为较新的排序总是会将较旧的排序排除在排序映射之外。如果这是一个糟糕的简化，请告诉我。;-)

4

2 回答 2

3

您要查找的内容称为拓扑排序。使用该搜索词，您可能会找到非常好的资源。

在您的特定领域中存在一种复杂情况：循环（因为驱动程序随着时间的推移表现不一致）。您需要打破依赖循环这一事实是正确的，否则拓扑排序将失败。

您还需要打破所有长度大于两个的循环。

让我们将 ID-map 视为图形：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完全正确。这是一种启发式方法，您可以根据自己的需要进行调整。

于 2012-09-01T09:43:22.370 回答
0

我将提出一种替代方法，但如果我误解了业务需求，请告诉我。

有一个像 (DriverId, LocationId, Priority) 这样的表，用于存储每个驱动程序位置的相对优先级。

每当您需要处理已完成的行程时，从列表底部（最后访问的位置）开始，并为每个位置运行以下算法，沿列表向上：

  • 如果该位置的优先级尚未大于其下方位置的优先级，则 newPriority = priorityBelow + 1。（如果下方没有任何内容，priorityBelow = 0）

处理完列表后，将优先级重新归一化为 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

于 2012-08-31T06:55:38.370 回答