带权重限制的图搜索

Question

我有一个无向加权图，其中任意类型的对象作为节点。两个节点 A 和 B 之间的边的权重是这两个节点在区间 (0, 1] 中的相似度。相似度为 0 导致节点之间没有连接，因此可以对图进行划分。

给定一个目标权重w 和起始节点 S，这是一种查找权重大于 w 的所有节点的算法。子节点（从 S 中看到）应该具有路径上所有权重的乘积，即：

S --(0.9)-- N1 --(0.9)-- N2 --(0.6) -- N3

从 S 开始，节点将具有 w 和起始节点 S。以下相似值：

N1: 0.9 
N2: 0.9 * 0.9 = 0.81
N3: 0.9 * 0.9 * 0.6 = 0.486

所以给定 S目标权重为 0.5，搜索应返回 N1 和 N3。从 N2 开始的搜索将返回 S、N1 和 N3。

他们有适合我的需求的算法吗？

Answer 1

请注意以下几点：

1. log(p1 * p2) = log(p1) + log(p2)
2. 如果 p1 p2 ，然后 log(p1) log(p2) 因此：-log(p1) > -log(p2)

主张【基于上面提到的1,2】：找到从s到t最相似的路线，实际上就是找到从s到t的最小路径，其中权重为-log原始的。

我建议使用以下算法，基于 Dijkstra 算法 和上述声明。

1. define for each edge e: w'(e) = -log(w(e)) //well defined because w(e) > 0
2. run Dijkstra's algorithm on the graph with the modified weights.
3. return all vertices v that their weight is dijkstra(v) < -log(needed)

Answer 2

您可以尝试使用贝尔曼-福特算法，因为它可以很好地处理边的求和和乘法，以及最小值和最大值（您可以通过执行反转操作来计算最长路径 - 使用最大值）。

另外，如果对所有路径取对数，问题就会从乘法简化为求和。之后，您可以反转权重的符号（将问题从寻找最小值转变为寻找最大值），并在该图上使用贝尔曼-福特算法。由于所有权重最初都在 0 和 1 之间，因此在这两个转换之后，您应该也能够使用 Dijkstra。

然后在计算路径后，只需恢复转换并检查哪些“距离”适合您。