论文部分内容阅读
要求在平面上确定几个设施的位置，已知任何两个设施i，j之间的相邻关系密切度为非负实数r（i，j）。问如何求出最合理的布局，即如何求出按此布局放置设施时，各相邻设施间的关系密切度之和为最大？针对这一设施平面布局问题，该文提出算法并证明之。算法的主要步骤为：1、求G的最大权生成树T；2、通过先序遍历树T找出一包含几个顶点的n边形；3、对n边形的里面和外面求出最大权的三角分划；4、n边形的边和这两个三角分划的对边的全体构成一个近似解。（珑摘）