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

Question

迄今为止我最好的镜头：

送货车辆需要进行一系列送货（d₁、d₂、...d_n），并且可以以任意顺序执行此操作 - 换句话说，集合 D = {d₁,d₂,...d_{n< 的所有可能排列/sub>} 是有效的解决方案 - 但需要在离开路线一端的基站之前确定特定的解决方案（例如，想象一下包裹需要按后进先出的方式装载到车辆中）。}

此外，各种排列的成本也不相同。 它可以计算为 d_{i -1} 和 d_i 之间行驶距离的平方和，其中 d₀ 被视为基站，但需要注意的是，任何涉及方向改变的路段成本都是原来的 3 倍（想象一下这是在铁路或气动管道上发生的，备份会扰乱其他交通）。

给定一组交付 D 表示为距基站的距离（因此 abs(d_i-d< /code>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)) 相比，有洞察力的人会发现， 我的问题是

：你能想出一个看似合理的问题描述吗？它自然会导致粗心的人陷入更糟糕（或者更糟糕的）排序算法实现？

Answer 1

我假设您在面试中使用这个问题是为了看看申请人是否可以在看似复杂的问题中注意到一个简单的解决方案。

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

您提供了太多信息。

解决这个问题的关键是认识到这些点是一维的，并且只需要排序即可。 为了让这个问题变得更加困难，尽可能隐藏这个事实。

最大的线索是距离公式。 它引入了改变方向的惩罚。 我首先想到的是尽量减少这种惩罚。 为了消除惩罚，我必须将它们按某个方向排序，这种排序是自然排序顺序。

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

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

我将其表述为：

给定所有可能的列表
n 个交付地点的排列，
其中每个交付排列
(d₁, d₂, ...,
d_n) 的成本定义为：

返回排列 P，使得
P 的成本小于或等于任何
其他排列。

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

如果他们构建一个循环来比较成本，请询问他们算法的 big-o 运行时间是多少，其中 n 是送货地点的数量（另一个陷阱）。

Answer 2

这不是直接答案，但我认为需要更多澄清。

d_i 允许为负数吗？ 如果是这样，据我所知，仅排序是不够的。

例如：

d₀ = 0

deliveries = (-1,1,1,2)

在这种情况下，最佳路径似乎是<代码>1> 2> 1> -1。

编辑：这实际上可能不是最佳路径，但它说明了这一点。

Answer 3

首先找到最佳解决方案后，您可以将其重新表述为

“给我一个证明，证明以下说服对于以下规则集是最佳的，其中最佳意味着所有阶段成本之和产生的最小数字，考虑到考虑到所有阶段(A..Z)都需要出现一次且仅一次：

说服：

A->C->D->Y->P->...->N

阶段成本：

A->B = 5,
B->A = 3,
A->C = 2,
C->A = 4,
...
...
...
Y->Z = 7,
Z->Y = 24."

这应该让某人忙碌一段时间。

Answer 4

这让我想起了背包问题，而不是旅行推销员。 但背包也是一个 NP 难问题，因此，如果人们将你的问题与背包相关联，你可能可以欺骗人们使用动态规划想出一个过于复杂的解决方案。 基本问题是：

能否达到至少 V 的值
不超过重量W？

现在的问题是，当 V 唯一时，您的距离可以找到一个相当好的解决方案，如下所示：

每种类型的背包问题
项目 j 具有不同的值
重量单位 (vj = pj/wj) 是
被认为是最简单的之一
NP 完全问题。 确实是经验主义的
复杂度约为 O((log
n)2) 非常大的问题可以是
很快就解决了，例如2003年
求解所需的平均时间
n = 10,000 的实例低于 14
使用商品个人的毫秒
计算机1。

因此，您可能想要声明多个站点/包裹可能共享相同的 vj，从而邀请人们思考真正困难的解决方案：

但是在
多个项目的退化情况
共享相同的值 vj 变成
极端情况下困难得多
vj = 常数的情况
具有复杂性的子集和问题
O(2N/2N)。

因此，如果您将每个值的权重替换为每个值的距离，并声明几个距离实际上可能共享相同的值，那么退化，有些人可能会落入这个陷阱。

Answer 5

这不就是（NP-Hard）旅行推销员问题吗？ 你似乎不会让事情变得更加困难。

也许对问题的表述使得实际的算法不清楚 - 例如，通过将路径描述为单轨铁路线，这样人们就必须从领域知识中推断出回溯的成本更高。

如果以一种让人忍不住进行递归比较的方式来描述问题——例如“你能通过使用你最好的（到目前为止）结果的最佳最大子集来加速算法吗”？

顺便说一句，这样做的目的是什么——听起来似乎是为了折磨受访者。

Answer 6

您需要更清楚送货卡车是否必须返回基地（使其成为往返）。 如果卡车确实返回，那么简单的排序不会生成最短路线，因为从最远点到基地的返回平方成本非常高。 在“出去”的路上错过一些啤酒花并在回来的路上使用它们会更便宜。

如果你欺骗某人给出了错误的答案（例如，没有向他们提供所有信息），那么是他们的愚蠢还是你的欺骗造成了这种情况？

如果智者不留意自我的谎言，他们的智慧会有多大？