我将介绍一些理论知识,然后提供一些符合1-4和6的JavaScript代码,以及经过修改的版本5和以下两点:
- 能够应对数值问题
- 没有外部依赖
我们可以将1-4表示为线性规划。例如,您的样例实例将被转换为:
minimize x4 - x1
subject to
(known minimum distances)
a: x3 - x1 >= 200
b: x4 - x1 >= 900
(fixed order)
c: x2 - x1 >= 0
d: x3 - x2 >= 0
e: x4 - x3 >= 0
x1, x2, x3, x4 unbounded
每个线性规划问题都有一个对偶问题,其最优目标值相同(在这里满足一定条件)。上述问题的对偶问题如下:
maximize 200 a + 900 b
subject to
x1: -a - b - c = -1
x2: c - d = 0
x3: a + d - e = 0
x4: b + e = 1
a, b, c, d, e >= 0
这是一个没有容量限制的最大费用流问题。因此,某些路径是最优流,所以我们可以将标准1-4理解为最长路径问题。
一旦我们有了最优目标,这里是900,我们可以将标准4转换为约束条件。
x4 - x1 <= 900
思考如何制作最令人愉悦的布局。按照所写,我们可以通过解决二次规划问题来实现标准5:
minimize (x2 - x1)**2 + (x3 - x2)**2 + (x4 - x3)**2
subject to
(most efficient layout)
x4 - x1 <= 900
(known minimum distances)
x3 - x1 >= 200
x4 - x1 >= 900
(fixed order)
x2 - x1 >= 0
x3 - x2 >= 0
x4 - x3 >= 0
x1, x2, x3, x4 unbounded
我写的目标不是标准差,但这并不重要。最小化标准差等价于最小化方差。反过来,随机变量 X 的方差是 E[X**2] - E[X]**2,而 E[X]**2 在此处是一个常数 (例如,在本例中 E[X]=900/4=150)。最后,最大化 E[X**2] 等价于最大化等可能结果的平方和。
然而,我提出了一个不同的标准。
5′. 按照字典顺序最大化(从小到大排序)间隙长度列表。
这意味着我们尽可能地避免小间隙。在 Roman Svistunov 给出的示例中,假设我们有如下约束条件:
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8
标准差最小的解决方案集
x1 = 0
x2 = 0.75
x3 = 2
x4 = 6.25
x5 = 10
与优化替换目标的解决方案相比
x1 = 0
x2 = 1
x3 = 2
x4 = 6.5
x5 = 10
我们已经将
x2
更加居中,代价是让
x4
不太居中。由于
x2
比
x4
更靠近其邻居,因此我认为这是一个合理的权衡,但最终还是由您决定。
要优化5',我们按如下步骤进行。首先制定一个线性规划问题,如下所示:
maximize z
subject to
(most efficient layout)
x5 - x1 <= 10
(known minimum distances)
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8
(fixed order)
x2 - x1 >= z
x3 - x2 >= z
x4 - x3 >= z
x5 - x4 >= z
x1, x2, x3, x4, x5 unbounded
在这里,我们解决最优情况,即 z = 1
,并记录哪些差距阻止了它变得更大。我们替换那些 z
变量,并再次解决,重复此过程直到没有 z
的出现。
maximize z
subject to
(most efficient layout)
x5 - x1 <= 10
(known minimum distances)
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8
(fixed order)
x2 - x1 = 1
x3 - x2 = 1
x4 - x3 >= z
x5 - x4 >= z
x1, x2, x3, x4, x5 unbounded
最优解为 z = 3.5
。
maximize z
subject to
(most efficient layout)
x5 - x1 <= 10
(known minimum distances)
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8
(fixed order)
x2 - x1 = 1
x3 - x2 = 1
x4 - x3 >= z
x5 - x4 = 3.5
x1, x2, x3, x4, x5 unbounded
最优解为z = 4.5
,并且这是最后一次迭代。
正如前面所观察到的,我们可以使用扩展的最长路径算法来解决这些线性规划问题。在JavaScript中:
function Dual(p, v) {
return { position: p, velocity: v };
}
function dualPlus(x, y) {
return Dual(x.position + y.position, x.velocity + y.velocity);
}
const epsilon = Math.sqrt(Number.EPSILON);
function dualLessThan(x, y) {
let d = x.position - y.position;
return d < -epsilon || (Math.abs(d) <= epsilon && x.velocity < y.velocity);
}
function DeltaTracker() {
return {
delta: Infinity,
dualLessThan: function (x, y) {
let lessThan = dualLessThan(x, y);
if (lessThan) {
[x, y] = [y, x];
}
if (x.velocity < y.velocity) {
this.delta = Math.min(
this.delta,
(x.position - y.position) / (y.velocity - x.velocity)
);
}
return lessThan;
},
};
}
function graphFromMatrix(n, matrix) {
let graph = [];
for (let j = 0; j < n; j++) {
graph.push([]);
for (let i = 0; i < j; i++) {
if (matrix[i][j] > 0) {
graph[j].push({ i: i, length: Dual(matrix[i][j], 0) });
}
}
}
return graph;
}
function longestPathTable(graph, gaps) {
let tracker = DeltaTracker();
let maximum = Dual(0, 0);
let table = [];
for (let j = 0; j < graph.length; j++) {
let argument = null;
if (j > 0) {
maximum = dualPlus(maximum, gaps[j - 1]);
}
for (let edge of graph[j]) {
let x = dualPlus(table[edge.i].maximum, edge.length);
if (tracker.dualLessThan(maximum, x)) {
argument = edge.i;
maximum = x;
}
}
table.push({ argument: argument, maximum: maximum });
}
return [tracker.delta, table];
}
function freezeCriticalGaps(table, graph, gaps) {
let j = table.length - 1;
while (j > 0) {
let critical = true;
let argument = table[j].argument;
if (argument !== null) {
j = argument;
} else {
j--;
gaps[j].velocity = 0;
}
}
}
function advanceGaps(gaps, delta) {
for (let i = 0; i < gaps.length; i++) {
gaps[i].position += gaps[i].velocity * delta;
}
}
function positionsFromTable(table) {
let positions = [];
for (let entry of table) {
positions.push(entry.maximum.position);
}
return positions;
}
function layOut(n, matrix) {
let graph = graphFromMatrix(n, matrix);
let gaps = [];
for (let j = 1; j < n; j++) {
gaps.push(Dual(0, 1));
}
while (true) {
let [delta, table] = longestPathTable(graph, gaps);
if (delta == Infinity) {
return positionsFromTable(table);
}
if (table[n - 1].maximum.velocity > 0) {
freezeCriticalGaps(table, graph, gaps);
} else {
advanceGaps(gaps, delta);
}
}
}
console.log(
layOut(4, [
[0, 200, 0, 900],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
])
);
console.log(
layOut(5, [
[0, 0, 2, 0, 0],
[0, 0, 0, 5.5, 0],
[0, 0, 0, 0, 8],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
])
);
console.log(
layOut(4, [
[0, 0, 200, 0],
[0, 0, 0, 150],
[0, 0, 0, 0],
[0, 0, 0, 0],
])
);
console.log(
layOut(4, [
[0, 0, 200, 0],
[0, 0, 0, 200],
[0, 0, 0, 0],
[0, 0, 0, 0],
])
);
console.log(
layOut(4, [
[0, 0, 200, 0],
[0, 0, 0, 300],
[0, 0, 0, 0],
[0, 0, 0, 0],
])
);
(好要有)相邻点之间的间隙
在5中是什么意思?你想最小化最大间隙大小、平方间隙尺寸的总和还是其他函数? - kcsquaredm_d(P1, P2)
和m_d(P3, P4)
。在这种情况下,d(P1, P4)将是m_d(P1, P2) + m_d(P3, P4)
。这里没有给出m_d(P1, P4)
。如果给出了,它不一定是最终结果,因为其他间隙可能会进一步推动P4向右移动。我在问题中提出的算法可以为P1和P4之间的距离产生正确的结果。它不满足#5。 - Devs love ZenUML