0

我正在编写一个网络爬虫，我需要找到两个 URL 之间的最小距离。

我用哈希表示网络。每个不在网络末端的节点都被键入到它所连接的节点的向量：

hash = {:v0 => [:v1,  :v2,  :v3],
        :v1 => [:v4,  :v5,  :v6], 
        :v2 => [:v7,  :v8,  :v9],
        :v3 => [:v10, :v11, :v12],
        :v4 => [:v13, :v14, :v15]}

此解决方案不起作用。问题是我只在找到目标时增加距离（dist 变量），所以结果总是1：

def path src, target, hash, dist
    return -1 if hash[src] == nil # invalid distance if source is invalid
    return dist += 1 if hash[src].include? target

    arr = Array.new
    for i in hash[src] do
        arr.push path(i, target, hash, dist) 
    end
    arr = arr.delete_if {|x| x < 0} # delete invalid values
    return -1 if arr.empty?
    return arr.min # return the shortest distance
end

我该如何修复它，使其在网络的每一层都增加？

4

2 回答 2

1

我修好了它。这是代码，如果它对某人有帮助。

def distance src, target, hash
    return 0 if src == target
    return nil if hash[src].nil?
    dist = 1

    if hash[src].include? target
        return dist
    else
        arr = hash[src].map {|x| distance x, target, hash}
    end
    arr = arr.delete_if {|x| x.nil?}

    return dist + arr.min if !arr.empty?
    return nil
end
于 2013-02-12T10:15:27.260 回答
1

看来您还没有完全理解递归的概念。为此，首先写下您的“路径距离”的定义。我引用的原因是我希望你要么想要距离，要么想要路径（路径的长度就是距离），但我真的不知道你需要什么。

现在，重要的原因是，在这种情况下，它可能类似于“路径是从当前 URL 到目标 URL 的最短距离”。实现类似于“如果目标 URL 是直接邻居，则距离为 1，否则它是与任何邻居的最短距离加 1”。在您的情况下，您通过现有距离，这并不是真正的错误，而是不寻常的。接下来，如果您在 中找到 URL hash[src]，则增加该距离（是 Ruby 传递引用，顺便说一句？）并返回它。那时，我实际上希望您返回 1，因为这是当前位置和目标之间的距离。同样，稍后，您可能还需要dist在将其传递给递归调用之前递增。

现在，有一个完全不同的问题，那就是您的算法效率低下，以至于它在使用多个 URL 时将变得无用。让我们假设 URL 像“A - X - T”一样连接，X 是开始，T 是目标。如果你不走运，你会先下到 A，这可能是由数千个 URL 组成的云。在遍历整个图之后，它们中的每一个都将找到通往 T 的路径。看看广度优先搜索 (BFS) 和深度优先搜索 (DFS) 之间的区别，这将为您提供如何修复它的提示。

还有两件事：

  • 考虑 A 和 A 之间的路径。我会说它们的距离为零，这是您的函数应该处理的。然后距离变为：如果 S=T，则距离为零，否则为一加到任何邻居的最短距离。
  • 我会尽量避免使用 -1 表示“未找到”。我宁愿什么都不返回（nil？），因为这样你就不太可能不小心对其进行任何算术运算。
于 2013-02-12T05:28:31.130 回答