1

英語を母国語としない人 (ロシア) として、ウィキペディアでこの記事を読みました: http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search

そして、私はハードコアな英語で書かれたこの疑似コードの例に従い、説明やコメントをほとんど付けないようにしています。

特に、私は彼らがこの文で何を言おうとしているのか理解できません:

DFS(u):

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

u に隣接するすべてのノード v に対して

この文の私の問題は、「隣接」部分です。私の辞書によると、これは「隣人」のようなものを意味します。では、u のスーパーノードのサブノードを反復処理する必要がありますか? u はグラフのノードであることに注意してください。

それとも、u のすべてのサブノードを反復処理しなければならないと言いたいのでしょうか? これは大きな違いになるからです。

これらの英語の問題に加えて、彼らはdとpが何を意味するのかを言及するのを忘れていました。

記事内のリンクは、このあまり意味のない不可解なことを繰り返しているだけです。たぶん、誰かが実際にこれを、より多くのコメントと意味のある変数を使って、より人間が読める方法で書き直すことができたでしょうか? DFSに関連するライターの支配的な知性を誇示するためだけにあるのではない、本当に良い説明は見つかりませんでした.

したがって、誰かがその場でそれをより良い方法で書き直し、学習価値を高めて私の一日を救うことができれば、私の口ひげを救います. すべてを保存します。ありがとうございました。

4

3 に答える 3

2

これは、「u に直接接続されたすべてのノード v に対して」という意味です。

http://en.wikipedia.org/wiki/Depth-first_searchの疑似コードは、はるかに単純です。これがあなたにとってよりうまくいくことを願っています。

私の記憶が正しければd、pとfは Cormen のアルゴリズムに関する本から来ています。これらは、(それぞれ) ノードが検出された瞬間、DFS トラバーサル ツリー上の前のノード、およびノー​​ドが終了した瞬間を意味します。それらのいくつかは、一部のアプリケーション (トポロジーの並べ替え、コンポーネントの検索、DFS に関するその他のアルゴリズムなど) に役立ちますが、DFS 自体にとって重要ではありません。

于 2011-04-26T09:59:43.060 に答える
2

同様の質問からの私のコードはあなたに役立つかもしれません:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

dfs(t)
于 2011-04-26T14:42:58.257 に答える
1

言葉の壁があなたの側にあれば、私は少し非難されることはありません.

とにかく、「隣接」とは、直接接続されていることを意味します。このグラフでは:

    A   E
   / \ /
  B   C
       \
        D

Aは に隣接しB、は に隣接しC、は に隣接し、は に隣接し、はに隣接し、はに隣接しています。BACAEDDCEC

これは同じコードですが、もう少し冗長です。

{with the following global variable:
    time, which is a single integer, and initially 0;}

{and a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;
    previous-node;
    discovery-time;
    finishing-time;}

{depth-first-search of node u is:
    visit the value of u;
    increase time by 1;
    set the discovery-time of u to time;
    set the colour of u to grey;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            set the previous-node of v to u;
            depth-first-search of v;}}

    increase time by 1;
    set the finishing-time of u to time;
    set the colour of u to black;}

このコードには、純粋に説明を目的としたものがいくつかあります。中心的なテーマは次のとおりです。

{with a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;}

{depth-first-search of node u is:
    visit the value of u;
    set the colour of u to black;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            depth-first-search of v;}}}
于 2011-04-26T12:02:30.177 に答える