这个问题的名称是什么？

Question

给出一条线上各点之间的距离列表。

例如：

• 20 c和d之间c和b
• 90之间
• 170 a和d之间

返回的a和b之间排序的点序列，因为它们出现在它们之间的距离上：

例如以上输入收益率： a < ---- 80 -----> c < ---- 20 ------> b < ---- 70 -----> d或相反的顺序（无所谓）

这个问题叫什么？我想研究它。

如果有人知道，那么为什么会有一些可能的渐近运行时间呢？

Answer 1

不确定它是否有名称;更正式地说，这将是：

|a-b| = 100 
|c-b| = 20 
|c-d| = 90 
|a-d| = 170 

其中|x|代表x的absolute value

至于广义系统去，如果你有这种类型的k个未知数的N个方程，你有N个标志的选择。不失一般性（因为任何解决方案都会得到逆向排序的第二种解决方案），您可以为第一个方程选择一个符号，为其中一个未知物选择一个特定值（因为整个事物可以左右滑动）。然后你有剩余方程的可能性，你所要做的就是通过它们去查看哪些方法（如果有的话）有解决方案。由于该系数均+/- 1和每个方程有2个未知数，你只是通过他们去逐一：

Step 1: Without loss of generality, 
    choose a sign for one equation 
    and pick a value for one unknown: 
a-b = 100, a = 0 

Step 2: Choose signs for the remaining absolute values. 
a = 0 
a-b = 100 
c-b = 20 
c-d = 90 
a-d = 170 

Step 3: go through them one by one to solve/verify there aren't conflicts 
(time = N steps). 
0-b = 100 => b = -100 
c-b = 20 => c = -80 
c-d = 90 => d = -170 
a-d = 170 => OK  => (0,-100,-80,-170) is a solution 

Step 4: if this doesn't work, go back through the possible choices of sign 
and try again, starting at step 2. 

Full set of solutions is (0,-100,-80,-170) 
and its negation (0,100,80,170) and any number x<sub>0</sub> added to all terms. 

所以上限为运行时是O（N * 2 ^N-1 ）≡ O（N * 2 ^N）。

我想可能有一个捷径，但没有一个明显的想法。

Answer 2

代数...

，或者它可能是旅行商问题

Answer 3

的简化我没有一个算法预定方便，但是这听起来像一个graph search problem如果路径是限制。您可能可以使用Dijkstra's Algorithm或它的一些变体。

Answer 4

正如你所写的，你的问题只是一个非线性方程组（表示为绝对值或二次方程）。然而，它看起来类似于寻找哥伦布统治者或完美统治者的问题。

如果你认为你的约束是二次方程，例如。（a-b）^ 2 = 100^2，那么你可以将其表述为一个二次规划问题，并使用一些经过深入研究的技术来解决这类问题。

Answer 5

考虑到每个区段的方向符号X[i] -> X[i+1]它变成了boolean satisfiability problem。我看不到明显的简化。运行时间是O（2^N） - 特别是用N值和O（1）表达式来测试的2 ^（N-2）测试。

假设a = 0和固定的a -> b方向：

a = 0 
b = 100 
c = b + 20 X[0] = 100 + 20 X[0] 
d = c + 90 X[1] = 100 + 20 X[0] + 90 X[1] 
test d == 170 

其中X[i]是+1或-1。尽管d的表达式似乎需要O（N）运算（（N-2）乘法和（N-2）加法运算），但是通过使用Gray code或其他此类机制来改变只有一个X的状态一次，所以成本可以是O（1）每次测试。 （尽管对于N = 4，它可能不值得）

如果你有更多的约束条件可能会导致简化 - 如果给出|b-d| == 70，那么你只需要测试两个案例而不是四个 - 基本上是b， c和d成为他们自己完全受限的子问题。

及其简化还可以从三角形属性

| |a-b| - |b-c| | <= |a-c| <= |a-b| + |b-c|出现所有的a，b和c。

所以如果你有很多点，并且你知道在给定X的赋值的情况下点之间的距离总和，并且总距离目标值远大于总点之间的距离其余的点，你可以推断，没有任何组合的剩余点将工作。