LoginSignup
1
0

More than 5 years have passed since last update.

Fertile Forest Model (11/n) 実数列化ツリーモデル

Last updated at Posted at 2016-01-01

実数列化ツリーモデル (Linearized Tree Model)

「入れ子集合モデル」の左右カラムを実数化した「入れ子区間モデル」と同じく、 FF モデルにも 序列カラムを実数化した「実数列化ツリーモデル( Linearized Tree Model )」があります。 QUEUE を実数にすれば、その間が無限に区切れます。これを利用すれば、ノード追加時のコストが軽減できるというわけです。

「実数列化ツリーモデル」は理論上は成立しますが、実用した際に問題が発生することが分かっています。その根拠も入れ子集合モデルと同じで、実数の精度が有限なので無限に区切れないというものでした。

結論に至った経緯

FFモデルのライブラリは、当初は「肥沃な森林モデル」と「実数列化ツリーモデル」を同時に公開する予定で進めていました。ところが、実装中に上記の問題に行き当たり、それが解決不能であることが分かりました。実際にライブラリを作成してみた人でないと気づきにくいかと思います。

現時点では解決不能と結論づけていますが、将来その問題がクリアできるアイディアが得られる可能性はあります。もし見つかったなら、改めて実数列化ツリーモデルのライブラリを作成する予定でいます。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0