7

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

运送车辆需要进行一系列运送（d 1 ,d 2 ,...d n），并且可以按任何顺序进行 - 换句话说，集合 D = {d 1的所有可能排列， d 2 ,...d n } 是有效的解决方案——但具体的解决方案需要在路线的一端离开基站之前确定（假设需要在车辆 LIFO 中装载包裹，例如）。

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

给定一组传递D表示为它们与基站的距离（所以abs(di -dj)是两个传递之间的距离）和一个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)，例如非常糟糕——尤其是与有洞察力的人通过简单地对 D 进行排序会发现的 O(n log(n)) 相比。

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

4

6 回答 6

6

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

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

你提供的信息太多。

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

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

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

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

我将其表述为：

给定 n 个交付位置的所有可能排列的列表，其中每个交付排列 (d 1 , d 2 , ..., d n ) 的成本定义为：

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

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

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

于 2009-03-13T17:49:48.503 回答
2

这不是一个直接的答案，但我认为需要进一步澄清。

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

例如：

d0 = 0

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

在这种情况下，最佳路径似乎是1 > 2 > 1 > -1.

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

于 2009-03-13T16:48:22.457 回答
1

你可以改写它，首先找到最佳解决方案，如

“给我一个证明，证明以下说服对于以下规则集是最优的，其中最优意味着最小的数字来自所有阶段成本的总和，同时考虑到所有阶段(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."

那应该让某人忙一阵子。

于 2009-03-18T16:51:36.950 回答
1

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

可以在不超过重量 W 的情况下达到至少 V 的值吗？

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

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

所以你可能想说明几个站点/包裹可能共享同一个 vj，邀请人们思考真正困难的解决方案：

然而，在多个项目共享相同值 vj 的退化情况下，在 vj = 常数是复杂度为 O(2N/2N) 的子集和问题的极端情况下变得更加困难。

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

于 2009-03-22T07:49:09.757 回答
0

这不只是（NP-Hard）旅行商问题吗？你似乎不太可能让它变得更难。

也许用措辞来表达问题，使实际算法不清楚——例如，将路径描述为单轨铁路线，这样人们就不得不从领域知识中推断出回溯成本更高。

如果以某人很想进行递归比较的方式来描述问题，例如“您能否通过使用最佳（迄今为止）结果的最佳最大子集来加速算法”？

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

于 2009-03-13T16:49:03.500 回答
0

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

如果您欺骗某人给出错误的答案（例如，不向他们提供所有信息），那么是他们的愚蠢还是您的欺骗导致了它？

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

于 2009-03-23T08:58:32.577 回答