張強(qiáng)

摘 要：本文把筆式繪圖儀繪圖過程時間最少的調(diào)度問題轉(zhuǎn)換為在加權(quán)無向圖中求解最優(yōu)H-回路，并且利用最小生成樹、歐拉回路、非二部圖賦權(quán)匹配的算法給出了一種近似調(diào)度算法，旨在減少繪圖儀移動空走時間和換筆時間，從而提高繪圖效率。本算法經(jīng)RP-MF160等繪圖儀應(yīng)用，效率提高約15%。

關(guān)鍵詞：筆式繪圖儀；調(diào)度算法；H-回路；加權(quán)圖匹配

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

計算機(jī)繪圖是CAD和CAM的重要組成部分。隨著計算機(jī)應(yīng)用技術(shù)的飛速發(fā)展，目前已廣泛應(yīng)用于各個領(lǐng)域。

筆式繪圖儀在完成一幅圖的繪制時，其總時間消耗由三段組成：即實(shí)際繪圖時間，抬筆移動空走時間以及更換畫筆時間。由于實(shí)際繪圖這段時間是必不可少的，因此，為了減少總時間消耗，提高繪圖儀的使用效率，必須盡可能地減少另兩段的時間耗費(fèi)，即減少抬筆移動空走時間和換筆時間。這樣一來，我們實(shí)際上面臨的是一個繪圖儀繪圖過程的時間優(yōu)化問題，解決的主要途徑就是設(shè)計一個高效的繪圖過程調(diào)度算法。目前，在設(shè)計繪圖儀繪圖過程時，采用的主要方法基本上是根據(jù)一幅圖上各個基本圖形的分布情況、相對位置以及程序設(shè)計人員的實(shí)際編程經(jīng)驗進(jìn)行安排，還沒有一個公認(rèn)高效的調(diào)度算法作為依據(jù)。因此，不難想象，在某種復(fù)雜情況下，采用上述方法將會大大增加繪圖儀繪圖過程的時間開銷，降低其使用效率。為此，下面將針對繪圖儀繪圖建立一種具體的數(shù)學(xué)模型，在此基礎(chǔ)上給出一種相應(yīng)的調(diào)度算法，并對其時間復(fù)雜度進(jìn)行分析，旨在盡可能地減少繪圖時的抬筆移動空走時間和換筆時間，降低其時間耗費(fèi)。

2 建立數(shù)學(xué)模型（Set up mathematical model）

基本圖形：指繪圖儀無需抬筆就可一筆繪制完成的圖形。即所謂的“一筆畫”圖形。如圓、矩形、三角形、弧線等。

一幅圖：指若干基本圖形依照某種特定的布局組合而成的圖。

封閉圖形：指由n（n為正整數(shù)）條線段或弧組成的閉合基本圖形。如圓、矩形、三角形等。

開放圖形：指由n（n為正整數(shù)）條線段或弧組成的非閉合基本圖形。這里要求開放圖形恰有兩個端點(diǎn)。如拋物線、線段等。

無向圖：指圖G中每一條邊都是無方向的。

加權(quán)無向圖：指無向圖G中每一條邊e都對應(yīng)一個實(shí)數(shù)W（e），稱W（e）為e的“權(quán)”。

H-回路：指經(jīng)過圖G中每個節(jié)點(diǎn)一次且僅一次的回路。

另外，還要求繪圖儀在繪制一個基本圖形時，其間不能抬筆、間斷。必須一次性完成。

接下來，我們可以將繪圖儀完成一幅圖繪制的操作過程描述如下：繪圖儀將畫筆從起始點(diǎn)移動空走到第一個基本圖形，完成該基本圖形的繪制后，再移動空走到下一個基本圖形，完成繪制后，再移動空走……直至把所有基本圖形繪制完畢，然后把畫筆移動空走到初始位置。

下面我們用構(gòu)造法將一幅圖轉(zhuǎn)換成與之對應(yīng)的加權(quán)無向圖，以此來描述繪圖儀繪圖過程并分析其時間復(fù)雜度。構(gòu)造步驟如下：

（1）用一個實(shí)節(jié)點(diǎn)表示封閉圖形，其坐標(biāo)定為繪圖儀繪制該基本圖形時的起始位置。

（2）用兩個實(shí)節(jié)點(diǎn)分別表示開放圖形的兩個端點(diǎn)，其坐標(biāo)分別定為對應(yīng)端點(diǎn)的坐標(biāo)位置；另外，在兩個實(shí)節(jié)點(diǎn)之間增加一個虛節(jié)點(diǎn)，其坐標(biāo)定為這兩個實(shí)節(jié)點(diǎn)的中心點(diǎn)坐標(biāo)；該虛節(jié)點(diǎn)僅與這兩個實(shí)節(jié)點(diǎn)有邊相連，這兩條邊的權(quán)值均為0。

（3）用一個實(shí)節(jié)點(diǎn)來表示繪圖儀的畫筆起始位置，其坐標(biāo)為畫筆起始位置坐標(biāo)。

（4）圖中的任何兩個實(shí)節(jié)點(diǎn)間均有無向邊相連，每條邊的權(quán)值均為畫筆在該邊所關(guān)聯(lián)的兩個實(shí)節(jié)點(diǎn)間移動空走所需時間。若兩實(shí)節(jié)點(diǎn)對應(yīng)的圖形顏色不同，再加換筆時間。

采取上述的方法，可以由一幅圖G構(gòu)造出與之對應(yīng)的一個加權(quán)無向圖G*。這樣一來，繪圖儀繪制一幅圖G的過程相當(dāng)于G*上構(gòu)造一個H-回路，反之亦然。實(shí)際上，繪圖儀繪制一幅圖G相當(dāng)于在其對應(yīng)G*中的一條H-回路上遍歷一次。其所消耗的全部移動空走時間和換筆時間等于對應(yīng)G*中的該條H-回路上各邊的權(quán)值之和。因而，尋找花費(fèi)時間最少的繪圖過程相當(dāng)于在G*中求解邊權(quán)之和最小的H-回路，即最優(yōu)H-回路。進(jìn)一步，我們可以把繪圖儀繪圖過程調(diào)度問題抽象為在加權(quán)無向圖中求解最優(yōu)-回路問題。然而，求解加權(quán)無向圖G*的最優(yōu)H-回路屬于NP完全問題。到目前為止，對此沒有有效的多項式算法。因此，求解該問題的主要途徑是設(shè)計有效的近似算法。

3 近似算法設(shè)計（The approximate algorithm design）

約定一幅圖G對應(yīng)的加權(quán)無向圖為G*，C*為G*的一個最優(yōu)H-回路，n=v（G*），OPT（G*）表示C*上各邊權(quán)之和，并且假定G*不含虛節(jié)點(diǎn)，因此，任取x，y，z∈V（G*），滿足：

（1）對稱性：d（x，y）=d（y，x），其中d（x，y）表示節(jié)點(diǎn)x與節(jié)點(diǎn)y之間邊的權(quán)值。

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

下面將運(yùn)用最小生成樹、E-回路、非二部圖賦權(quán)匹配的標(biāo)準(zhǔn)算法來給出求G*圖中最優(yōu)H-回路的一種算法，稱為最小匹配構(gòu)造H-回路算法（簡記MM）。

MM算法描述如下：

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

（2）求T*中奇度數(shù)節(jié)點(diǎn)構(gòu)成的集合V'={a1，a2，…，a2k}。

（3）由V'中節(jié)點(diǎn)及相關(guān)邊構(gòu)成G*的一個子圖G1*，求G1*中邊權(quán)之和最小的完全匹配M，|M|=K。

（4）把M中的K條邊加到T*上，得到T**，T**是一個E-圖。

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

（6）采用“捷徑”技術(shù)[5]，將E-回路變?yōu)镠-回路。

設(shè)MM（G*）表示MM算法在G*中產(chǎn)生的H-回路的邊權(quán)之和。則有：

定理MM（G*）證明見參考文獻(xiàn)[2]。

MM算法的時間復(fù)雜度分析如下：

步驟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算法總的時間復(fù)雜度為O（n3）。

4 結(jié)論（Conclusion）

MM算法僅討論了一幅圖中只包含封閉圖形和整個圖為單一顏色的情況。若一幅圖G包含開放圖形且有多種顏色時，由G誘導(dǎo)的G*不滿足三角不等式，需要對G*及MM算法做適當(dāng)修改，較為復(fù)雜，限于篇幅，在此不作進(jìn)一步討論。

筆式繪圖儀繪圖過程之調(diào)度算法的研究是圖論在計算機(jī)繪圖領(lǐng)域的典型應(yīng)用，尤其是文中所涉及的最優(yōu)H-回路問題在運(yùn)籌學(xué)中也有著實(shí)際意義。因此，越來越受到科研人員（尤其是CAD和CAM的從業(yè)人員）及有關(guān)商家的高度關(guān)注。若能將一個好的調(diào)度算法加以編程實(shí)現(xiàn)，再將其作為一個應(yīng)用程序集成到繪圖軟件系統(tǒng)中，不僅能提高該繪圖軟件系統(tǒng)的商業(yè)價值，也將會大大提高繪圖儀的使用效率。

參考文獻(xiàn)（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] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1987.

[5] 盧開澄.組合數(shù)學(xué)—算法與分析[M].北京：清華大學(xué)出版社，

1983.

作者簡介：

張 強(qiáng)（1962-），男，碩士，教授，碩導(dǎo).研究領(lǐng)域：計算機(jī)科

學(xué)理論，軟件技術(shù)，現(xiàn)代教育技術(shù).