algorithm - 修改距离以违反三角不等式

Question

我想验证一个猜想，说某个算法的性能取决于 c 违反三角不等式的程度，其中 c 是距离算法正在求解的实例的矩阵。

我的问题是，什么是修改距离矩阵 c 的好方法，以便我可以控制它违反三角不等式的程度？

到目前为止我想出的最好的是这样的:对于参数 p 和 q，随机选择 p% c 的元素，并且对于每个选择的元素，将其乘以 1+u，其中 u 从 [0, 中统一选择q].

我想我们可以做得更好。有什么想法吗？

Answer 1

我会运行一些测试。对于每个测试，我都会生成两个矩阵。一个完全随机但对称的。这几乎肯定会违反三角不等式。另一个距离矩阵基于计算n维空间中随机点之间的距离，因此服从三角不等式。现在使用这两个的加权平均值，使用各种不同的权重。用不同的基础矩阵重复。

只是添加评论中没有的内容我会注意到，如果您考虑任何三重点，您可以计算出该三角形违反三角形不等式的权重(如果有的话)，因为您只是检查三个不等式其中值是线性的加上权重中的常数。考虑到所有的三元组都不是很好，因为这是 O(n^3) 的点数，但是矩阵有 O(n^2) 个元素，所以你总是可以声明它只有 O(n^1.5)输入数据量。