為了明確啟發(fā)式排序DFS,BFS和NDS的性能優(yōu)劣及正確選擇合適的排序策略和排序起點,采用實證研究方法,在比較DFS,BFS和NDS排序策略性能的基礎(chǔ)上,研究排序策略選擇和排序起點選擇的指標數(shù)據(jù).提出依賴集總長度小優(yōu)先的排序策略和最佳排序起點的選擇方法,并在工程網(wǎng)絡(luò)中進行驗證.結(jié)果表明:1)相比較于BFS和DFS,NDS能指導(dǎo)生成更小的BDD模型;2)指標數(shù)據(jù)依賴集總長度可以有效表征排序策略和排序起點;3)基于依賴集總長度小優(yōu)先的選擇方法有助于選出最優(yōu)的排序策略和排序起點.該結(jié)果可以為選擇和設(shè)計啟發(fā)式排序策略提供理論依據(jù).

【文章頁數(shù)】：6 頁

【部分圖文】：

圖13×3SquareLattice網(wǎng)絡(luò)

在圖1中,若按小編號優(yōu)先進行BFS排序,則得到節(jié)點和邊的混合排序結(jié)果為:n0≤e1≤e2≤n1≤e3≤e4≤n3≤e5≤e6≤n2≤e7≤n4≤e8≤e9≤n6≤e10≤n5≤e11≤n7≤e12≤n8;若選用DFS進行排序,則得到n0≤e1≤n1≤e3≤n2≤e7≤n5≤e8≤....

圖2規(guī)則網(wǎng)絡(luò)

分別在如圖2所示的網(wǎng)絡(luò)中進行實驗,按節(jié)點對統(tǒng)計各排序策略指導(dǎo)生成的最小/最大BDD模型的次數(shù),見表1.表1不同策略下最小/最大BDD模型出現(xiàn)的次數(shù)規(guī)則網(wǎng)絡(luò)最小BDD模型次數(shù)最大BDD模型次數(shù)DFSBFSNDSDFSBFSNDSDe-Bruijn(Order=....

圖3BDD模型尺度的圖形表示

上述實驗結(jié)果如圖3和圖4所示.圖4指標數(shù)據(jù)依賴集總長度的圖形表示

圖4指標數(shù)據(jù)依賴集總長度的圖形表示

圖3BDD模型尺度的圖形表示從圖3和圖4可知,對于同一排序策略,排序起點不同,排序結(jié)果的TLDS值也不同,從而指導(dǎo)生成的BDD模型尺度不同.當(dāng)TLDS較小時,對應(yīng)的BDD模型尺度較小;TLDS較大時,對應(yīng)的BDD模型尺度較大,即指標數(shù)據(jù)依賴集總長度與BDD模型尺度之間存在相關(guān)性....

本文編號：3978018