基于熱流道系統硬管鋪設的最短路徑方法研究

王遵義 仲梁維

摘? 要：對于熱流道系統，將軟管改為硬管可以節約成本，同時也提高了其外觀及品質。但是，硬管的手工折彎導致裝配成本更高，因此基于熱流道3D模型開發一款插件，能夠在三維軟件中自動對熱流道三維模型提取特征，程序自動生成硬管管道的最優路徑。利用VB.NET對Solidworks進行二次開發，提取熱流道系統的框架特征，運用迪杰斯特拉算法求解最短路徑，最后將最短路徑坐標以表格的形式顯示在三維軟件中。

關鍵詞：特征提取;迪杰斯特拉算法;最短路徑

中圖分類號：TP391.7? ? ?文獻標識碼：A

Research on the Shortest Path Method of Hard Pipe

Laying based on Hot Runner System

WANG Zunyi， ZHONG Liangwei

（University of Shanghai for Science and Technology， Shanghai 200093， China）

1270623490@qq.com; zlv@usst.edu.cn

Abstract： Replacing hoses of hot runner system with hard pipes can save costs and improve the appearance and quality of the hot runner system. However， manual bending of hard pipes leads to higher assembly costs. This paper proposes to develop a plug-in based on the three-dimensional （3D） model of the hot runner， which can automatically extract features from the 3D model of the hot runner in the 3D software and generate optimal path of hard pipes. VB.NET is used to re-develop Solidworks， frame features of the hot runner system are extracted， and Dijkstra's algorithm is used to solve the shortest path. Finally， the shortest path coordinates in the form of a table is displayed in the 3D software.

Keywords： feature extraction; Dijkstra's algorithm; shortest path

1? ?引言（Introduction）

近幾年，由于計算機技術的高速發展，各種軟件和算法層出不窮，未來人工智能將大有作為[1]。而人工智能應用的基礎是對智能算法的深入研究，其中最短路徑問題對各行各業有著深入的影響，比如地圖和智能導航系統都需要使用智能算法解決最短路徑的問題[2]。

目前熱流道系統軟管的成本比較高，而硬管的成本相對較低，且使用壽命更長、更可靠，同時提高了熱流道系統的外觀和品質。因此將熱流道系統軟管換成硬管不僅可以節約成本，而且保證了熱流道系統的品質。但是目前的熱流道上的硬管都是采用折彎的方式進行裝配，雖然硬管的成本低，但是裝配手工折彎的時間更長，從而導致裝配成本增加。因此，利用軟件自動計算并生成熱流道系統硬管的最短路徑，然后直接加工硬管管道，從而跳過手動折彎裝配環節，這樣既可以節約成本，又可以提高熱流道系統的品質，增加使用壽命。所以利用軟件和智能算法自動計算并生成硬管管道的最短路徑就顯得尤為重要[3]。

2? ?特征提取（Feature extraction）

利用三維軟件Solidworks打開熱流道系統的裝配體文件，對熱流道系統進行特征提取，獲得所需要的點坐標和框架，并將數據存儲到軟件中。特征提取的工作流程圖如圖1所示。

2.1? ?讀取裝配體文件

對于熱流道系統，首先需要用三維軟件Solidworks打開，然后對Solidworks進行二次開發，讀取當前已打開的裝配體文件。這里應用VB.NET程序語言對Solidworks進行二次開發，首先要獲得Solidworks的接口，連接成功后，Solidworks一共有三種文件類型：零件（PartDoc）、裝配體（AssemblyDoc）和工程圖（DrawingDoc）。這里需要讀取的是裝配體（AssemblyDoc）文件的名稱、屬性和部件[4]。

2.2? ?遍歷特征樹

每個熱流道系統裝配體都有幾十個甚至上百個部件，首先需要找到包含目標草圖的部件，因為包含目標草圖的部件有通用的名稱，可以根據名稱找到目標部件。每個部件又有上百個特征，需要遍歷目標部件的特征樹。判斷每個特征中是否含有草圖特征，如果沒有草圖特征則繼續遍歷下一個特征;如果含有草圖特征則判斷該草圖特征是否為目標草圖。根據目標草圖中草圖點和草圖線段之間特有的關系，將目標草圖從眾多特征中篩選出來。

2.3? ?獲得草圖點

提取目標草圖中的草圖點并且將草圖點按照框架的走勢進行排序，最后儲存到程序中。如圖2所示，根據API函數獲得的草圖點是亂序的，需要程序自動將獲得的草圖點按照如圖2標識所示進行排序并存儲到二維數組中。目標草圖中草圖點的類型有很多，比如線段端點、線段中點、單獨點等，可以根據草圖點的類型和數量對草圖點進行排序。將排序后得到的草圖點三個坐標值存儲到二維數組中。

3? ?迪杰斯特拉算法（Dijkstra）

3.1? ?算法概述

迪杰斯特拉（Dijkstra）算法是典型的求解單源最短路徑的一種算法，用于計算一個節點到其他節點的最短路徑。迪杰斯特拉算法的核心是循環遍歷除了起點之外的其他所有節點，并計算它們到起點的距離，根據排序計算出距離起點最近的節點并存儲到起點所在的集合中[5]。這是遍歷循環的第一層，算法會遍歷循環計算除起點之外集合中所有的節點，每計算一個節點，都需要排序計算出距離起點最近的節點并存儲到起點所在的集合中。

3.2? ?算法原理

在圖論中有一種圖叫帶權有向圖，帶權有向圖最常見的問題是求解兩點之間最短路徑[6]，迪杰斯特拉算法是最典型的求解帶權有向圖最短路徑問題的算法，很多其他求解圖論中最短路徑的算法都是迪杰斯特拉算法的變體。

首先，假設表示帶權有向圖的集合為F=（I，D），其中I表示有向圖中節點的集合，D表示各節點的權重[7]。把節點集合I分成兩組，一組為Q，表示已經求出的最短路徑節點的集合，起初集合Q只有一個起點;另一組為Z，表示除Q外，集合I中剩余的節點集合。在求解最短路徑時，每求得一個最短路徑的節點，都將該節點加入集合Q中，并將該節點從集合Z中刪除，直到遍歷循環集合Z中所有的節點，算法結束。在將計算出的節點從集合Z中移動到集合Q時，需要始終保持起點到Q各節點的最短路徑長度不大于起點到集合Z中各點的最短路徑長度。迪杰斯特拉算法原理流程圖如圖3所示。

4? ?最短路徑（Shortest path）

4.1? ?確定起點、終點坐標和方向

計算最短路徑時，首先需要確定起點和終點。在熱流道系統中分為油路和水路，本文只研究油路的走勢和最短路徑。一般來說，油路都是從一個電磁閥的接口連接到另一個電磁閥或者控制閥的接口。在提取特征時，獲得的是電磁閥接口草圖的原點坐標和接口的方向向量，因此需要根據點坐標和方向向量計算與草圖框架的交點，從而確定最短路徑的起點和終點。

起點的坐標和方向向量如圖4所示，根據點坐標和方向向量可以構建起點射線的方程，然后根據線段端點坐標構建線段1→2、2→3、3→4、4→5的方程。由平面幾何知識可知，平面內任意兩條不平行的直線必有交點，如圖4所示，交點1和交點2即需要求解的點。

求解步驟：

（1）構建起點射線方程和框架四條線段的方程。

（2）將方程系數存儲到數組中，建立行列式。

（3）由線性代數行列式知識可得，行列式可以表示方程，對行列式求解，所得的解即是兩條直線的交點坐標。

（4）如圖4所示，求解方程得到交點1和交點2，但是只有一個交點是我們需要的交點坐標。

（5）將交點1和交點2分別和起點建立方程，判斷起點→交點1的方向與起點的方向向量方向是否一致，如果一致則是我們需要的交點;如果不一致，則運用同樣的方法對交點2進行判斷。交點到起點的方向與起點方向向量的方向一致的交點才是我們需要的，實際計算過程中，由于草圖框架比較復雜，求得的交點往往不止兩個，方向一致的交點也可能有不止一個。

（6）當方向一致的交點個數大于一個時，計算所有交點到起點的距離，并且運用冒泡法對距離進行從小到大排序，距離最近的交點是我們需要的點。

4.2? ?計算最短路徑

首先計算出熱流道系統一共有多少條管道，然后利用循環語句，循環次數為管道的條數，循環體為生成管道最短路徑。

計算步驟：

（1）輸入特征提取的目標草圖框架。

（2）輸入起點坐標、終點坐標及管道數。

（3）編寫迪杰斯特拉算法程序，作為循環體。

（4）輸出最佳路徑坐標，并存儲到數組中。

（5）將最佳路徑系列坐標顯示在DataGridView中。

4.3? ?結果評估

給定起點和終點，測試程序自動生成的最短路徑測試結果如表1所示。Path_name是最短路徑的名稱，越復雜的熱流道系統，管道連接的數量越多，因此加以命名，以便區分;Point_name是點的名字，便于人工檢測最短路徑是否正確;X、Y、Z是點的三個坐標;Type是點的類型，用于程序識別點的種類。經過檢測，程序獲得的最短路徑與人工設計的路徑完全吻合，結果正確。

5? ?結論（Conclusion）

本文基于熱流道系統三維模型，對三維軟件Solidworks進行二次開發，開發一個插件，能夠實現在三維軟件中自動計算并生成硬管管道最短路徑，最后將最短路徑結果以表格（DataGridView）的形式顯示在三維軟件中。最短路徑的獲得是根據圖論中典型的單源最短路徑算法——迪杰斯特拉算法（Dijkstra）實現的[8]。自動生成的硬管管道熱流道系統不僅降低了系統的成本，而且提高了系統的質量和品質，同時降低了工人安裝管道的復雜程度，并且硬管管道相比軟管也更加美觀。

參考文獻（References）

[1] 趙美勇，宋思睿.三種最短路算法的比較[J].數碼世界，2019（06）：77.

[2] 劉汝佳.算法競賽入門經典[M].2版.北京：清華大學出版社，2014：56.

[3] 賴志剛.求解最短路問題的一個計算機算法解析[J].中國新通信，2019，21（20）：133.

[4] 曾慶紅，楊橋艷.最短路問題算法綜述[J].保山學院學報，2019，38（05）：44-46.

[5] （美）CORMEN T H， LEISERSON C E， RIVEST R L，等.算法導論[M].殷建平，徐云，王剛，等，譯.北京：機械工業出版社，2012：45-46.

[6] （美）SEDGEWICK R， WAYNE K.算法[M].4版.謝路云，譯.北京：人民郵電出版社，2012：23-25.

[7] 吳昕宇，羅雪穎.基于Dijkstra算法的旅游路線規劃研究[J].數碼世界，2019（07）：33-34.

[8] QU S X. Research on dynamic route guidance system based on comparison of shortest path algorithms[J]. International Core Journal of Engineering， 2020， 6（12）：12-14.

作者簡介：

王遵義（1993-），男，碩士生.研究領域：計算機輔助設計與智能制造.

仲梁維（1962-），男，碩士，教授.研究領域：計算機輔助設計，企業信息化.本文通訊作者.