问题标签 [graph-algorithm]

我正在寻找一种算法来在六边形（蜂窝）图上找到成对的相邻节点，以最小化成本函数。

• 每个节点连接到三个相邻节点
• 每个节点“i”都应该与一个相邻节点“j”配对。

• 每对节点定义一个成本函数

  c = pairCost(i, j)

• 然后总成本计算为

  totalCost = 1/2 sum_{i=1:N} (pairCost(i, pair(i)))

其中 pair(i) 返回与“i”配对的节点的索引。（总和除以二，因为总和计算每个节点两次）。我的问题是，如何找到最小化总成本的节点对？

链接的图像应该更清楚解决方案的外观（粗红线表示配对）：

一些进一步的说明：

• 我真的不在乎最外面的节点
• 我的成本函数类似于 || v (i) - v (j) || （与节点关联的向量之间的距离）
• 我猜这个问题可能是 NP 难的，但我真的不需要真正的最佳解决方案，一个好的解决方案就足够了。
• 朴素算法倾向于得到“锁定”的节点，即它们的所有邻居都被占用。

注意：我不熟悉该领域的常用术语（是图论吗？）。如果您能对此提供帮助，那么也许这可以让我在文献中寻找解决方案。

假设我们有一个相互连接的大型数据库图，实际上是一个巨大的分布式数据库。图上的任何节点都可以通过递归查询其邻居来查询整个数据库，这些邻居从邻居那里获取结果并将组合结果传递回查询路径。

此外，假设如果节点自己的数据库包含“足够好”的结果，则可以停止递归，这样如果附近已经有一个不错的结果，就不必查询整个网络。这使得我要说的内容具有相关性。

每次进行查询时将返回的数据传输到更接近发起查询的节点是否有意义？也就是说，被查询节点查询其邻居并获取 X，查询自身并获取 Y，将 X+Y 传递回查询它的节点，将 X 存储在其数据库中，并从其数据库中删除 Y。这不会最终导致分布式数据库在其节点之间具有相对于查询期间将咨询的平均节点数量的大致最佳数据分布吗？

这种技术有名字吗？

我有这个可以用有向无环图（DAG）来表达的技术问题。节点代表事件（时间未知），有向边编码关系：“我比你年轻/我发生在你之前”。

我需要估计边缘权重（即“动态权重”），以便加权 DAG（WDAG）暗示 DAG 上的距离函数。换句话说，节点 A 和 B 之间路径的权重总和对于所有路径应该相等。

这是一个未确定的问题，即使权重是整数（我想拓扑排序不是唯一的根本原因也是如此）。一般来说，代表节点/事件之间的时间间隔的边权重是实数。因此，我在加权 DAG 上引入了一些预设目标函数 C=J(WDAG)，此处未指定。

我的问题是：是否有一种算法可以在 WDAG 上分配正定权重，受制于 1）权重形成 DAG 的距离函数和 2）最小化目标函数成本 C。

这似乎与传统上与 WDAG 相关的最短路径或最小生成树问题无关。对上述问题的正式或启发式解决方案有什么想法吗？

问候，

斯蒂芬妮

我有一个来自 mygraph 的顶点向量，我对顶点进行拓扑排序。

对顶点“按顺序”进行拓扑排序。那么，比较 v1 和 v2 以测试我的原始顶点向量（v1）是“有序”还是“无序”的最佳方法是什么。

编辑：例如：如果向量 v1 有顶点 {A, B, C} 并且我们有边 (A,B) (C,A)

所以在拓扑排序之后，我将在 v2 中

{出租车}

在某些情况下，我可能无法获得唯一的拓扑顺序，例如，如果我有 (A,C) 作为唯一的边，那么 v2 可能以 {A , B , C} 或 {B , A , C} 结尾

现在我需要查看 v1 和 v2 以确定 v1 和 v2 是否代表相同的订单。

第二次编辑：我尝试了一种方法，它现在有效，请告诉我这是否是一个好方法。

我想知道 TSP 的问题名称是什么，不考虑返回起点的方式以及解决此问题的算法是什么。

我研究了最短路径问题，但这不是我要找的，这个问题只能从 2 个指定点找到最短路径。但我正在寻找的是我们给出 n 分并且只输入 1 个起点的问题。然后，找到通过所有点的最短路径恰好一次。（终点可以是任何点。）

我还研究了哈密顿路径问题，但它似乎没有解决我定义的问题，而是找出是否存在哈密顿路径。

我试图理解为什么 Dijkstra 的算法不适用于负权重。阅读有关Shortest Paths的示例，我试图找出以下情况：

从网站：

假设边都是从左到右的，如果我们从 A 开始，Dijkstra 的算法会选择边 (A,x) 最小化 d(A,A)+length(edge)，即 (A,B)。然后它设置 d(A,B)=2 并选择另一个边 (y,C) 最小化 d(A,y)+d(y,C)；唯一的选择是 (A,C)，它设置 d(A,C)=3。但它永远不会找到从 A 到 B、通过 C、总长度为 1 的最短路径。

我不明白为什么使用 Dijkstra 的以下实现，d[B] 不会更新为1（当算法到达顶点 C 时，它将在 B 上运行松弛，看到 d[B] 等于2，因此更新其值为1)。

谢谢，

梅尔

任何人都知道在图像上选择一个点然后保存它的代码是什么。我正在使用 Dreamweaver CS5 在伦敦地下 [Tube Map] 的图像上创建热点。但是选择这两个点的方法是什么。

由于我正在开发一个可点击界面的旅程规划器，因此我需要选择“管图”上的任意两个点，然后获得任意两个选定点之间的最短路径。类似于这样的http://www.mtr.com.hk/jplanner/flash_chi/index.php

我有 Tube Map 的信息，并在 MySQL 或 PhpMyAdmin 中创建了所有信息，我从 Wikipedia http://commons.wikimedia.org/wiki/London_Underground_geographic_maps/SQL获得了它。 有人请帮助我从哪里开始，这很令人困惑。我正在使用 Wampserver2

这是一个几乎与语言无关的问题，而不是家庭作业。理想情况下，我会使用 C# 和/或 SQL 服务器作为解决方案。

假设我有一个函数GetExchangeRate(buyCurrency, sellCurrency)。所以，如果 1 GBP 值 1.6 USD，那么GetExchangeRate('GBP', 'USD') = 1.6和GetExchangeRate('USD', 'GBP') = 0.625。

系统中的订单将表示为以下三元组：(buyCurrency, SellCurrency, buyCurrencyAmount)。因此，('GBP', 'USD', 125.00) 表示用多少美元买入 125 GBP。

我的目标是节省交易成本并取消订单，包括传递性。对同一对货币之间的买入和卖出进行净额计算很容易，也很容易证明是合理的。假设我可能有商业原因来简化订单，我用美元购买英镑，并用英镑购买欧元，等等......

我想传递地简化这组命令。我正在考虑构建一个图形数据结构（节点是货币，边是 buyCurrencyAmounts），即使数据将存储在 SQL 表中，并对此应用正确的算法。我想先做一个简单的网络，然后在 DAG 上进行拓扑排序，然后从顶部开始，然后按拓扑顺序走并“挤压”订单，例如简化它们。

问题是我不一定会有 DAG。但是，我可能会在执行算法时简化图形结构，无论是哪一种。

我应该为此使用什么正确的数据结构/算法？我应该担心由此产生的精度吗？有没有一些好的方法可以让我不损失美分？你能推荐一个可以处理这个问题的好 C# 库吗？仅使用 SQL Server 2008 尝试此操作会是疯狂/低效/太多工作吗？

编辑：为交易支付的费用都包含在价格（汇率）中。没有固定的固定费用或类似的东西。

我有一个有向图，其中有两条有向路径。

我想要一个算法来确定两条路径之间的相似性。

这篇文章提到使用Levenshtein 距离来确定近似相似度。我也意识到汉明距离使用了类似的度量。

我的问题是：

您如何处理两条路径相互平行的情况。也就是说，如果两条路径没有相似的节点，但会被认为是“相似的”，因为它们的路径以相同的方向行进，彼此非常接近。

谢谢

虽然我知道我们可以通过检测后端http://cs.wellesley.edu/~cs231/fall01/dfs.pdf来使用 DFS 算法检测周期。在遵循上述方法时，我无法弄清楚如何以有效和“干净”的方式输出循环中的节点。

将不胜感激一些帮助

谢谢