有向無(wú)環(huán)圖的布局優(yōu)化方法與實(shí)現(xiàn).pdf

1、有向無(wú)環(huán)圖DAG(Directed Acyclic Graph)廣泛應(yīng)用于數(shù)據(jù)庫(kù)建模、工程設(shè)計(jì)等領(lǐng)域。將矩陣存儲(chǔ)的DAG圖正確、美觀地繪制出來(lái),可以使其更直觀、清晰,并且方便各種問(wèn)題的分析和處理。DAG畫(huà)圖是一個(gè)有挑戰(zhàn)的工作,要求的算法不僅要正確表達(dá)各個(gè)結(jié)點(diǎn)的偏序關(guān)系,同時(shí)還要給出圖的方向。后者表明無(wú)向圖的畫(huà)圖方法不能用于有向圖,但是有向圖可以從相應(yīng)的無(wú)向圖的畫(huà)圖方法得到可用的策略。 在DAG畫(huà)圖領(lǐng)域,已經(jīng)有很多有效的針對(duì)不同類

2、型和不同領(lǐng)域的畫(huà)圖方法。本文從畫(huà)圖的3條審美標(biāo)準(zhǔn)出發(fā),提出針對(duì)審美標(biāo)準(zhǔn)的解決方法,設(shè)計(jì)了新的畫(huà)圖方法：提出了分層問(wèn)題的多項(xiàng)式時(shí)間算法和消除啞結(jié)點(diǎn)算法；通過(guò)重新設(shè)計(jì)交叉算子、變異算子和控制參數(shù)改進(jìn)了已有的分層和最小化邊交叉的遺傳算法。 為了驗(yàn)證所提出的畫(huà)圖算法的可行性和正確性,用Java語(yǔ)言實(shí)現(xiàn)了LEMDES(Layered Edge-crosses Minimization and Dummy-nodes Elimination