中小型藥房取藥最短路徑算法研究

包代小，李根全（1.南陽師范學院校醫院，河南南陽473061；.南陽師范學院物理與電子工程學院，河南南陽473061）

中小型藥房取藥最短路徑算法研究

包代小1＊，李根全2（1.南陽師范學院校醫院，河南南陽473061；2.南陽師范學院物理與電子工程學院，河南南陽473061）

目的：解決中小型藥房中取藥人員找藥過程費時費力的問題。方法：對藥房中藥架進行區域劃分，并針對各個區域內部、區域之間的出入口的具體位置進行分析，通過寬度優先遍歷的方法實現最短路徑的查找算法。結果：最佳取藥路徑算法分8步實現，由計算機自動設計路線，使得取藥人員可快速、輕松地獲得最短路徑。結論：通過此算法的實現，可以提高工作效率，且因實現此算法不依賴藥房的特定設備，所以此算法具有很好的推廣前景。

中小型藥房；最短路徑；算法；劃分；寬度優先遍歷；取藥

隨著計算機技術的發展，數據結構[1]和人工智能[2]領域在日常生活中的應用也日趨廣泛。最短路徑的思想產生已久，在查找最短路徑的研究中也不斷取得新的成果，如Ahmed等[3]提出SDP和SGDP 2個算法，Kobayashi等[4]提出的平面圖中不相交的最短路徑等。Te等[5]提出了對動態有序樹的壓縮算法，使得平面圖和樹有了更強的機動性。而最短路徑這個研究領域在實際生活中的應用也極其廣泛，如謝建國等[6]提出的基于平面規劃中的最短路徑原理提出的針對存儲的VBR壓縮視頻的最短路徑率平滑傳輸算法。在土地定級中，劉耀林等[7]探討了將圖論中的最短路徑理論應用于城鎮土地定級，并靈活應用最短路徑算法計算某類定級因子到評價單元的實際距離。在高速公路收費系統中，黃賢英等[8]提出了根據重慶高速公路路網的特點，采用分治法，以一種將Floyd算法和Johnson算法相結合的改進算法來求任意2個結點間的最小費用矩陣。

在藥房中，由于中西藥品種繁多，專業人員取藥時也不免會有忘記某些藥品的具體位置的情況，從而耽誤時間。為此，特日根等[9]提出了基于概率的增強型區分服務算法，提高了相對區分服務中成比例延遲區分（PDD）服務模型算法的公平性。趙雪峰等[10]提出了自動化藥房取藥系統，這是基于一定的機械原理設計的全自動取藥系統，這個系統具有很高的取藥效率，但成本過高，對于規模不大的藥房實用性不是很強。王立鑫等[11]提出的智能藥房中最小代價取藥原理是在綜合考慮了時間、機械臂承受能力等多個因素的基礎上提出的。但這個算法也只適用于大型藥房，因為一般藥房的單張處方單不會有太多的藥，不會出現一次拿不完的情況。尤其是在學校醫院里，學生買藥的計量單位是粒、盒、瓶，所以取藥路線可以成為決定取藥效率的唯一因素。

本文提出了適用于中小型藥房的取藥最短路徑算法，以寬度優先遍歷[5，9]為基礎進行路徑選擇（寬度優先遍歷是指在圖G中任選一頂點v為源點，其他點的初態均為未訪問過，并由v點出發，依次訪問v的所有鄰接點w1，w2，…，wt，從中選取度量值最大的為擴展點，然后再依次訪問其他所有未曾訪問過的鄰接點，依此類推，直至訪問到圖G中所有點）。該算法通過對藥架分布的分析進行區域劃分，并針對其劃分結果綜合考慮區域內、區域間不同出入口的具體位置進行路徑選擇，從而得到取藥的最短路徑。

1 藥架分析

在一般的中小型藥房內，藥品均是擺放在類似于書架的藥架上，所以對于每一種藥都有一個平面坐標，按此坐標可以建立一個藥品坐標網絡，且其中會有多種藥品擁有同一個坐標。中小型藥房內的藥架分布格局示例見圖1。

圖1 中小型藥房內的藥架分布格局示例Fig 1Demonstration of drug shelves distribution in small and medium pharmacy

2 藥品網絡拓撲圖的構建

定義1：在藥房P中存在藥架集合A，其中藥架a，b∈A，且a≠b，若Ε為藥品），使得m1、m2坐標的連線穿越a或b的背面，則稱a和b為背靠背關系，用符號⊥表示，即a⊥b。如圖1中藥架2與藥架3的這種背靠背的關系，若只簡單考慮藥品坐標，而忽略實際中取藥需要繞行，則可導致取藥算法的失效。

定義2：在藥房P中存在藥架集合A，其中藥架a，b∈A，且a≠b，若為藥品），使得m1、m2坐標的連線均不穿越a和b的背面，則稱a和b為連通關系，用符號<＝>表示，即a<＝>b。如圖1中從藥架1到藥架2的過程中，不會穿過任何其他的藥架，因此稱藥架1與藥架2的關系是連通關系。

藥品網絡拓撲圖的構建：根據定義1、定義2、定義3確定各藥架之間的連通關系以及區域的劃分，并通過此劃分確定其各自的出入口坐標。因為圖1中藥架7獨立成為一個整體，根據其實際情況，可以對藥架7設定3個出入口坐標。因此，可生成如圖2所示的藥房藥架分布格局的網絡拓撲圖。

圖2 藥房藥架分布格局的網絡拓撲圖Fig 2Network topology of drug shelves distribution in pharmacy

在算法中，通過每個整體的邊界坐標，確定所要取的藥品所在的區域，通過指定的出入口進入區域后，可以直接通過直線距離判斷最短的路徑。

3 最佳路徑算法原理

最佳路徑算法首先將處方單中所有藥品根據藥架區域劃分的情況分成若干類別，再確定每個劃分中取藥的順序，在完成某一劃分中取藥任務后，不再進入該區域。通過各劃分之間的出入口之間的連通性進入下一區域取藥，在完成所有取藥后，通過出入口回到起點。

3.1 區域間路徑選擇

所有的取藥路徑都是從起點開始，到起點結束。在確定所有要經過的區域后，通過回溯法找到最佳路徑。

從起點開始，將起點定為擴展點，記錄所有可擴展點與擴展點的距離，從所有下一步可擴展的區域中選取距離擴展點最近的一個未曾經過的區域，選定區域的入口是距離擴展點最近的入口，并累計此距離及選定的路徑，且此時擴展點為剛剛選定的區域。通過已選定的路徑繼續對未擴展的區域進行擴展，在此時路徑的累計長度超過之前其他路徑的累計長度，則選擇其他路徑繼續進行擴展，直到找到一條經過所有需要經過的區域的最短路徑。

3.2 區域內部路徑選擇

在區域內部，因為每個藥架之間是連通的，所有藥品之間都可以由直線相連，且區域間路徑確定后，每一個區域的入口及出口即已確定，所以路徑選擇的原則是：將入口定為初始擴展點，首先選擇距離擴展點最近的，如果存在多個可擴展點與擴展點距離相同，選擇距離出口最近的點擴展，并將此點定位為下一擴展點，繼續尋找路徑。

3.3 區域間路徑優化

在確定區域內部路徑后，每一個區域的內部的終點與下一區域的起點之間經過的出入口不一定是最佳的，如圖3所示。

根據算法之前的計算，各個區域的出入口的選擇是2個區域之間最接近的出入口，而不一定是距離區域內部起點或終點最近的出入口，所以需要重新計算路徑選擇的出入口是距離區域內部起點或終點最近點時的路徑長度，通過與原路徑長度進行比較，如果路徑更短，則說明區域間路徑需要優化。

圖3 需要優化的區域間路徑Fig 3 Interregional pathway in need of optimization

4 最佳取藥路徑算法實現

第1步：根據貨架的擺放確定區域的劃分，以及每個劃分的出入口。第2步：確定此次取藥所需要的所有劃分。第3步：將起點定為可擴展點，通過寬度優先遍歷確定回到起點并經過所有需要區域的路線。第4步：在每個區域內通過第3步中確定的路線確定區域內的起點和終點。第5步：由區域內起點出發，通過寬度優先遍歷確定到達終點的最短路徑。第6步：如果所有區域內的路線都已確定，繼續執行第7步，否則選定下一個未被確定區域內路線的劃分區域，繼續執行第4步。第7步：選定2個相連的區域B1和B2，且路徑順序中B1在B2之前，如果B1中存在另一出口，使得從B1內部終點到B2內部起點的路線長度更短，則B1中的出口被更新，B2入口也用同樣的方法確定其是否需要更新。第8步：若所有的出入口都已更新，則算法結束，否則繼續執行第7步。

5 討論

目前，國內醫院藥房的藥品主要是以固定式貨架來存儲，藥品存儲分散，因此，藥房工作人員在取藥過程中費時費力、處方處理效率低。為節省時間、提高效率，通過計算機技術確定醫院藥房最短取藥路徑成為迫切需要。且這種需要也不僅限于醫院，在各大藥店以及通過人工到貨架取貨的銷售系統中均具有重要的意義。上述內容提出了一種基于最短路徑算法的取藥算法，其核心思想是通過劃分，確定應有的所有路線，再通過寬度優先遍歷的思想從中選取最短路徑。因之前的分區選路徑的方法導致路線并非最優的情況，故最后通過對路線的優化確定最佳路徑。通過此算法的實現，不僅使工作人員能夠免去思考取藥路線的問題，還能快速得到最短路徑，既可以提高工作效率，又可增加工作人員對工作的熱情。此外，該算法的實現沒有依賴藥房專有的設備或工具，因此可將此算法移植到任意一個依賴貨架擺放的售貨系統中，因此其應用范圍比較廣泛。且該算法的實現成本不高，可以被廣大人群或商家接受。

因藥房的需要，藥房中的的藥架不一定都是書架式的，還有旋轉式、抽屜式等，在今后的研究中，要將這類藥架加入到算法中，綜合考慮取藥的所有情況。

[1] Kawaguchi M，Rondon P，Jhala R.Type-based Data Structure Verification[C].PLDI’09Proceedings of the 2009ACM SIGPLAN conference on programming language design and implementation table of contents，2009：304-315.

[2] Russell SJ，Norvig P，Canny JF，et al.Artificial Intelligence：A Modern Approach[M].Stuart Russell&Peter Norvig：Prentice Hall，2003：12-102.

[3] Ahmed M，Das S，Lodha S.Approximation algorithms for shortest descending paths in terrains[J].Journal of Discrete Algorithms，2010，8（2）：214.

[4] Kobayashi Y，Sommer C.On shortest disjoint paths in planar graphs[J].Discrete Optimization，2010，7（4）：234.

[5] Te RG，Li W，Li XF，et al.Storage Mode of the Dynamic Ordered Tree[C].2011International Conference on Computer Science and Service System（CSSS），2011：2591-2596.

[6] 謝建國，姜靈敏，陳松喬.VBR流式視頻的最短路徑率平滑傳輸算法[J].計算機學報，2004，27（3）：357.

[7] 劉耀林，范延平.最短路徑方法在土地定級中的應用[J].武漢測繪科技大學學報，2000，25（6）：510.

[8] 黃賢英，李玉桃，張本強.最短路徑搜索算法在高速公路收費系統中的應用[J].重慶工學院學報，2007，21（3）：44.

[9] 特日根，孫永雄，李雄飛，等.基于概率的增強型區分服務算法[J].計算機工程，2011，37（21）：71.

[11] 王立鑫，負 超，吳平龍，等.智能藥房中最小代價取藥原理算法及實現[J].計算機測量與控制，2004，12（6）：557.

Shortest Path Algorithm for Taking Drugs in Small and Medium Pharmacy

BAO Dai-xiao（University Hospital，Nanyang Normal University，Henan Nanyang 473061，China）
LI Gen-quan（Physics&Electronic Engineering College，Nanyang Normal University，Henan Nanyang 473061，China）

OBJECTIVE：To resolve the problems of time-consuming and energy-consuming when the staff are looking for drugs in small and medium pharmacy.METHODS：The drug shelves were divided into some units，the specific position of interface in each unit or among units were analyzed.The breadth-first was adopted to achieve the shortest path algorithm.RESULTS：By computers designing course automatically，optimal path algorithm for taking drugs was achieved by 8steps to enable the staff to get the shortest path easily.CONCLUSION：This algorithm can enhance the efficiency of work.The implementation of this algorithm does not need the unique equipments in pharmacies，so this approach has good prospects for promotion.

Small and medium pharmacy；Shortest path；Algorithm；Divide；Breadth-first；Taking drugs

R952

C

1001-0408（2012）13-1192-03

DOI10.6039/j.issn.1001-0408.2012.13.15

2011-04-25

2011-07-09）