高级检索
刘婷婷, 汪云海, 屠长河, 蒋鹏. 基于蒙特卡罗树搜索的树图布局[J]. 计算机辅助设计与图形学学报, 2021, 33(9): 1367-1376. DOI: 10.3724/SP.J.1089.2021.18682
引用本文: 刘婷婷, 汪云海, 屠长河, 蒋鹏. 基于蒙特卡罗树搜索的树图布局[J]. 计算机辅助设计与图形学学报, 2021, 33(9): 1367-1376. DOI: 10.3724/SP.J.1089.2021.18682
Liu Tingting, Wang Yunhai, Tu Changhe, Jiang Peng. Treemap Layout Based on Monte Carlo Tree Search[J]. Journal of Computer-Aided Design & Computer Graphics, 2021, 33(9): 1367-1376. DOI: 10.3724/SP.J.1089.2021.18682
Citation: Liu Tingting, Wang Yunhai, Tu Changhe, Jiang Peng. Treemap Layout Based on Monte Carlo Tree Search[J]. Journal of Computer-Aided Design & Computer Graphics, 2021, 33(9): 1367-1376. DOI: 10.3724/SP.J.1089.2021.18682

基于蒙特卡罗树搜索的树图布局

Treemap Layout Based on Monte Carlo Tree Search

  • 摘要: 树图是层次数据可视化的常用方法,已有的研究发现,满足逐步加点原则的3种树图布局算法(正方化布局算法、条状布局算法和螺旋线布局算法)在常见的4种优化指标(平均长宽比、稳定性、数据一致性和可读性)上各有优缺点.其中,条状布局算法和螺旋线布局算法的长宽比较大,正方化布局的长宽比仍有优化空间.基于蒙特卡罗树搜索,在树图布局的同时构建对应的搜索树并利用置信度上界公式作为搜索路径的选定标准,在用户可接受时间内对3种布局算法的算术平均长宽比和所提加权平均长宽比分别进行了优化.为了证明算法的有效性,在构造出的3种不同分布、7种不同规模的单层数据集以及真实的多层数据集上测试,并与原算法进行比较分析,最后利用对应结论指导用户选择更好的布局算法以及设置更恰当的参数.

     

    Abstract: Treemaps are a commonly used method for hierarchical data visualization.The previous research shows that three treemap layout algorithms(SQR,STR,SPI)that meet the principle of gradually adding points on four common optimization indicators(average aspect ratio,stability,consistent data,readability)have their own advantages and disadvantages.Both Strip and Spiral algorithms result in relatively large as-pect ratio of layouts,and the squarified treemap has some room for optimization in the aspect ratio.Based on Monte Carlo tree search,the corresponding search tree is constructed while laying out the treemap and the upper confidence bound formula is used as the selection criterion for the search path.For the three layout algorithms,the arithmetic average aspect ratio and the newly proposed weighted aspect ratio are improved within acceptable time for users.To show the effectiveness of the algorithm,the evaluation with the con-structed single-layer dataset which with 3 different distributions and 7 different scales and multi-layer real dataset is conducted and then the results are compared with the original algorithm.The guidelines for users to select a suitable layout algorithm and set proper parameters are also provided.

     

/

返回文章
返回