3

ウィキペディアの 2 つのページ間の最短距離を見つける必要があります (「ホップ」単位)。

ページ上のすべての内部 wiki リンクを抽出する方法があります

開始目的地と最終目的地はわかっていますが、データからホップを抽出する方法がわかりません

これまでのところ、リンク抽出メソッドを使用して、キーがページ上のリンクであり、値がリンクが取得されたページである辞書を作成してきました。

誰かが情報を保持するための優れたデータ構造とは何か、そしてそれをどのように調べるかというアイデアを持っているなら、私はそれを非常に感謝しています

4

5 に答える 5

6

グラフ理論について何か知っていますか? グラフを作成するために必要なデータはありますが、ダイクストラのアルゴリズムを使用してデータを走査し、2 点間の最短経路を見つける必要があります。

于 2009-12-14T17:08:02.600 に答える
2

私は実際には C# プログラマーではないので、少しばかげているかもしれませんが、内部のすべてのリンクを含む多次元配列は、次元の深さに応じて、フープが少ない方法を知ることができます。

配列が持つことができる次元の数に言語の制限がないため、これは理論的には確かに実行可能ですが、それは本当にメモリを消費することになると確信しています!

このようなもの：

[source] -> [source link] -> ['source link' link] -> etc
         -> [source link] -> ['source link' link] -> etc
         -> [source link] -> ['source link' link] -> etc
         -> [source link] -> ['source link' link] -> [target]
         -> [source link] -> ['source link' link] -> etc
于 2009-12-14T17:12:15.040 に答える
1

あなたが持っていると仮定するとIEnumerable<Link> PageLinks(Link link)

ホップ数は、次のように解決されます。

Link curentPage = "somepage";
Link destinationPage = "otherpage";
if (currentPage == destinationPage) return 0;
int hops = 1;
IEnumerable<Link> currentLinks = PageLinks(currentPage);
IEnumerable<Link> visited = new [] {currentPage};
while(!currentLinks.Contains(destinationPage)) 
{
    currentLinks = currentLinks
        .SelectMany(l => PageLinks(l).Where(f => !visited.Contains(f)));
    visited = visited.Union(currentLinks);
    hops++;
}
return hops;

サイクリングが速くなるように編集されていますが、アルゴリズムはそれがなくても機能していました。ページがリンクされていない場合、StackOverflow まで実行される可能性があります。

于 2009-12-14T17:17:43.797 に答える
1

Python でのダイクストラのアルゴリズムの実装は次のとおりです: http://code.activestate.com/recipes/119466/

于 2009-12-14T17:24:26.823 に答える
0

この場合、グラフはまばらだと思います。そのため、ウィキペディアの各ページに HashSet のようなものを使用し、セット内にリンクするページを使用することをお勧めします。

この場合、Dijikstra の最短パス アルゴリズムを実際に実装する必要はありません。これは、各エッジの重みが 1 に等しい最短経路問題に等しいためです。幅優先検索を実行して、目的のページが見つかった深さを取得できます。

于 2009-12-14T17:18:35.713 に答える