Yufei Tao: Interactive Graph Search
タイトル
ソース
Proceedings of the 2019 International Conference on Management of Data
巻
号
ページ
1393-1410
年
2019
ISBN
978-1-4503-5643-5
著者
概要
内容
コメント
DAGからインタラクティブかつ効率的にNode検索する手法の提案 問題例
1. 何らかのDAGがあると仮定
2. 2人のプレイヤーがいるとする(BobとAlice)
3. BobはNodeを一つ選ぶ
4. Aliceはできるだけ少ない質問でBobが選んだNodeを見つける
Q. この場合どんな戦略を取れば質問数を減らせるか
最大の部分木(subtree)を持つNodeへのEdgeをHeavy, それ以外をLightとしてNode/Edgeを分類する
最大の部分木になるPathから順にDFSしていく
5.1のアルゴリズム
DFS TreeはNodeから辿れるNodeの総数が最も多いNodeを選ぶことで構築できる
分岐に差し掛かったときは↑でcountしたNodeが多い方に進む
https://gyazo.com/5b94ed1e239a654b0e9000cc3758c44a