-1

前縁は子以外の子孫につながります

  • 頂点が別の頂点につながる場合、定義上、2番目の頂点は最初の頂点の子です。したがって、頂点はどのようにして非子につながることができますか？定義上、頂点の子はそれによって導かれるものです。

クロスエッジは祖先にも子孫にもつながりません

  • 頂点が別の頂点につながる場合、2番目の頂点が最初の頂点の子になります。したがって、定義上、頂点が導くものがその子である場合、クロスエッジはどのようにして非子孫につながることができますか？

  • ソースはどのように選択されますか？DFSアルゴリズムは、どこから開始するかをどのように認識しますか？

  • エッジのタイプは、アルゴリズムが開始する場所によって異なりますか？たとえば、アルゴリズムが頂点Aで開始し、頂点Zで終了する場合、ZからAへのエッジはバックエッジになります。ただし、アルゴリズムがZで開始し、Aで終了した場合、それはフォワードエッジになります。私の推論は正しいですか？エッジのタイプは実行ごとに変わりますか？

4

1 に答える 1

2

頂点が別の頂点につながる場合、定義上、2番目の頂点は最初の頂点の子です。

いいえ; ここでの「子」とは、検索スペースを表すツリーを指し、検索の順序を示すためにその上に「重ねられた」グラフではありません。ウィキペディアの役立つイラストを参照してください。

他の質問についても同様の混乱があります。

ソースは問題を反映するように選択されます。許容できる解決策に到達するまで続きます。

あなたがバスルームからあなたの寝室に行く方法を見ようとしているとしましょう。あなたのスタートノードはバスルームでなければなりません-あなたが実際に失われた場所です。あなたは家の中を歩き回り、バックアップして他のドアを試し、寝室（解決策）を見つけたら立ち止まります。2つのグラフがあります。1つは検索ツリーです。もう1つは、検索順序の線形パスです。問題のあるスペース自体を含めると、実際には3つになります。

双方向のエッジを意味する問題空間<>（ほとんどの人の家のすべてのドアは、どちらの方向にも人を入れることができます）：

            BATHROOM
              <> 
ENTRANCE <> HALLWAY  <>  DINING ROOM
              <>
            STAIRWAY <>  KIDS ROOM
              <>
            BEDROOM

検索グラフ-ツリー（->母娘の関係を意味します。ツリーでは、通常、一方向と見なされます）

Bathroom -> Hallway -> Entrance
                    -> Stairway -> Kids Room
                                -> Bedroom                            
                    -> Dining Room

検索順序-ツリーをどのようにトラバースするかを示す線形グラフ。

Bathroom -> Hallway -> Entrance -> Stairway -> Kids Room -> Bedroom

BFSでは、同じグラフが与えられると、次のようになります。

Bathroom -> Hallway -> Entrance -> Stairway -> Dining Room -> Kids Room -> Bedroom

開始ノードは、「私はトイレにいます」という問題によって設定されます。目標ノードは、「寝室に行きたい」という問題によっても設定されます。

別の問題：「私はオセロの特定の位置にいます。（開始）勝ちたいです。（目標）」

廊下で迷子になった場合でも、DFSを使用できることにも注意してください。グラフをツリーに変換し、最初から離れる方向にエッジを修正します。

Hallway -> Entrance
        -> Dining Room
        -> Stairway -> Kids Room
                    -> Bedroom
        -> Bathroom
于 2012-06-17T19:39:10.787 に答える