0

Webクローラーを作成していますが、2つのURL間の最小距離を見つける必要があります。

ネットをハッシュで表現しています。ネットの端にないすべてのノードは、接続されているノードのベクトルにキー設定されます。

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

このソリューションは機能していません。問題は、ターゲットが見つかったときにのみ距離（距離変数）をインクリメントすることです。そのため、結果は常に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）の違いを見てください。これにより、修正方法のヒントが得られます。

さらに2つのこと：

  • AとAの間のパスを考えてみましょう。これらの距離はゼロであり、関数が処理する必要があります。その場合、距離は次のようになります。S= Tの場合、距離はゼロです。それ以外の場合は、1に隣接するものまでの最短距離を加えたものになります。
  • 「見つかりません」に-1を使用しないようにします。何も返さない（nil？）ので、誤って算術演算を実行する可能性が低くなります。
于 2013-02-12T05:28:31.130 に答える