请记住，您最大的问题是您不知道自己想要什么。所以我不得不猜测。有时看到一些猜测可以帮助您完善您想要的内容，所以这对您来说并不算太糟糕，但它确实使您的问题对于本网站的格式更加困难。
首先，我假设弹簧可以建模为有向无环图。也就是说，我可以用指向右侧的箭头替换所有弹簧。永远不会有从右到左的箭头（否则你的弹簧会弯曲成一个圆圈）。
完成此操作后，您可以使用设置逻辑来确定最左侧蓝色条的标识。（我假设只有一个 - 留作练习以弄清楚如何进行概括。）然后您可以将此条锚定在合适的位置。所有其他条将相对于它定位。这个约束看起来像：
S[leftmost] = 0
现在，我们需要一些约束。
每条边i都有一个起点和终点（因为边是有向的）。调用源点S的位置和结束点的位置E。此外，边具有最小长度l和最大长度L。由于我们固定了最左侧蓝条的位置，因此连接到它的弹簧定义了它们的端点落下的间隔。这些端点是其他弹簧等的源点。因此，每条边定义了对其端点位置的两个约束。
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
顺便说一句，请注意我们现在可以制定一个简单的线性程序：
min 1
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
如果这个程序可以解决，那么你的问题就有一个可行的解决方案。也就是说，条形长度不会对蓝条应该在哪里产生相互不一致的描述。
现在，无论这意味着什么，我们想要“均匀地最大化灰线的大小”。
最小化平均长度的偏差
这是一个想法。程序为每个条形选择的长度由下式给出E[i]-S[i]。让我们指定这个长度应该“接近” bar 的平均长度(L[i]+l[i])/2。因此，我们希望为每个柱最小化的目标数量是：
(E[i]-S[i])-(L[i]+l[i])/2
有问题的是，这个值可以是正数或负数，具体取决于是否(E[i]-S[i])>(L[i]+l[i])/2. 这不好，因为我们希望最小化与 的偏差(L[i]+l[i])/2，这个值应该始终为正。
为了应对，让我们将值平方然后取平方根，这给出：
sqrt(((E[i]-S[i])-(L[i]+l[i])/2)^2)
这似乎无法解决，但请和我在一起。
请注意，上述与取一元素向量的 L2 范数相同，因此我们可以将其重写为：
|(E[i]-S[i])-(L[i]+l[i])/2|_2
我们现在可以总结每个柱的偏差：
|(E[0]-S[0])-(L[0]+l[0])/2|_2 + |(E[1]-S[1])-(L[1]+l[1])/2|_2 + ...
这给了我们以下优化问题：
min |(E[0]-S[0])-(L[0]+l[0])/2|_2 + |(E[1]-S[1])-(L[1]+l[1])/2|_2 + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
这个问题用上述的形式不容易解决，但是我们可以通过引入一个变量来进行简单的操作t
min t[0] + t[1] + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
|(E[i]-S[i])-(L[i]+l[i])/2|_2<=t[i]
这个问题和上一个问题完全一样。那么我们得到了什么？
优化是将问题转换为标准形式的游戏。一旦我们有一个标准形式的问题，我们就可以站在巨人的肩膀上，使用强大的工具来解决我们的问题。
上述操作已将问题转化为二阶锥问题（SOCP）。一旦采用这种形式，几乎可以直接解决。
这样做的代码如下所示：
#!/usr/bin/env python3
import cvxpy as cp
import networkx as nx
import matplotlib.pyplot as plt
def FindTerminalPoints(springs):
starts = set([x[0] for x in springs.edges()])
ends = set([x[1] for x in springs.edges()])
return list(starts-ends), list(ends-starts)
springs = nx.DiGraph()
springs.add_edge('a', 'b', minlen= 1, maxlen= 3)
springs.add_edge('a', 'c', minlen= 1, maxlen= 4)
springs.add_edge('a', 'f', minlen=15, maxlen=15)
springs.add_edge('b', 'c', minlen= 0, maxlen= 1)
springs.add_edge('b', 'e', minlen= 9, maxlen=11)
springs.add_edge('c', 'd', minlen= 7, maxlen=11)
springs.add_edge('d', 'e', minlen= 0, maxlen= 1)
springs.add_edge('d', 'f', minlen= 3, maxlen= 6)
springs.add_edge('e', 'f', minlen= 3, maxlen= 5)
if not nx.is_directed_acyclic_graph(springs):
raise Exception("Springs must be a directed acyclic graph!")
starts, ends = FindTerminalPoints(springs)
if len(starts)!=1:
raise Exception("One unique start is needed!")
if len(ends)!=1:
raise Exception("One unique end is needed!")
start = starts[0]
end = ends[0]
#At this point we have what is essentially a directed acyclic graph beginning at
#`start` and ending at `end`
#Generate a variable for the position of each blue bar
bluevars = {n: cp.Variable(name=n) for n in springs.nodes()}
dvars = {e: cp.Variable() for e in springs.edges()}
#Anchor the leftmost blue bar to prevent pathological solutions
cons = [bluevars[start]==0]
for s,e in springs.edges():
print("Loading edge {0}-{1}".format(s,e))
sv = bluevars[s]
ev = bluevars[e]
edge = springs[s][e]
cons += [sv+edge['minlen']<=ev]
cons += [ev<=sv+edge['maxlen']]
cons += [cp.norm((ev-sv)-(edge['maxlen']-edge['minlen'])/2,2)<=dvars[(s,e)]]
obj = cp.Minimize(cp.sum(list(dvars.values())))
prob = cp.Problem(obj,cons)
val = prob.solve()
fig, ax = plt.subplots()
for var, val in bluevars.items():
print("{:10} = {:10}".format(var,val.value))
plt.plot([val.value,val.value],[0,3])
plt.show()
结果如下所示：
如果您想“手动调整”蓝条，您可以通过添加 weights 来修改我们构建的优化问题w[i]。
min w[0]*t[0] + w[1]*t[1] + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
|(E[i]-S[i])-(L[i]+l[i])/2|_2<=t[i]
越大w[i]，所讨论的弹簧接近其平均长度就越重要。
最小化有序蓝条之间的平方距离，受约束
使用与上述相同的策略，我们可以最小化蓝色条之间的平方距离，假设某种已知顺序。这将导致：
min t[0] + t[1] + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
|(S[i]-S[i+1])/2|_2<=t[i]
在下面的代码中，我首先找到蓝条的可行位置，然后假设这些映射到理想的顺序。用更准确的信息代替这种启发式方法将是一个好主意。
#!/usr/bin/env python3
import cvxpy as cp
import networkx as nx
import matplotlib.pyplot as plt
def FindTerminalPoints(springs):
starts = set([x[0] for x in springs.edges()])
ends = set([x[1] for x in springs.edges()])
return list(starts-ends), list(ends-starts)
springs = nx.DiGraph()
springs.add_edge('a', 'b', minlen= 1, maxlen= 3)
springs.add_edge('a', 'c', minlen= 1, maxlen= 4)
springs.add_edge('a', 'f', minlen=15, maxlen=15)
springs.add_edge('b', 'c', minlen= 0, maxlen= 1)
springs.add_edge('b', 'e', minlen= 9, maxlen=11)
springs.add_edge('c', 'd', minlen= 7, maxlen=11)
springs.add_edge('d', 'e', minlen= 0, maxlen= 1)
springs.add_edge('d', 'f', minlen= 3, maxlen= 6)
springs.add_edge('e', 'f', minlen= 3, maxlen= 5)
if not nx.is_directed_acyclic_graph(springs):
raise Exception("Springs must be a directed acyclic graph!")
starts, ends = FindTerminalPoints(springs)
if len(starts)!=1:
raise Exception("One unique start is needed!")
if len(ends)!=1:
raise Exception("One unique end is needed!")
start = starts[0]
end = ends[0]
#At this point we have what is essentially a directed acyclic graph beginning at
#`start` and ending at `end`
#Generate a variable for the position of each blue bar
bluevars = {n: cp.Variable(name=n) for n in springs.nodes()}
#Anchor the leftmost blue bar to prevent pathological solutions
cons = [bluevars[start]==0]
#Constraint each blue bar to its range
for s,e in springs.edges():
print("Loading edge {0}-{1}".format(s,e))
sv = bluevars[s]
ev = bluevars[e]
edge = springs[s][e]
cons += [sv+edge['minlen']<=ev]
cons += [ev<=sv+edge['maxlen']]
#Find feasible locations for the blue bars. This is a heuristic for getting a
#sorted order for the bars
obj = cp.Minimize(1)
prob = cp.Problem(obj,cons)
prob.solve()
#Now that we have a sorted order, we modify the objective to minimize the
#squared distance between the ordered bars
bar_locs = list(bluevars.values())
bar_locs.sort(key=lambda x: x.value)
dvars = [cp.Variable() for n in range(len(springs.nodes())-1)]
for i in range(len(bar_locs)-1):
cons += [cp.norm(bar_locs[i]-bar_locs[i+1],2)<=dvars[i]]
obj = cp.Minimize(cp.sum(dvars))
prob = cp.Problem(obj,cons)
val = prob.solve()
fig, ax = plt.subplots()
for var, val in bluevars.items():
print("{:10} = {:10}".format(var,val.value))
plt.plot([val.value,val.value],[0,3])
plt.show()
看起来像这样：
最小化所有蓝条之间的平方距离，受约束
我们还可以尝试最小化蓝条之间的所有成对平方距离。在我看来，这似乎给出了最好的结果。
min t[i,j] + ... for all i,j
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i] for all i
E[i] <= S+L[i] for all i
|(S[i]-S[j])/2|_2 <= t[i,j] for all i,j
看起来像这样：
#!/usr/bin/env python3
import cvxpy as cp
import networkx as nx
import matplotlib.pyplot as plt
import itertools
def FindTerminalPoints(springs):
starts = set([x[0] for x in springs.edges()])
ends = set([x[1] for x in springs.edges()])
return list(starts-ends), list(ends-starts)
springs = nx.DiGraph()
springs.add_edge('a', 'b', minlen= 1, maxlen= 3)
springs.add_edge('a', 'c', minlen= 1, maxlen= 4)
springs.add_edge('a', 'f', minlen=15, maxlen=15)
springs.add_edge('b', 'c', minlen= 0, maxlen= 1)
springs.add_edge('b', 'e', minlen= 9, maxlen=11)
springs.add_edge('c', 'd', minlen= 7, maxlen=11)
springs.add_edge('d', 'e', minlen= 0, maxlen= 1)
springs.add_edge('d', 'f', minlen= 3, maxlen= 6)
springs.add_edge('e', 'f', minlen= 3, maxlen= 5)
if not nx.is_directed_acyclic_graph(springs):
raise Exception("Springs must be a directed acyclic graph!")
starts, ends = FindTerminalPoints(springs)
if len(starts)!=1:
raise Exception("One unique start is needed!")
if len(ends)!=1:
raise Exception("One unique end is needed!")
start = starts[0]
end = ends[0]
#At this point we have what is essentially a directed acyclic graph beginning at
#`start` and ending at `end`
#Generate a variable for the position of each blue bar
bluevars = {n: cp.Variable(name=n) for n in springs.nodes()}
#Anchor the leftmost blue bar to prevent pathological solutions
cons = [bluevars[start]==0]
#Constraint each blue bar to its range
for s,e in springs.edges():
print("Loading edge {0}-{1}".format(s,e))
sv = bluevars[s]
ev = bluevars[e]
edge = springs[s][e]
cons += [sv+edge['minlen']<=ev]
cons += [ev<=sv+edge['maxlen']]
dist_combos = list(itertools.combinations(springs.nodes(), 2))
dvars = {(na,nb):cp.Variable() for na,nb in dist_combos}
distcons = []
for na,nb in dist_combos:
distcons += [cp.norm(bluevars[na]-bluevars[nb],2)<=dvars[(na,nb)]]
cons += distcons
#Find feasible locations for the blue bars. This is a heuristic for getting a
#sorted order for the bars
obj = cp.Minimize(cp.sum(list(dvars.values())))
prob = cp.Problem(obj,cons)
val = prob.solve()
fig, ax = plt.subplots()
for var, val in bluevars.items():
print("{:10} = {:10}".format(var,val.value))
plt.plot([val.value,val.value],[0,3])
plt.show()
看起来像这样：
灰线可以拉伸和收缩由它们顶部的范围给出的量。蓝线只是端点，显示灰线如何相互作用。