如何将不满足三角形不等式的图转换为满足三角形不等式的图？

文章/答案/技术大牛

发布

1回答

algorithm、math

我有一个图G=(V，E)，它不满足三角形不等式，我想解决TSP问题。然后我有一个算法来解决这个问题，需要满足三角形不等式。 如何将不满足三角形不等式的图转换为满足三角形不等式的图？

浏览 10提问于2018-02-01得票数 0

1回答

非平面图中是否存在最小生成树？

algorithm、graph、graph-algorithm、prims-algorithm

我读过prim算法和三角形不等式，但我的图不满足三角形不等式？

浏览 1提问于2013-06-10得票数 1

回答已采纳

2回答

确保图的边满足三角形不等式

algorithm、graph

我正在生成边被分配了随机权重的图。如何保证边的权重服从三角形不等式？我看到了一个类似的问题，已经被问到了，但我不能真正理解答案

浏览 7提问于2020-03-26得票数 0

1回答

具有多次访问的TSP

algorithm、graph-theory

你能为下面的问题提出可能的方法吗:通过图的顶点找到一条路径，这样两个顶点i之间的距离(边的权重之和)不会超过Di。它显然是无限的，所以我想为这条路径生成一个生成器。

浏览 0提问于2012-08-06得票数 0

1回答

最小化图中的最大距离

algorithm、graph、nodes、graph-theory、edge-list

假设我们有一个加权的无向图。假设图中有N个节点(城市)，我们希望在城市中构建M (M<=N)个医院。现在我们需要选择最优的解决方案，这样从一个城市到一个有医院的城市的最大距离将被最小化。显然，最好的解决方案是在3号城市建立一家医院，因为这样最大距离将是83。我的想法是使用弗洛伊德-沃肖尔算法，然后在距离数组中具有最小最大值的城市中建立一家医院。然后更新另一个数组b，使b1显示从城市1到有医院的城市的最小距离，

浏览 3提问于2015-04-11得票数 4

1回答

我们能用空间填充曲线求解最短路径吗？

shortest-path、space-filling-curve

我想知道我们是否可以用空间填充曲线来解决最短路径，或者是否有更好的解决方案？与精确求解器相比，近似值有多好？图不需要满足三角形不等式。

浏览 2提问于2013-06-14得票数 1

回答已采纳

1回答

带权重参数的空间数据库索引

mysql、database、geospatial

在大型数据集的情况下，MySQL不是一个选项，因为它将创建大型表格。那么，有没有这样的数据库可供公众使用呢？

浏览 0提问于2011-12-17得票数 0

2回答

tf的余弦相似选择(三角形不等式)

nlp、cluster-analysis、information-retrieval、tf-idf、cosine-similarity

我的系统的主要缺点之一是它使用余弦相似性来决定哪些向量应该聚在一起。满足

浏览 5提问于2017-04-10得票数 2

1回答

如果我捷径一个最优的TSP解，是否仍然是最优的？

algorithm、graph、traveling-salesman

让我们有一个有k个节点的完全无向度量图；度量图是一个满足三角形不等式的图，所以对于所有节点a，b，c，w(a，c)都是权函数，所以w(a，c)确实小于或等于w(a，b) + w(b，c)。Wlog假设循环：<1，2，3，…，k，1>是该图的最佳TSP解。我的问题是:如果我从图中删除一个节点(例如，n)，并且我缩短了周期，那么只要跳过n，得到的循环仍然是一个最优

浏览 3提问于2014-04-10得票数 5

回答已采纳

2回答

TSP变种，可能的算法？

algorithm、graph、traveling-salesman、approximation、np-hard

经典的旅行商问题(TSP)定义之一是：在我的例子中，我不需要哈密顿路径，我需要两个已知顶点之间的路径。因此，公式将是：给定一个加权完全无向图，其中三角形不等式成立，两个称为源和目的地的特殊顶点返回一条最小加权路径，该路径恰好访问所有节点一次，从源开始，结束于目的地。我记得哈密顿路径是无向图中的一条路径

浏览 4提问于2013-03-08得票数 0

2回答

三角不等式对kmeans来说是必要的吗？

machine-learning、cluster-analysis、distance、data-mining、k-means

我想知道kmeans中使用的距离度量是否有必要使用三角形不等式。

浏览 0提问于2012-07-17得票数 4

回答已采纳

2回答

在一定范围内的解数，使得两个(较小的)数之和大于第三个(最大)。

python、python-3.x

我必须在一定范围(x，y)内找到满足三角形不等式的解的数目。X和y只是整数，(0 <x <y <10,000)对这个例子的解释：2 3 42 4 5三角形不等式对于除一个(2, 3 ,5)以外的所有组合都是真的，所以正确的答案是3。我刚刚找到了一种方法来计算牛顿符号的所有组合

浏览 7提问于2022-01-10得票数 0

回答已采纳

1回答

浮点计算与三角形不等式

floating-point、distance、trigonometry、nearest-neighbor

VPTree要求距离函数满足。三角形不等式指出，下列情况必须是正确的：我们的距离函数的一个特点是地理距离，以米为单位，用浮点算法计算。我发现，由于浮点计算不精确，这个特性一直在违反三角形不等式。我到处乱搞，发现如果我把距离以米为单位转到下一个整数，即java中的Math.floor()，然后添加5，结果似乎在所有我测试过的</

浏览 3提问于2014-01-30得票数 2

回答已采纳

1回答

如何利用计算几何技术处理不准确的地图坐标

computational-geometry、convex-hull、voronoi、delaunay

我在后端实现了节约算法，这有助于确定进行一系列交付的最佳路线。我遇到的问题是，在地图上点击的地方返回的一些坐标是错误的。假设我要在两个不同的地方送货。这两个位置的坐标，再加上我从哪里开始，当我完成时返回，应该形成一个三角形。有时返回的坐标可能是非常错误的，以致于违反了三角形不等式定理。我一直在阅读Skiena的算法设计手册，我想知道，给定错误的

浏览 0提问于2018-02-12得票数 0

回答已采纳

1回答

简单2D自上而下车辆碰撞物理的算法？

c++、algorithm

我正在尝试创建一个简化的GTA 2克隆来学习。我研究的是车辆碰撞/物理学。我想说的基本思想是，将由车辆A的位置和速度确定的力F施加到车辆B上的点P上，但这到底应该做什么呢？我的车辆有一个中心位置和一个角度，但我不确定像应用力这样的东西应该做什么。在撞击后，我如何确定车辆的新中心和角度？谢谢

浏览 0提问于2012-10-07得票数 0

回答已采纳

1回答

比较图之间的相似性？

cluster-analysis、similarity、directed-graph

我有多个，表示为有向图。我已经使用来比较两个概念图，但是现在我想将相似的图分类/聚类在一起。 AFAIK，传统的聚类算法以输入为多维数据点.但我也读到，很难，而且不建议将一个图转换成一个向量。

浏览 3提问于2016-06-14得票数 0

2回答

Levenshtein距离与三角不等式

string、algorithm、levenshtein-distance

我对Levenshtein距离和三角不等式感到困惑。维基百科和其他文章说，Levenshtein距离遵循三角形不等式。三角不等式表示x+y>z，但对于Levenshtein距离，在我看来，x+y可以等于z。编辑三角不等式不是在核空间，而是度量空间。在度量空间中，三角形不等式是d(x,z)<= d(x,y)+d(y,z)。

浏览 4提问于2013-09-20得票数 4

回答已采纳

2回答

我们将如何找到三角形内的点数？

java

如果给定二维笛卡尔平面上所有三个顶点的x和y坐标，则可以得到三角形内部和边界上的点的坐标。我正在考虑将三角形包围在一个矩形内，然后找出直线方程，并逐个检查这些点，以满足不等式方程。有没有更好的计算方法来解决这个问题？请帮帮我。

浏览 1提问于2012-08-16得票数 0

1回答

球树与伪计量学

scikit-learn、k-nn、metric

文档 for sklearn.neighbors.DistanceMetric声明(即非负，仅当对象相等、对称且满足三角形不等式时为0)。我的问题是，这些要求有多严格？更具体地说，圆球树是否适用于伪测量(对于不相等的对象可以是0，但满足其他条件)？

浏览 0提问于2019-08-15得票数 1

回答已采纳

1回答

曼哈顿距离与三角不等式

algorithm、geometry、distance

问题陈述如下：给定的距离应满足：原因是:首先对距离进行排序，这样那么我们有以下几个方面|x3-x2|+|y3c-a)/2a+b>=c should hold (Triangle inequality over Manhattan Distance)

浏览 2提问于2017-10-05得票数 1

点击加载更多