學習可視化表征工具軟件算法設計研究

朱良學

(酒泉職業技術學院，甘肅 酒泉 735000)

0 引言

學習可視化及其表征工具結構導圖是提高學生學習興趣、增強學生自主學習能力的一個重要途徑和優秀工具。在知識更新異常迅速的學習型社會，利用可視化技術將抽象的知識轉變成為易于被人們接受認知的圖形圖像，有助于知識快速學習和傳播，利用結構導圖軟件來繪制知識結構導圖也成為知識爆炸時代一個必然的選擇[1]。與傳統媒介(紙筆)相比，單幅圖(一個文件)能儲存的知識量足夠大，知識概括結構性、系統性好，一目了然；易于保存，便于修改，攜帶、與人交流和傳播都非常方便。要繪制出內容豐富、結構清晰的知識結構導圖，圖中各知識分支(關鍵詞節點)在界面的布局，就是一個核心重要的問題。

因此，基于手繪結構導圖的經驗和規則，總結出結構導圖軟件的布局規則，設計出結構導圖軟件的布局算法，就成了設計結構導圖軟件的關鍵問題[2]。

把結構導圖中的每個知識分支抽象成一個節點，知識分支間的邏輯關系用有向邊表示，這就是一個有向圖。結構導圖軟件的布局問題就轉化成為一個有向圖的層次布局問題。

1 學習可視化及其表征工具

“可視化”一詞，來源于英文的“visualization”，原意是“可看得見的，清楚的呈現”，也可譯為“圖示化”，如計算機編程的可視化界面(VB,VC等)。學習可視化是指學生在學習過程中運用可視化學習工具將學習內容(知識)、學習過程細節、學習成果以直觀形象的視覺方式表征，激發學生學習的積極性、主動性，增強學生的學習興趣，提高學生的學習效率[3]。利用學習可視化技術將嚴謹但枯燥的專業學習過程轉變為直觀、生動形象的個性化學習，極大地提高學生在知識學習中的創新意識和興趣，最終提升學生自主學習之品質，提高學習績效。

學習可視化的表征工具，其代表性工具就是思維導圖和概念圖。本人在研習思維導圖應用實踐的過程中，發現了博贊思維導圖在學生學習應用中的不足和缺點：思維過于發散，思維深度廣度不夠，思維系統性差；遂提出了結構化思維導圖(結構導圖)的概念，使思維導圖與結構化思維相結合，更好地體現了學習可視化在學生學習中的優勢[4]。如圖1就是一幅“英語語法知識體系”典型結構導圖。

圖1 “英語語法知識體系”典型結構導圖

2 有向無環圖

從圖1典型的結構導圖實例出發，將導圖中的每個知識分支簡化為圖中的一個節點，即導圖中有多少個分支，圖中就有多少個節點；導圖中知識分支間的關聯關系用圖中節點與節點之間的邊表示。這樣抽象的圖有三個顯著特征：

節點位置層次性：節點位置有明顯的層次關系；節點之間關系方向性：節點之間的箭頭是單指向的，兩節點間只能有單向邏輯關系；由于是結構化圖，圖中不可能存在環[5]。

這樣就將結構導圖轉換為一個有向圖。導圖中分支與分支間的關聯是單向的，這樣的圖一般是一個有向無環層級圖。

有向圖(Directed Graph ):圖中所有邊都是有向邊；有向邊由圖中兩個頂點有向連接構成，從一個頂點指向另一個頂點的箭頭表示邊的方向[6]。

有向無環圖(Directed Acyclic Graph，簡稱DAG): 在圖論中，如果一個有向圖無法從某個頂點出發經過若干條邊回到該點，則這個圖是一個有向無環圖，如圖2.

圖2 有向無環圖

層級圖(Hierarchical Graph):指一個已分層的有向無環圖，圖中所有邊都沒有方向表示，構成邊的兩個節點(父節點，子節點)已經含有方向關系[7]。

這樣結構導圖在平面上的繪制呈現問題就轉化為一個有向無環圖在平面上的布局問題[8]。

3 Sugiyama層次布局算法

層次布局算法,最典型最常用的是由Sugiyama,Tagawa和Toda(1981)提出的Sugiyama算法[9]。標準的該算法通常由三個部分構成:

第一，分層(Layer Assignment):將圖中所有節點分層，同層的節點具有相同的縱坐標；

第二，交叉減少(Crossing Reduetion):對層內節點重新排序，減少邊與邊的交叉數量；

第三，坐標分配(Coordinate Assignment):計算節點的坐標，同層的節點具有相同的縱坐標。

4 運用Sugiyama層次布局算法進行層次指定

定義1 給定有向無環圖(Directed Acyclic Graph,DAG)DAGG=(V,E),V是圖G中節點的集合，E是圖G中節點之間邊的集合。

寬度：對于圖G中任一節點v∈V,對應有一個寬度w；

圖的分層：將圖G的節點集合V分成子集V1,V2,…,Vk, 并且V1,V2,…,Vk互不相交；對于任一邊(u,v)∈E,u∈Vi,v∈Vj,則有i>j.如此分層的DAG即為分層圖。分層圖的層的數目h即為該圖的高度。

定義2 層Vk的寬度為w(Vk)﹦∑VEVk,分層圖的寬度w﹦max1≤k≤w(Vk).很顯然，通過分層，將所有節點歸置在不同的層中，假定某圖有k層，則表示該分層圖的高度為K,其取值范圍在1～k.這樣圖中每個節點都確定了縱坐標，同層的節點縱坐標值相同。

4.1 最長路徑分層算法

這種算法思想簡潔清晰，容易實現：假定某圖為G，u為G中任一節點，又圖中根節點所在層設為層1，則u的層數值即為該節點至根節點的最長路徑+1.這種算法能夠求得層數最小的分層結果，但將會使圖的寬度變為最大值。

4.2 最小化寬度分層算法

最長路徑分層算法使圖的層數最小，寬度變大，這樣的布局很不協調。為了找到一種長寬最一致的分層，提出了最小化寬度分層的思想：通過添加虛擬節點將設定部分做下移處理，使層中頂點數目減少，從而使交叉減少。找到一種寬度和高度都最佳的分層本身就是一個魚或熊掌不可兼得的問題，由于虛構節點也需要占據空間，導致的結果是圖的寬度值有可能大于預期值。

4.3 虛擬節點最少化分層算法

該算法目標是要找到一種虛擬節點最少的分層。減少虛擬節點(邊)，不僅可大大減少交叉模塊花費的時間，而且使得圖的布局更加協調、緊湊。但同理，這種算法對于圖的長度和寬度沒有良好的處理。

基于以上算法的優缺點，在上面三個算法基礎上，Healy 和Nikolv于2001年提出了著名的WHS-layering算法：修正了最小化寬度分層算法的寬度邊界問題，而且通過參數的設置，可以設定圖的寬度和高度邊界值，以及調整節點和邊(虛構節點)的寬度值。顯然，這是一個折中有效的處理結果。

5 運用Sugiyama層次布局算法減少交叉

圖的層次布局要簡潔、緊湊，簡潔就是節點間邏輯關系結構性好，緊湊就是圖布局要協調，不能太散。圖中邊與邊的交叉直接影響了圖的邏輯性，使圖不易閱讀。所以，層次布局中要最大可能的盡量減少邊與邊交叉。減少圖中的交叉數量不僅使圖的邏輯表達更流暢，表示的內涵也更易于理解。最簡單的一個交叉減少思路莫過于：“可減少圖中兩個輸入層之間的交叉數量”設想，這就是2-交叉減少算法[10]。

要對整幅圖進行“交叉減少”，一般有K-層交叉減少算法，這一算法的基礎就是2-交叉減少算法。下述的“逐層清理”(layer-by-layer sweep)思想也是以2-交叉減少算法為基礎，旨在減少整個圖的交叉數。

由于每層中節點的排列順序決定了圖中的交叉數目，即便圖中僅有兩層，，要設計算法完全消除其中的交叉都是不可能的，目前能達到的就是設計有效的算法盡量減少邊的交叉數。

下面說明“逐層清理”過程的主要思想。

第一，節點順序初始化。對每一層各個節點的順序進行初始化,具體做法就是對節點編號，從左到右依次為1,2,…,n,n為該層的節點數，其中也含虛擬節點在內。

第二，自頂向下清理。設定層Li-1,從i﹦2,…,k, 做循環, 使用一個單邊2-交叉減少算法找出層Li的一個新排序。

第三，自底向上清理。設定層Li-1,從i～k開始,反過來第(2)步,使用一個單邊2-層交叉減少算法找到層Li的一個新排序。

第四，重復第(2)步和第(3)步,若無法獲得更優的結果，終止。

2-層交叉減少算法中一般用的是單邊(one-sided)2-層交叉減少算法,其思路比較容易理解：先設定兩層中的一層不動,對另一層進行重排，從而減少交叉。基于該思想的常見啟發式算法有如下一些：排列啟發式算法、重心啟發式算法、中值啟發式算法、分支切割啟發式算法、貪婪交換啟發式算法等。

下面著重說明排列啟發式算法和重心啟發式算法。

排列啟發式算法的思路是：先窮盡所有可能性，即將一層中的所有節點進行排列；而后擇優，即從所有產生的排列中選擇出最小交叉的排列。其優點很明顯，能夠找到單邊2-層交叉減少的最優結果。缺點也很顯著，如果這一層中節點數比較大(N個)，當然也包括虛擬節點，那計算量就非常大(N!)，時間復雜度為N!，這就不易用了。

下面通過一個實例來說明重心啟發式算法的思路。

如圖3所示，第一層有四個節點a,b,c,d,其初始順序依次為1,2,3,4；第二層有3個節點Ⅰ，Ⅱ，Ⅲ ，其初始順序依次為1,2,3；顯然，圖3的交叉數為5.

現在按照節點相關聯的邊在鄰層中的平均順序值重排節點。

第一步，先設定abcd所在的第一層不動，與Ⅱ相連接的兩邊端點為bc，其在第一層的順序分別是2和3,可以算出X的重心值為2.5.同理，Ⅱ和Ⅲ的重心依次計算得出為3和1.由于第一層(abcd所在層)不動，根據Ⅰ,Ⅱ,Ⅲ的重心值按從小到大排序,得到新的節點順序為Ⅲ，Ⅰ，Ⅱ.如下圖4所示：

圖4的交叉數已減少到1.

第二步，再設定Ⅰ,Ⅱ,Ⅲ所在的第二層不動，如上計算出abcd的重心值，得到新的排序為acbd，如圖5所示：

圖5 交叉數0

圖5的交叉數已減少到0.

由于重心啟發式算法思路簡潔、易于理解，輸出結果表現良好，時間復雜度也呈線性，并不復雜，因此得到廣泛應用。

6 運用Sugiyama層次布局算法進行坐標分配

現在要計算分層圖中所有節點的坐標，這些節點包括真實節點、虛擬節點(實際是有向無環圖中的邊)。虛擬節點的引入雖然方便了分層處理，但也產生了多余的彎曲點，要盡量減少。對圖中所有節點橫坐標(X-坐標)和縱坐標(Y-坐標)可以分別單獨進行計算[11]。

縱坐標(Y-坐標)計算的規則是：同一層中的所有節點具有相同的Y-坐標，也就是它們的Y值都一樣；Y值通常是由節點所在的高度以及層與層之間的最短距離決定。

X-坐標的計算。對于一個分層圖G﹦(VUB,E;L)，V是所有真實節點的集合，集合B表示所有虛擬節點，集合E表示所有邊，集合L表示所有層。每層中節點之間的最小距離用Δ表示。分層圖的橫坐標計算問題就可以做如下描述：

分層圖G﹦(VUB,E;L)中每層的節點都已排好序；v和u是G中同層相鄰的節點，v∈V∪B，

u∈V∪B；x(u)+Δ≤x(v).

通常橫坐標的計算采取的策略有兩種：利用啟發式算法，不斷對布局逐步改進，以期達到目標效果；對一個受約束的坐標差異的目標函數做最優化處理。

式(1)(2)是Sugiyama算法中的目標函數：

(1)

(2)

現在對這兩個表達式做分析和說明。u和v是G中同層的兩個相鄰節點。

1)式主要是判定分層圖的邊的長度。

2)式作用主要是處理節點與其上、下層相鄰節點的位置關系問題，盡量使節點與其上、下層相鄰節點保持協調。

顯然目標函數受到兩個因素的影響，一個是層中節點最小距離Δ，一個是虛擬邊的約束。

要控制分層圖的邊的長度，一個必要條件是：分層圖中任何一個節點都位于其相鄰節點坐標的中心。用式(3)來計算節點的X坐標：

(3)

用這個表達式計算出的節點坐標，不論從圖的平面性而言，還是從圖節點分布的勻稱性而言，布局效果都是良好的。

為了保證分層圖布局后的易讀性，一般考慮以下三個方面的因素：盡可能使邊的長度要短一些，這樣使圖緊湊; 盡可能使跨層邊要保持直；對于圖中任何一個節點，其位置要能使該節點與其上下層的相鄰節點保持協調、勻稱。(1)(2)(3)解決了前兩個因素的問題。對于第三個因素，Sugiyama算法的解決策略是這樣的：假定對于圖G,對于任何一條有向道,v1,…,vk∈V,v2vk-1∈B，用式(4)來做控制：

(4)

7 算法總體設計構想

以上對圖的布局所涉及的關鍵問題及其重要細節做了分析處理,現在給出算法的總體設計思路。遵循解決復雜問題由易到難的簡化原則,將一個典型的結構導圖剝離其中所表達的內容因素,抽象成有向無環平面圖，有向是因為結構導圖中一個上一級節點指向下一級節點的關系是單向的,只能是上一級節點指向下一級節點,它們之間是父子關系,圖中的有向邊表達的其實就是這種關系[12]。再把這一有向無環平面圖轉換為層級圖，層級圖中的每條邊都沒有方向表示,其上下父子關系已經隱含了方向表示，現在問題就轉換成一個層級圖的平面布局問題。Sugiyama算法是最典型的層級布局算法。運用Sugiyama層次布局算法進行層次指定，將圖中所有節點分層，同層的節點具有相同的縱坐標。層次指定相當于層級圖布局中節點位置的重新調整，層次越多，圖中邊與邊的交叉就有可能越發增多，節點間邏輯關系就會呈現結構很不清晰的狀態，這樣就需要運用Sugiyama層次布局算法中另一個模塊來減少邊與邊交叉。由于要完全消除這樣的交叉不可能，只能設計算法盡可能減少邊的交叉數，使圖重新邏輯關系清晰，結構性好。最后需要運用Sugiyama層次布局算法進行坐標分配,對于層級圖中的節點要確定其在平面布局中的具體位置。處在同一層中的節點縱坐標相同，這個值通常可以由節點所在的高度以及層與層之間的最短距離計算出來。橫坐標的計算稍顯復雜，前面已有論述，此不復述。算法整體設計如圖6所示：

圖6 算法整體設計

8 結論

結構導圖是學習可視化的一個重要表征工具，在結構導圖軟件的設計過程中，知識分支節點在平面上位置的調整、分布，即圖的布局問題是一個基本而又重要的問題。本文將一個典型結構導圖抽象簡化為一個有向無環圖，應用Sugiyama層次布局算法中的“分層模塊”對此有向無環圖進行分層，處理了虛擬節點；對分層后的節點應用“減少交叉”模塊減少節點間邊的交叉數，使節點間邏輯關系結構清晰；應用“坐標分配”模塊計算出圖中各節點的坐標，同層的節點具有相同的縱坐標，主要是橫坐標計算；考慮了圖中節點分布的勻稱性、可讀性好等因素。該算法已在本人申請的甘肅省高等學校科研項目《學習可視化理論、應用及其表征工具軟件設計研究》中得到應用，并編程實現，得到了比較理想的效果。