Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

論文の支配木の使い方をちゃんと読む #11

Open
khei4 opened this issue Jan 24, 2021 · 5 comments
Open

論文の支配木の使い方をちゃんと読む #11

khei4 opened this issue Jan 24, 2021 · 5 comments

Comments

@khei4
Copy link
Owner

khei4 commented Jan 24, 2021 •
edited
Loading

特に多変数, 多出力の時に役に立つ方法だと思うんだけど, HashしてるならHash tableの方に全部持たせればええやんになってきた.
@khei4
Copy link
Owner Author

khei4 commented Feb 1, 2021

つまり木DPをすれば支配木なんて使わなくても同じ計算量で計算できるし.
支配木を求めるのにかける時間に対して, 結局式木をある程度まとめるだけで計算量は改善されないのではという.

@khei4
Copy link
Owner Author

khei4 commented Feb 6, 2021

木DPを何もわかっていなかったので勉強したけど厳しそう.
おとなしく支配木を実装する

@khei4
Copy link
Owner Author

khei4 commented Feb 6, 2021

Domは求められた気がするけど, Pdomが結構きつい
一旦DomTreeを求めるアルゴリズムをちゃんと説明作ろうと思った.

@khei4
Copy link
Owner Author

khei4 commented Feb 6, 2021

  • Pdomを求める
  • factor node, factor baseを求める
  • subgraphをEdgeにする

@khei4
Copy link
Owner Author

khei4 commented Feb 6, 2021

ていうか一旦PdomはSetを使ったIntersectionに戻しちゃうか

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@khei4