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

到目前为止我最好的一击:

交付工具需要进行一系列交付(d ₁,d ₂,... d _n),并且可以按任何顺序进行交付- 换句话说,集合的所有可能排列D = {d ₁, d ₂,... d _n }是有效的解决方案 - 但是特定的解决方案需要在路由器的一端离开基站之前确定(想象一下这些包需要加载到车辆LIFO中,例如).

此外,各种排列的成本也不相同.它可以计算为d _{i -1}和d _i之间行进距离的平方和,其中d ₀被认为是基站,需要注意的是任何涉及方向变化的段都要花费3倍的时间(想象一下,这是在铁路或气动管上进行的,备份会破坏其他交通).

鉴于交付的集合D表示为它们与基站的距离(因此abs(d_i -d_j)是两个交付之间的距离)和迭代器permutations(D)将连续产生每个排列,找到一个成本小于或等于任何排列的排列其他排列.

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

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.

我的问题:你能否提出一个似乎合理的问题描述,这自然会导致粗心大意进入排序算法的更糟(或不同的可怕)实现？

我假设你正在使用这个问题进行面试,看看申请人是否能在一个看似复杂的问题中注意到一个简单的解决方案.

[这个假设不正确 - MarkusQ]

你提供的信息太多了.

解决这个问题的关键是要意识到这些点在一个维度上,并且只需要排序.为了使这个问题更加困难,尽可能地隐藏这个事实.

最大的线索是距离公式.它引入了改变方向的惩罚.我想到的第一件事就是尽量减少这种惩罚.为了消除惩罚,我必须在某个方向订购它们,这种排序是自然的排序顺序.

我会删除改变方向的惩罚,这太过分了.

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

我会把它说成:

给出n个交付地点的所有可能排列的列表,其中交付的每个排列(d ₁,d ₂,...,d _n)具有由以下定义的成本:

返回置换P使得P的成本小于或等于任何其他排列.

所有真正需要完成的工作都是在第一个排列中读取并对其进行排序.

如果他们构建一个单独的循环来比较成本,请询问他们算法的大运行时间,其中n是交付位置的数量(另一个陷阱).