algorithm - 提出这个问题最阴险的方法是什么？

Question

到目前为止我最好的镜头:

A delivery vehicle needs to make a series of deliveries (d₁,d₂,...d_n), and can do so in any order--in other words, all the possible permutations of the set D = {d₁,d₂,...d_n} are valid solutions--but the particular solution needs to be determined before it leaves the base station at one end of the route (imagine that the packages need to be loaded in the vehicle LIFO, for example).

Further, the cost of the various permutations is not the same. It can be computed as the sum of the squares of distance traveled between d_{i -1} and d_i, where d₀ is taken to be the base station, with the caveat that any segment that involves a change of direction costs 3 times as much (imagine this is going on on a railroad or a pneumatic tube, and backing up disrupts other traffic).

Given the set of deliveries D represented as their distance from the base station (so abs(d_i-d_j) is the distance between two deliveries) and an iterator permutations(D) which will produce each permutation in succession, find a permutation which has a cost less than or equal to that of any other permutation.

现在，从这个描述中直接实现可能会导致这样的代码:

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

这是 O(n*n!^2)，例如非常糟糕——特别是与 O(n log(n)) 相比，有洞察力的人会发现，只需对 D 进行排序。

我的问题:你能想出一个合理的问题描述，这自然会导致粗心的人进入排序算法的更糟(或不同程度的糟糕)实现吗？

Answer 1

我假设您将这个问题用于面试，看看求职者是否能在看似复杂的问题中注意到一个简单的解决方案。

[这个假设是不正确的 -- MarkusQ]

你提供的信息太多了。

解决这个问题的关键是认识到点在一个维度上，并且只需要排序。为了让这个问题更难，请尽可能隐藏这个事实。

最大的线索是距离公式。它引入了改变方向的惩罚。我想到的第一件事就是最小化这种惩罚。为了消除惩罚，我必须按特定方向对它们进行排序，此排序是自然排序顺序。

我会取消改变方向的惩罚，这太过分了。

另一个主要线索是算法的输入值:整数列表。给他们一个排列列表，甚至是所有排列。这让他们认为 O(n!) 算法实际上可能是预期的。

我会这样表述:

Given a list of all possible permutations of n delivery locations, where each permutation of deliveries (d₁, d₂, ..., d_n) has a cost defined by:

Return permutation P such that the cost of P is less than or equal to any other permutation.

所有真正需要做的是读取第一个排列并对其进行排序。

如果他们构造一个循环来比较成本，请问他们算法的大运行时间是多少，其中 n 是交付位置的数量(另一个陷阱)。