7

Nodeオブジェクトで表される巡回グラフのような構造があります。Nodeは、スカラー値 (葉) または n>=1 Nodes (内部ノード)のリストです。

循環参照が発生する可能性があるため、すべての子ノードの HashCode() を結合する再帰 HashCode() 関数を単純に使用することはできません。無限再帰になってしまいます。

HashCode() の部分は、フラグを立てて既にアクセスしたノードを無視することで少なくとも実行できるように見えますが、Equals() の機能する効率的なアルゴリズムを考えるのに苦労しています。

驚いたことに、これに関する有用な情報は見つかりませんでしたが、多くの賢明な人々がこれらの問題を解決するための良い方法を考えたことは確かです...そうですか?

例 (python):

A = [ 1, 2, None ]; A[2] = A  
B = [ 1, 2, None ]; B[2] = B

A は B と同じです。これは、まったく同じグラフを表すためです。

ところで。この質問は特定の言語を対象としているわけではありませんが、Java で説明されているNodeオブジェクトに hashCode() と equals() を実装することは、実用的な良い例です。

4

3 に答える 3

0

これをグラフと考えると、リーフノードは接続が1つしかないノードであり、複雑なノードは少なくとも2つあるノードです。そのようにして、単純なBFSアルゴリズムを実装すると、それぞれにハッシュ関数が適用されます。通過したノードを通過し、結果をドロップします。このようにして、輪に陥ったり、ノードを複数回通過したりしないようにします。

実装は非常に単純である可能性があります。ここでそれについて読んでください。

于 2010-12-27T17:49:25.263 に答える
0

グラフをたどる必要があります。

ここで質問です: これらのグラフは等しいですか?

A = [1,2,None]; A[2] = A
B = [1,2,[1,2,None]]; B[2][2] = B

その場合、(Node, Node) タプルのセットが必要です。このセットを使用してループをキャッチし、ループをキャッチすると「true」を返します。

そうでない場合は、ノードからノードへのマップを使用して、もう少し効率的にすることができます。次に、グラフをたどって、一連の対応関係を構築します。(上記の場合、A は B に対応し、A[2] は B[2] に対応します。) 次に、ノード ペアにアクセスするときに、正確なペアがマップにあることを確認します。そうでない場合、グラフは一致しません。

于 2010-12-27T17:53:27.253 に答える
0

私も良い答えが知りたいです。これまでのところ、訪問したセットに基づくソリューションを使用しています。

ハッシュを計算するとき、グラフ構造をトラバースし、訪問したノードのセットを保持します。同じノードには二度と入らない。すでに訪問したノードにヒットすると、ハッシュは再帰なしで数値を返します。

これは等価比較でも機能します。ノード データを比較し、子に対して再帰的に呼び出します。既にアクセスしたノードにヒットすると、比較は再帰なしで true を返します。

于 2016-09-01T05:26:49.247 に答える