張強(qiáng)

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

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

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

1 引言（Introduction）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）對(duì)稱性：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)用最小生成樹(shù)、E-回路、非二部圖賦權(quán)匹配的標(biāo)準(zhǔn)算法來(lái)給出求G*圖中最優(yōu)H-回路的一種算法，稱為最小匹配構(gòu)造H-回路算法（簡(jiǎn)記MM）。

MM算法描述如下：

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

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

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

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

（5）求T**的一個(gè)E-回路。

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

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

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

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

4 結(jié)論（Conclusion）

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

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

參考文獻(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] 盧開(kāi)澄.組合數(shù)學(xué)—算法與分析[M].北京：清華大學(xué)出版社，

1983.

作者簡(jiǎn)介：

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

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