問題タブ [graph-traversal]

現在、接続のリストがリストに保存されています。各接続は、2 つのポイントを接続する有向リンクであり、ポイントが複数のポイントにリンクしたり、複数のポイントにリンクされたりすることはありません。例えば：

生成する必要があります:

入力ポイントと接続のリストを受け取り、それ自体を再帰的に呼び出して次のポイントを見つけ、それを成長する順序付きリストに追加するアルゴリズムを使用してこれを実行しようとしました。ただし、正しいポイントから開始しないと (これは同じアルゴリズムを逆に繰り返すだけの問題である必要があります)、接続されていないストランドが複数ある場合にも、私のアルゴリズムは機能しなくなります。

これらの接続を順序付けるための効率的なアルゴリズムを作成する最良の方法は何でしょうか?

有向グラフに「and」および「or」および「not」ゲートの束を作成したいと思います。次に、入力からトラバースして、結果が何であるかを確認します。

それを行う既製のトラバーサルがあると思いますが、表示されません。そのようなトラバーサルの名前が何であるかはわかりません。

確かに幅優先ではうまくいきません。私はすべての葉を手に入れ、根に向かって上る必要があります. 言い換えると

A = (B & (C & Z))

最初に C @ Z を解決する必要があります。

このタイプのものをグラフに入れて上にトラバースする必要があります。

特にHadoopによって実装されたMapReduceフレームワークについてまだ学んでおり、次のタスクを実行するように変更できるかどうか疑問に思っています:

Map() 関数は、キーがサイズ 2 の配列、たとえば int[2] である (key,value) ペアを出力します。共通の 2 つの整数のいずれかを含むすべてのペアを同じレデューサーにマップしたいと思います。

たとえば、Map() が ([2,3],4),([2,4],5),([6,5],2),([5,7],1),次に、Reduce1 は最初の 2 つのペアを受け取り、Reduce2 は次の 2 つのペアを受け取る必要があります (最初の 2 つは 2 を共有し、2 番目の 2 つは 5 を共有します)。これは、頂点が int[] 内の整数であり、エッジが同じ int[] 内の任意の 2 つの整数間で共有される連結成分の問題と見なすことができます。

私はこの問題を解決する方法を見つけようとしています..これは、12 年生の生徒を対象に開催されたプログラミング競技会から取られています。タスクは、学生「Karli」に 214 単位を取得するのに十分なクラスを受講させることです。学生は、試験室に入る前に 214 単位以上または以下を取ることはできません。ドアは図に示されています。ユーザーは追加のクラスのためにクラスを繰り返すことができますが、その教室を離れて別の教室に移動し、戻ってくる必要があります。

これを手動で実行しようとしたところ、パスで 1 つの解決策を見つけることができました。

数学-代数-哲学-代数-数学-モデリング-微積分-モデリング-試験

必要なクレジット数 (この場合は 214) を指定してパスを見つけるアルゴリズムを開発しようとしています。

これが私が試して行き詰まったものです：

ドアが 2 つのノード間の二重エッジであるグラフとしてマップを表します。しかし、どのグラフ走査アルゴリズムでこの問題を解決できるかわかりません。

グラフを隣接行列に変換すると、物事が簡単になりますか?

ありがとう