代码之家 › 专栏 › 技术社区 › MarkusQ

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

puzzle analysis algorithm

MarkusQ · 技术社区 · 17 年前

我迄今为止最好的投篮:

_2. _n ),并且可以以任何顺序执行——换句话说,集合D={D的所有可能排列 _2. _n

和 d _我

D abs(d _我 -d ) 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

我的问题是:你能想出一个合理的问题描述吗更糟

6 回复 | 直到 5 年前

Community Mohan Dere 9 年前

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

你提供的信息太多了。

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

排列。这让他们认为O(n!)算法实际上可能是预期的。

我会这样表述:

其中交付的每个排列 _2. _n )成本定义如下:

$\sum_{i=1}^{n-1}\sqrt[]{(d_{i}-d_{i+1})^2}$

P的成本小于或等于任何

真正需要做的就是按照第一种排列方式阅读并排序。

如果他们构建一个单独的循环来比较成本,问他们算法的big-o运行时是什么,其中n是交付位置的数量(另一个陷阱)。

recursive 17 年前

是d _我

d = 0

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

1 > 2 > 1 > -1 .

dsm 17 年前

(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."

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

Robert Gould 17 年前

Knapsack problem

项目j具有不同的值重量单位(vj=pj/wj)为被认为是最简单的之一复杂性约为O(log n) 2)可能会出现非常大的问题很快就解决了,例如在2003年解决所需的平均时间 n=10000的实例数低于14 计算机 1 .

然而,在共享相同的vj值极端情况下要困难得多 vj=常数的情况具有复杂性的子集求和问题

Steve B. 17 年前

Travelling Salesman Problem

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

那么,以一种有人倾向于进行递归比较的方式描述这个问题呢?例如,“你能通过使用(到目前为止)最佳结果的最佳最大子集来加速算法吗?”?

Phil H 17 年前

返回,然后进行简单排序不产生最短的路线,因为从最远点到基地的回报的平方成本很高。在“出去”的路上错过一些跳,在回来的路上使用它们,结果证明更便宜。

如果你诱骗某人给出一个糟糕的答案(例如,不向他们提供所有信息),那么是他们的愚蠢还是你的欺骗造成了这种情况?

智者的智慧有多大,如果他们不理会自我的谎言?