生成满足三角不等式的图形。

Question

生成满足三角不等式的图形。

4

我希望生成一组较大（~10,000-50,000）的完整加权图G =（V，E），其中边缘满足尖锐三角形不等式 - 因此对于每个v，u，w from V ： weight（vu）+ weight（uw） > weight（vw）; 权重是正整数。编辑顶点是 N 维欧几里得空间中的点，每条边缘uv的权重必须大于或等于u和v之间的欧几里得距离（因此，如果距离为2.753，则最小允许的权重为3，但它可以是4、5等等）。

截至目前，我提出了两种朴素方法。这两种方法都基于在 N 维欧几里得空间中随机生成点的思想。

一些符号表示：

vu或vertex1-vertex2表示一条边缘
E(v,u) - v和u之间的欧几里得距离
对于双倍/实数r，ceil(r)是一个整数n，使得n-1<r≤n（例如，ceil(10.5)=11，ceil(0.000000000001)=1，ceil(172)=172）。
（vu，c） - 边缘vu的权重为c

方法1-本地

vertices = {v,u} -- v, u generated randomly
edges = {vu} 
weights = {(vu,ceil(E(v,u))} 
i = 0
while(i < total_number_of_vertices)
    candidate = generate_new_point()
    ok = true
    foreach (vertex in vertices):
        integer_distance = ceil(E(candidate,vertex))
        if adding (candidate-vertex, integer_distance) to weights
           violates the triangle inequality:
               ok = false \\ this candidate is wrong
               break \\ breaking for-each; start with new candidate
        end_if
    end_for_each
    if(ok)
         i++
         add candidate to vertices, 
         for_each vertex in vertices:
             add vertex-candidate to  edges
             add (vertex-candidate, ceil(E(candidate,vertex))) to weights
         end_for_each          
     end_if
end_while

方法二 -- 全局变量

vertices = generate_points(total_number_of_vertices)
edges = complete Graph induced by vertices
weights = {}
for_each edge uv:
    add (uv, ceil(E(u,v))) to weights
end_for_each
all_good = false
while (!all_good):
    all_good = true
    for_each edge in edges:
         \\ this one has to be check in all triangles that edge belongs to
         if edge violates triangle inequality:
             \\ by appropriate I mean directly involved
             update appropriate weights to satisfy triangle inequality
             all_good = false \\ 'updating one edge may disturb other'
         end_if
    end_for_each
end_while

我非常怀疑这些方法是否足够高效，因此如果有任何帮助——改进它们或建议完全不同的方法——将不胜感激。

如果上面的内容有什么不清楚的地方，我会提供更多信息。

如果发现将权重保持为正的整数太困难，我可以考虑将它们作为正的双精度浮点数，但在这种情况下，浮点精度可能成为一个需要解决的问题[因为我确实需要具有尖锐三角不等式]。

- artur grzesiak

1

为什么不给所有的边赋相同的权重呢？ - Alex Reinking

1

有点困惑于您的限制条件“对于每个V中的v、u、w：weight（vu）+ weight（uw）> weight（vw）”...如果我们简单地将weight（xy）== distance（x，y）称为，则您能画出一个不符合所需属性的非退化三角形吗？我不确定这样的三角形是否存在，除了当weight（vu）+ weight（uw）== weight（vw）（即一个顶点在另外两个顶点所定义的直线上）的退化情况。 - twalberg

@twalberg 问题在于，一般情况下距离是实数/双精度，而我希望权重为整数。 - artur grzesiak

@Inwvr 我编辑了我的帖子。假设顶点实际上是N维欧几里得空间中的点。 - artur grzesiak

向上取整(E(u,v)) + 1 不够吗？ - Ante

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam · Accepted Answer

我将提出另一种天真的方法，尽管它是O（E）级别的。选择一个范围R=[A,B)，其中2A > B。这意味着如果权重在R中，则三角不等式保证成立。

例如，B=100。因此A=B/2=50。对于每条边，在50到99之间选择一个随机数。

通过将随机数添加到欧几里得距离中，您可以满足欧几里得空间要求。