search

khei4 / sym_diff

symbolic differentiation optimizer
MIT License
1 stars 0 forks source link

支配木を求めるアルゴリズムを実装する #4

Open khei4 opened 3 years ago

khei4 commented 3 years ago

早すぎる最適化以外のなにでもないけど, 論文の肝であるここは理解しておきたい

khei4 commented 3 years ago

https://onlinejudge.u-aizu.ac.jp/problems/0294 dfsをするときにSortをするのをやめろ

khei4 commented 3 years ago

というか, 微分グラフをどう表現するかがあんまり想像できていない. #16

とりあえず辺を, Nodeの両端点とExpを持つものとして作るのはいいとして. Sum of Productを部分グラフに対して計算しなきゃいけないのだけど それはPost Orderがついていればいい感じにできるのかな？？ 競プロ力...

khei4 commented 3 years ago

したいこと

支配関係を求める.

子供の数, 親の数が両方すぐ参照できるようにしたい →隣接リストなら二種類必要 Nodeを構造体にすれば一つで両方兼ねれる？