图实现算法综述与评测分析

• 作者: 孙天元 李德英 王永才
• 来源期刊: 自动化学报
• 关键词: 图实现 网络定位 全局优化 模块拼合 综述 刚性 全局刚性
• 年，卷（期）: 2020,（4）
• 所属期刊栏目: 综述
• 页码范围: 613-630
• 页数: 18页
• 字数: 13773字
• 语种: 中文
• DOI: 10.16383/j.aas.2018.c170561

摘要

图实现(Graph realization)问题研究基于节点间全部或部分距离关系测量,在d维空间中计算图的顶点坐标,使得在所实现图中各节点之间实现距离与测量距离尽可能一致.图实现问题是一个典型的优化问题,在传感器网络定位、蛋白质结构重建、数据可视化、社交网络分析、机器人同步定位与构图等领域有着广泛应用.图实现的研究同图刚性理论有着紧密的联系,图的刚性与全局刚性决定图的可实现性.在可实现图中,现有工作提出几类典型的代表性图实现算法,包括:1)基于三边测距类方法;2)求解距离方程类方法;3)基于全局优化类方法;4)基于模块拼合类方法.本文对图实现的刚性理论,四类图实现算法的设计思想、适用条件、算法流程等进行综述分析,通过实验对算法进行准确性、计算复杂度、可靠性等方面的比较和分析.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王永才	中国人民大学信息学院	21	75	4.0	8.0
2	李德英	中国人民大学信息学院	6	88	3.0	6.0
3	孙天元	中国人民大学信息学院	1	0	0.0	0.0