无向图在计算机绘图中的应用

摘 要：本文把笔式绘图仪绘图过程时间最少的调度问题转换为在加权无向图中求解最优H-回路，并且利用最小生成树、欧拉回路、非二部图赋权匹配的算法给出了一种近似调度算法，旨在减少绘图仪移动空走时间和换笔时间，从而提高绘图效率。本算法经RP-MF160等绘图仪应用，效率提高约15%。

关键词：笔式绘图仪；调度算法；H-回路；加权图匹配

中图分类号：TP301 文献标识码：A

1 引言（Introduction）

计算机绘图是CAD和CAM的重要组成部分。随着计算机应用技术的飞速发展，目前已广泛应用于各个领域。

笔式绘图仪在完成一幅图的绘制时，其总时间消耗由三段组成：即实际绘图时间，抬笔移动空走时间以及更换画笔时间。由于实际绘图这段时间是必不可少的，因此，为了减少总时间消耗，提高绘图仪的使用效率，必须尽可能地减少另两段的时间耗费，即减少抬笔移动空走时间和换笔时间。这样一来，我们实际上面临的是一个绘图仪绘图过程的时间优化问题，解决的主要途径就是设计一个高效的绘图过程调度算法。目前，在设计绘图仪绘图过程时，采用的主要方法基本上是根据一幅图上各个基本图形的分布情况、相对位置以及程序设计人员的实际编程经验进行安排，还没有一个公认高效的调度算法作为依据。因此，不难想象，在某种复杂情况下，采用上述方法将会大大增加绘图仪绘图过程的时间开销，降低其使用效率。为此，下面将针对绘图仪绘图建立一种具体的数学模型，在此基础上给出一种相应的调度算法，并对其时间复杂度进行分析，旨在尽可能地减少绘图时的抬笔移动空走时间和换笔时间，降低其时间耗费。

2 建立数学模型（Set up mathematical model）

基本图形：指绘图仪无需抬笔就可一笔绘制完成的图形。即所谓的“一笔画”图形。如圆、矩形、三角形、弧线等。

一幅图：指若干基本图形依照某种特定的布局组合而成的图。

封闭图形：指由n（n为正整数）条线段或弧组成的闭合基本图形。如圆、矩形、三角形等。

开放图形：指由n（n为正整数）条线段或弧组成的非闭合基本图形。这里要求开放图形恰有两个端点。如抛物线、线段等。

无向图：指图G中每一条边都是无方向的。

加权无向图：指无向图G中每一条边e都对应一个实数W（e），称W（e）为e的“权”。

H-回路：指经过图G中每个节点一次且仅一次的回路。

另外，还要求绘图仪在绘制一个基本图形时，其间不能抬笔、间断。必须一次性完成。

接下来，我们可以将绘图仪完成一幅图绘制的操作过程描述如下：绘图仪将画笔从起始点移动空走到第一个基本图形，完成该基本图形的绘制后，再移动空走到下一个基本图形，完成绘制后，再移动空走……直至把所有基本图形绘制完毕，然后把画笔移动空走到初始位置。

下面我们用构造法将一幅图转换成与之对应的加权无向图，以此来描述绘图仪绘图过程并分析其时间复杂度。构造步骤如下：

（1）用一个实节点表示封闭图形，其坐标定为绘图仪绘制该基本图形时的起始位置。

（2）用两个实节点分别表示开放图形的两个端点，其坐标分别定为对应端点的坐标位置；另外，在两个实节点之间增加一个虚节点，其坐标定为这两个实节点的中心点坐标；该虚节点仅与这两个实节点有边相连，这两条边的权值均为0。

（3）用一个实节点来表示绘图仪的画笔起始位置，其坐标为画笔起始位置坐标。

（4）图中的任何两个实节点间均有无向边相连，每条边的权值均为画笔在该边所关联的两个实节点间移动空走所需时间。若两实节点对应的图形颜色不同，再加换笔时间。

采取上述的方法，可以由一幅图G构造出与之对应的一个加权无向图G*。这样一来，绘图仪绘制一幅图G的过程相当于G*上构造一个H-回路，反之亦然。实际上，绘图仪绘制一幅图G相当于在其对应G*中的一条H-回路上遍历一次。其所消耗的全部移动空走时间和换笔时间等于对应G*中的该条H-回路上各边的权值之和。因而，寻找花费时间最少的绘图过程相当于在G*中求解边权之和最小的H-回路，即最优H-回路。进一步，我们可以把绘图仪绘图过程调度问题抽象为在加权无向图中求解最优-回路问题。然而，求解加权无向图G*的最优H-回路属于NP完全问题。到目前为止，对此没有有效的多项式算法。因此，求解该问题的主要途径是设计有效的近似算法。

3 近似算法设计（The approximate algorithm design）

约定一幅图G对应的加权无向图为G*，C*为G*的一个最优H-回路，n=v（G*），OPT（G*）表示C*上各边权之和，并且假定G*不含虚节点，因此，任取x，y，z∈V（G*），满足：

（1）对称性：d（x，y）=d（y，x），其中d（x，y）表示节点x与节点y之间边的权值。

（2）三角不等式：d（x，z）≤d（x，y）+d（y，z）。

下面将运用最小生成树、E-回路、非二部图赋权匹配的标准算法来给出求G*图中最优H-回路的一种算法，称为最小匹配构造H-回路算法（简记MM）。

MM算法描述如下：

（1）求G*中的一棵最小生成树T*。

（2）求T*中奇度数节点构成的集合V"={a1，a2，…，a2k}。

（3）由V"中节点及相关边构成G*的一个子图G1*，求G1*中边权之和最小的完全匹配M，|M|=K。

（4）把M中的K条边加到T*上，得到T**，T**是一个E-图。

（5）求T**的一个E-回路。

（6）采用“捷径”技术[5]，将E-回路变为H-回路。

设MM（G*）表示MM算法在G*中产生的H-回路的边权之和。则有：

定理MM（G*）

证明见参考文献[2]。

MM算法的时间复杂度分析如下：

步骤1：采用Prim算法[4]，O（n2）。

步骤2：O（n）。

步骤3：采用Lawler算法[1]，O（n3）。

步骤4：O（n）。

步骤5：采用Fleury算法[3]，O（n3）。

步骤6：O（n2）。

因此，MM算法总的时间复杂度为O（n3）。

4 结论（Conclusion）

MM算法仅讨论了一幅图中只包含封闭图形和整个图为单一颜色的情况。若一幅图G包含开放图形且有多种颜色时，由G诱导的G*不满足三角不等式，需要对G*及MM算法做适当修改，较为复杂，限于篇幅，在此不作进一步讨论。

笔式绘图仪绘图过程之调度算法的研究是图论在计算机绘图领域的典型应用，尤其是文中所涉及的最优H-回路问题在运筹学中也有着实际意义。因此，越来越受到科研人员（尤其是CAD和CAM的从业人员）及有关商家的高度关注。若能将一个好的调度算法加以编程实现，再将其作为一个应用程序集成到绘图软件系统中，不仅能提高该绘图软件系统的商业价值，也将会大大提高绘图仪的使用效率。

参考文献（References）

[1] E L lawler.combinatorialOptimization：Networks and

Matroids[M].New York：Holt，Rinehart and Winston，1976.

[2] Garey M R，Johnson D S.computers and intractability-A

Guide to the Theory Of NPcompletemess[M].W H Freeman

and compang，1979.

[3] Bondy J A，murty U S R.Graph Theory with Applications[M].

Macmillan Press LTD，1976.

[4] 严蔚敏.数据结构[M].北京：清华大学出版社，1987.

[5] 卢开澄.组合数学—算法与分析[M].北京：清华大学出版社，

1983.

作者简介：

张 强（1962-），男，硕士，教授，硕导.研究领域：计算机科

学理论，软件技术，现代教育技术.

推荐访问:绘图 计算机