Dijkstra算法在BIM審查中的應用

文｜北京構力科技有限公司 魏重潔 王委 王嘉 何啟明；中交天津港灣工程研究院有限公司 宋博文

0 引言

BIM 技術對于促進建筑全生命周期的信息化具有重要的意義，目前在實際項目中的應用頗為廣泛。隨著BIM 技術的普及，BIM 信息化數據審查的意義也逐漸凸顯[1-2]。傳統的二維施工圖審查并沒有真正的實現智能化審查，需要審查工作人員對提交的二維圖紙進行全專業的審查工作，將存在以下問題：問題（1）：在審圖過程中，由于審圖人員對規范的理解、專業水平、經驗以及審查尺度等不一致，這會造成審查結果的不一致。問題（2）：由于審查工作涉及的專業眾多，需要審查的規范眾多。隨著各個專業的飛速發展，各個專業所涉及審查規范的版本也在不停的更新之中，審查工作量大。在審圖工作進行時，存在挑選重要審查部位進行針對性審查。由此，造成了審查工作的不全面，規范條文漏審的情況。問題（3）：政府管控難。主管部門無法及時獲取施工圖審查過程中各環節存在的問題，對施工圖設計、審查質量的真實情況難以準確掌握，監管的有效性和時效性均不能得到保證。針對以上問題，2017年湖南省以工程建設項目三維數字報建為切入點開啟基于BIM 模型的施工圖數字化審查。2019年，指導各地開展城市信息模型（CIM）基礎平臺建設，推進智慧城市建設，北京、雄安、廣州、南京、廣州、廈門、雄安等多個城市被住房和城鄉建設部列為城市信息化建設和建筑信息模型審查的試點城市[3-6]。

隨著建筑信息化審查工作的開展，具體條文內容的審查以及建筑信息化數據的處理方法也成為數值化審查工作中的重點工作。特別是對應建筑消防的數字審查工作，如建筑消防審查參考的一個主要規范《建筑設計防火規范》（GB 50016-2014，2018年版）[7]。這本規范中5.5.17 對于疏散路徑的審查，需要對審查模型中的疏散路徑進行計算后與規范數值進行比對。模型中疏散路徑的計算一直都是數值化審查中的難點，針對該問題，本文將Dijkstra 算法應用到BIM 審查的數字計算中，更為準確的求除疏散路徑。

表1 防火規范中疏散距離的規定

1 Dijkstra 算法

Dijkstra 算法處理的是一組結點集合數據中各個節點到其他節點的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最短路徑問題是圖論研究中的經典算法問題。最常用的路徑算法有：Dijkstra 算法、A*算法、SPFA 算法、Bellman-Ford 算法和Floyd-Warshall 算法[8-11]。本文中主要正對Dijkstra 算法在消防審查中疏散路徑問題的應用進行描述。

為更好得理解Dijkstra 算法，如圖1所示，現有結點集合S=[P1、P2、P3、P4、P5、P6]以及其各節點之間的路徑信息，①為結點編號，-3-為路徑信息，各個結點之間雙向距離相等，再應用Dijkstra 算法對已知結點集合S 求其最短路徑。依據圖1的路徑星系，第一步列出一個二維數據結構，儲存結點集合S 中各個結點之間的直接路徑數據，形成表2所示的對稱的二維矩陣。

表2 直接路徑信息儲存表

圖1 結點集合以及其路徑線示意圖

第二步以結點1 直接到達各個結點的路徑距離為結點1 到各個結點的初始最短路徑距離，求到結點1 路徑最短的那個結點。根據最初的直接路徑信息儲存表可以確定，結點1 的路徑最短結點為結點2，并可以確定結點1 到結點2 的最短路徑為直接到達的路徑，即結點2-結點1。計算結點1 通過結點2 到達各個結點的路徑，并且將該路徑值與結點1 直接到達各個結點的路徑距離對比，取兩者的最小值，可以得到結點1 各個結點的最短路徑距離如表3所示。可以發現結點5、結點6 到結點1 的最短路徑得到了刷新。

表3 通過結點2 刷新的最短路徑

第三步獲取通過結點2 刷新的最短路徑的最短路徑結點（除結點2 外），可以確定此時的最短路徑結點為結點4，并且可以確定此時結點4 到結點1 的最短路徑為直接到達路徑，即結點4-結點1。計算結點1 通過結點4 再到各個結點的路徑距離，并與表2中的路徑距離對比，取兩者的最小值，可以得到結點1 到各個結點的最短路徑距離如表4所示。在該步驟比較中，并沒有最短路徑得到刷新。

表4 通過結點4 刷新的最短路徑

第四步獲取通過結點4 刷新的最短路徑的最短路徑結點（除結點2、結點4 外），可以確定此時的最短路徑結點為結點5，并且可以確定此時結點5 到結點1 的最短路徑為結點5-結點2-結點1。計算結點1 通過結點5 再到各個結點的路徑距離，并與表3中的路徑距離對比，取兩者的最小值，可以得到結點1 到各個結點的最短路徑距離如表5所示。在該步驟比較中，并沒有最短路徑得到刷新。

表5 通過結點5 刷新的最短路徑

第五步獲取通過結點5 刷新的最短路徑的最短路徑結點（除結點2、結點4、結點5外），可以確定此時的最短路徑結點為結點3，并且可以確定此時結點3 到結點1 的最短路徑為結點3-結點2-結點1或者結點3-結點1。計算結點1 通過結點3 再到各個結點的路徑距離，并與表4中的路徑距離對比，取兩者的最小值，可以得到結點1 到各個結點的最短路徑距離如表6所示。在該步驟比較中，并沒有最短路徑得到刷新。

表6 通過結點3 刷新的最短路徑

2 Dijkstra 算法的應用

2.1 計算前處理

在進行實際樣例模型計算之前，需要對實際樣例模型進行簡化處理。獲取Revit模型的房間內輪廓線以及疏散門、安全出口的位置點。如圖2所示，在對求圖中各個房間的疏散門到疏散走道的安全出口之間的疏散距離，即疏散門到安全出口的最短路徑。在求最短距離問題時，可以將房間內的疏散距離轉化為特征點之間最短路徑問題。特征點集合由疏散走道的輪廓線端點、疏散門以及安全出口的位置點組成，即S=[P1、P2、P3、P4、P5、P6、P7、P8、P9、P10]。如圖2所示，分別計算點集合S中P3、P4、以及P6 到P9 的最短路徑。

圖2 樣例模型示意圖

如圖3所示，在對點集合進行計算時，我們需要根據各個點之間的實際距離確定各個結點之間的路徑距離，即取樣例模型中各個結點的連線長度。需要注意，在實際問題中，當兩點直線連線穿越墻體時，人在疏散時無法按照該直線距離逃生，該疏散路徑可直接丟棄，即將兩點之間的路徑距離直接賦值正無窮大，進行后續計算。

2.2 Dijkstra 計算

在計算如圖3所示的樣例模型時，先根據Dijkstra 算法，算出所有結點到其他結點的最短路徑。

圖3 樣例模型Dijkstra 算法路徑線示意圖

第一步：

求出各個結點之間的距離，并存入一個二維數組D[10,10]，作為P1 結點到第P10 個結點之間的初始最短距離；

初始化一個一維數組Length，并存入P1 結點到其他結點的距離；

初始化一個一維數組Used，并存入Pi結點是否被遍歷，序號為0 即Used[0]=true，其他為false；

初始化一個字典，并存入P1 結點的最短路徑所經過的結點序號。

第二步：

初始化一個最小值dMin=double 值的最大值；

初始化一個序號k=0，即P1 結點在S中的序號；

循環所有的結點，找到沒有被遍歷過的結點中距離P1 最短的結點Pm（dMin=P1至Pm 之間的距離），并將k 刷新為結點Pm的序號m-1，數組Used[k]刷新為true。

循環所有的結點，找到沒有被遍歷過的結點Pn，如果Length[n-1]大于dMin 加上D[m-1,n-1](即結點P1 到結點Pn 的距離大于結點P1 通過結點Pm 到結點Pn 的距離)，則刷新數組Length 的值，Length[n-1]=dMin+D[m-1,n-1]，并更新字典中最短路徑的結點序號。

表7 疏散門至安全出口的最短路徑

第三步：

重復第二步，直至所有點集S 中結點被遍歷，以此求得各個結點到其他結點的最短路徑。

在求得所有結點到其他結點的最短路徑后，分別獲取P3 至P9，P4 至P9 以及P6 至P9 的最短路徑，如圖4所示。

圖4 初始疏散路徑結果

2.3 結果后處理

通過Dijkstra 算法對樣例模型進行計算，我們能夠得到疏散門位置點到安全出口位置點的距離。

實際最短疏散距離還需要對比疏散門邊到安全出口門邊的距離，此時只需要對比各個疏散門位置點與兩個門框在疏散路徑的最短距離，可確定為最終的疏散路徑，如圖5所示。

圖5 疏散路徑結果

2.4 計算結果在審查中的應用

將以上求解的疏散路徑結果應用以實際項目的審查之中，如圖6所屬的項目，疏散門到安全出口的最短路徑為33.116m，不滿足5.5.17 中疏散門至安全出口的疏散距離應該小于等于15m 的要求。

圖6 疏散路徑算法在審查項目中的應用

3 結論

本研究將Dijkstra 算法應用到BIM 審查的數字計算中，對《建筑設計防火規范》（GB 50016-2014，2018年版）中5.5.17條文中的疏散門到安全出口的疏散路徑進行計算。將房間輪廓線的兩個端點以及疏散門、安全出口的位置點作為特征點集合，應用Dijkstra 算法對特征點集合進行計算。將得到的初步疏散路徑再次經過門寬部分最短路徑對比，得到最終的疏散路徑。根據計算的最短路徑，與規范5.5.17 中的相關規定進行比對，以此審查出不滿足規范的距離。