木構造（位相構造）を比較するアルゴリズムって？

質問

木構造（位相構造）を2つ用意し、根からたどって比較してゆき、
差分をとるようなプログラムを書こうと思っています。
しかしアルゴリズムがまったくわからないので質問させていただきます。

子ノードの順番が異なる場合も同じものと見なすような条件で、
末端にノードが追加された程度の差異がわかればよいです。
（鏡に映した構造や、子ノードがABCという順だったのを、ACBにしたような構造は同じものと見なしたいということです。）

このようなアルゴリズムというのはあるのでしょうか？

回答No.4

arrysthmia · ベストアンサー

＞ 子ノードをソートする基準がないため

自分で基準を設定すればよいのです。(数学的には)それで済みます。

例えば、葉の評価値を 1 とし、
j 番目の子ノードの評価値が v_j であるようなノードの評価値を
j 番目の素数を p_j として (p_j)^(v_j) の総積 と定義します。

この評価値は、木を行きがけ順に１回たどるだけで、全て求めることができます。
各ノードの評価値を求める際に、子ノードの評価値をソート(v_j の j を付け替える)
してしまえば、子ノードの順番が異なる場合も同じものと見なすような木の「構造」
に対して一意的な値になります。
最後に、両方の根の評価値が一致しているか見ればok。

理論的には簡単ですが、この方法だと、木の段数が増えるにつれて
評価値の数値がベラボーに大きくなりますから、
実装は、あまり現実的ではないかもしれません。

木の構造に一意的な評価値を付ける替わりに、子ノード同士のマッチングを
枝狩りするのに役立つ部分的な情報をノードに持たせる 手もあると思います。

例えば、そこから下の部分木の総ノード数を、各ノードの評価値とするとか。
ノード数だけでは、どの子ノードとどの子ノードを比較すべきか決定はできませんから、
多少のバックトラックは発生しますが、全てのマッチングについて比較を試みるよりは
効率的かと思います。

補足

下の回答への補足としてネットワーク構造の比較をしたいと書きましたが、
もっと言うと3次元空間に存在する点と曲線からならなる構造の、意味的な構造を
比較するためにネットワーク、木構造という考え方を用いようと思っています。

このようなデータを2種類用意し、共通となる端末点をなんらかの方法できめた上で、
そのノードをスタートとして木構造を作成しています。

2つの木構造（木A、木Bとします）で分岐があるときに、
木Aと一方の分岐線が、木Bの分岐線のうちどちらに対応するのかを決定することができません。
言い換えれば、分岐がどちらに対応するかがわかればこの問題は解決します。

リンクは長さ情報は一応持ってはいるのですが、長さ自体が木Aと木Bで異なる場合があり、
保証されていませんので、できれば使わずに済む方法を考えたいと思っています。

以上が基準がない、決められないと述べた理由です。

木構造ではなく、ネットワーク構造の比較をしたい、と質問を変えさせていただきます。

私の考えとしては
・複数の端末ノードが一致するという条件のもと、わかるところまで端末から攻めていく
・ネットワーク途中のノードにも一致条件を持たせる

の2つを盛り込めば解決できるのではないかと思っているのですが、どうでしょうか

回答No.3

graphaffine

質問の一部を見落としてました。
>根からたどって比較してゆき、
根を持つのでしたら根付き木ですよね。そうすると先ほどの
「根付き木でなく抽象木が対象のようですね。」は撤回します。
しかし、
>（鏡に映した構造や、子ノードがABCという順だったのを、ACBにしたような構造は同じものと見なしたいということです。）
と仰られているからには根付き木ではありませんね。
結局、かなり特殊な木を考えておられるようですので、その具体的な定義或いは形を明確にしてもらわないと回答は難しいと思います。

補足

比較元となるデータはノードとリンクからなるネットワークのようなものです。（ループは存在しません）
このネットワークを、ある1ノードを根とした木構造と見なし比較するのが今回の目標です。
もっと言えばネットワークを比較できればなんでもいいです。
木構造的な考え方が適していると私が考えたためにこのような質問になりました。

ネットワークとして考えれば、鏡に映したものは同じであると考えるのは
正しいと思うのですが、これは間違いでしょうか。
そもそも木構造として考えるのが不適切なのでしょうか…

回答No.2

graphaffine

質問内容が、良く分かりません。
位相構造とは具体的にどのように定義されていますか。
普通は、位相を考えることは無いので単に筆が滑ったとは思いますが。
それから、差分とは具体的にはどう言うものを言ってるのでしょう。

一応、根付き木でなく抽象木が対象のようですね。
>末端にノードが追加された程度の差異がわかればよいです。
そもそも抽象木で末端とは何を言ってますか。

回答No.1

arrysthmia

各ノードが、予め、自分の子ノードをソートして持つ
ようなデータ構造にしておくのは、どうでしょう？
(子ノードがACBという順だったら、ABCにしてしまってから
比較したら良いということです。)

補足

ご回答ありがとうございます。

私の説明が足りなかったので補足します。
確かにその方法ができればいいのですが、子ノードをソートする基準がないため、
子ノードがソート済であることを前提とするアルゴリズムは採用できないのです。

（厳密にはソートは可能かもしれませんがかなり複雑になりそうです。こちらについても検討はしておりますが…