最短路徑算法在電阻片落料系統中的應用

朱菊香

（常州鐵道高等職業技術學校機電工程系，江蘇 常州213011）

0 引言

落料是利用沖裁取得一定外形的制件或坯料的沖壓方法，在電阻片生產中經常會用到這一制造工藝。以某公司PT06電阻片的生產為例，它需要經過兩次落料，第一次落料一次剔除基板上的不合格品，第二次落料將基板上剩余的合格品一次性沖落。在第一次落料時，需要知道不合格電阻的位置，并以較短的時間或運動路徑來沖除不合格品。

本文利用Prime最小生成樹算法來解算沖壓機構的最短運行路徑，縮短了落料過程的時間，尤其在基板不良品較多時，效果明顯。

1 落料系統的工作流程

整個落料系統是基于X—Y導軌結構的，包括機架、基板夾具、移動工作臺、導軌、絲杠、氣壓沖頭及步進電機等。PT06電阻片的基板為長方形的環氧樹脂印制板，其上共印制了12行20列共240個碳膜電阻片。基板夾具用來放置待測的電阻片基板，在其下方按電阻片在基板上的位置排列了測試探針。

工作流程如下：（1）電阻片基板進入基板夾具定位；（2）測試探針升至測試高度；（3）系統掃描測試探針處的檢測信號大小，獲得每個電阻片的阻值及不合格品在基板上位置；（4）氣壓沖頭到達基板上方，根據不合格品的位置信息沖落廢品；（5）電阻片基板退出夾具，送至成品區批量落料。以上過程中耗時最多的便是沖落不合格品的過程。

2 不合格品的定位

基板上的電阻片是通過20路運算放大電路來采樣的，每次采樣采集某一行電阻片的阻值，這樣共采樣12次后便能獲得所有240個電阻片的阻值。控制器通過控制20片多路模擬開關CD4067的通道地址，將12行的測試探針信號連接至運放電路。

通過兩個參數便可判斷不合格電阻片的位置信息。第一個參數為該電阻片所對應的CD4067的通道地址，第二個參數為該CD4067模擬輸出端所對應的模數轉換器的通道號。將這兩個通道參數合并，便可得到不合格電阻片在基板上的位置，如圖1所示。

圖1 電阻片位置示意圖

圖中，左側的0000～1100是CD4067的通道地址，0000代表選通第0個模擬通道，1100代表選通第11個模擬通道。CD4067的通道地址也代表了電阻片在基板上的行位置。上方AIN0～AIN19是20片CD4067模擬輸出端對應的ADC通道號，代表了電阻片在基板上的列位置。若CD4067的第1個通道選通，則行碼為0001，又發現PA7通道所對應的AD轉換值超出了5%的范圍，即模擬通道7的采樣值超標，則轉換成電阻片的位置為（1，7），即第1行、第7列。

3 最短路徑解算

可通過行列碼來儲存不合格電阻片的位置信息。若CD4067的第1個通道選通，則行碼為0001，又發現第7個通道的采樣數據超出了合格范圍，則第1行、第7列的電阻片為不合格品，記行列碼為（1，7）。

為了縮短工作臺移動的時間，節省電力和提高工作效率，需要對工作臺的移動路徑作出規劃，即要找出一條最短路徑，并將該路徑存入不合格電阻片隊列中供控制程序讀取，使得按該隊列順序可在最短的時間內將不合格電阻片沖除。

圖2為不合格電阻片組成的一個圖數據結構示例。

圖2 不合格電阻片組成的圖結構

圖中每個頂點代表一個不合格電阻片，頂點與頂點之間的權值為這兩個電阻片之間的距離。如第1行第1列頂點與第3生成的。顯然，遍歷所有頂點的最短路徑為（1，1）、（4，1）、（2，2）、（3，3）、（1，4）。

遍歷所有頂點又使路徑達到最短的算法在數據結構中被稱為求解最小生成樹。構造最小生成樹有多種算法，這些算法往往都利用了最小生成樹的 MST性質，即先假設N＝（V，｛E｝）為一個聯通圖，U是頂點集V的一個非空子集，若（u，v）是一條具有最小權值（最短路徑）的邊，則其中u∈U，v∈V－U，必存在一棵包含邊（u，v）的最小生成樹。

本設計采用的Prime算法即是利用MST性質求解最小生成樹（最短路徑）的算法。它假設N＝（V，｛E｝）是聯通網，TE是N 上最小生成樹中邊的集合，Prime算法從U＝｛u0｝（u0∈V），TE＝｛空｝開始，重復執行下述操作：在所有u∈U，v∈V－U的邊（u，v）∈E中找一條代價最小的邊（u0，v0）并入TE，直至U＝V為止。

此時，TE中必有n－1條邊，且T＝（V，｛TE｝）為N的最小生成樹，也即本設計要求解的最短路徑。

軟件系統找出這一最短路徑之后，將這些頂點（電阻片位置）的行列坐標按遍歷次序存入一個隊列當中，提供給步進電機控制模塊讀取。

為支持Prime算法，需要一個合適的數據結構來描述電阻片狀態。一般情況下，圖的數據結構可由鄰接矩陣、鄰接表或多重鄰接表來表示。本設計中采用鄰接表來存儲圖數據。若用鄰接矩陣，因采用數組的方式來存儲數據，所以需要占用240個存儲單元，而不合格電阻片畢竟為數不多，因此會使鄰接矩陣產生大量無用的“0”元素。而若采用鏈接存儲結構的鄰接表可避免這樣的問題出現。鄰接表的節點數可隨不合格電阻片的數目動態調整。對于圖2所示的情形，用鄰接表來存儲的形式如圖3所示。圖3表示的是一個無向重聯通圖，第一列框左邊的序號代表節點編號，框內信息為不合格電阻片位置，右側各框中的信息分別為節點編號、權值（節點間距離）、下一個節點的存儲地址。

圖3 不合格電阻片的鄰接表結構

4 結語

大量試驗表明，落料系統應用最短路徑解算方法之后取得了較好的效果。最短路徑求解的應用，有效縮短了氣動沖壓頭在X—Y導軌上的移動行程，由此帶來的好處不僅為縮短空程時間，電力消耗也得到降低，設備維護周期也變得更長。因電阻片產量巨大，即使在每個環節僅節省數十秒的空程時間，最后也能獲得可觀的經濟效益。

［1］張曉敏．構建整體化的自動化測試平臺［J］．中國高新技術企業，2010（22）：24－25．

［2］嚴蔚敏，吳偉民．數據結構（C語言版）［M］．北京：清華大學出版社，2011．

［3］王安敏，牛傳猛，崔偉．基于X－Y工作平臺的步進電機閉環控制系統［J］．微電機，2010，43（1）：103－105．

［4］殷人昆，陶永雷，謝若陽，等．數據結構（用面向對象方法與C＋＋語言描述）［M］．北京：清華大學出版社，1999．

［5］王昊，李昕．集成運放應用電路設計360例［M］．北京：電子工業出版社，2007．