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

包代小，李根全（1.南陽(yáng)師范學(xué)院校醫(yī)院，河南南陽(yáng)473061；.南陽(yáng)師范學(xué)院物理與電子工程學(xué)院，河南南陽(yáng)473061）

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

包代小1＊，李根全2（1.南陽(yáng)師范學(xué)院校醫(yī)院，河南南陽(yáng)473061；2.南陽(yáng)師范學(xué)院物理與電子工程學(xué)院，河南南陽(yáng)473061）

目的：解決中小型藥房中取藥人員找藥過(guò)程費(fèi)時(shí)費(fèi)力的問(wèn)題。方法：對(duì)藥房中藥架進(jìn)行區(qū)域劃分，并針對(duì)各個(gè)區(qū)域內(nèi)部、區(qū)域之間的出入口的具體位置進(jìn)行分析，通過(guò)寬度優(yōu)先遍歷的方法實(shí)現(xiàn)最短路徑的查找算法。結(jié)果：最佳取藥路徑算法分8步實(shí)現(xiàn)，由計(jì)算機(jī)自動(dòng)設(shè)計(jì)路線(xiàn)，使得取藥人員可快速、輕松地獲得最短路徑。結(jié)論：通過(guò)此算法的實(shí)現(xiàn)，可以提高工作效率，且因?qū)崿F(xiàn)此算法不依賴(lài)藥房的特定設(shè)備，所以此算法具有很好的推廣前景。

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

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

在藥房中，由于中西藥品種繁多，專(zhuān)業(yè)人員取藥時(shí)也不免會(huì)有忘記某些藥品的具體位置的情況，從而耽誤時(shí)間。為此，特日根等[9]提出了基于概率的增強(qiáng)型區(qū)分服務(wù)算法，提高了相對(duì)區(qū)分服務(wù)中成比例延遲區(qū)分（PDD）服務(wù)模型算法的公平性。趙雪峰等[10]提出了自動(dòng)化藥房取藥系統(tǒng)，這是基于一定的機(jī)械原理設(shè)計(jì)的全自動(dòng)取藥系統(tǒng)，這個(gè)系統(tǒng)具有很高的取藥效率，但成本過(guò)高，對(duì)于規(guī)模不大的藥房實(shí)用性不是很強(qiáng)。王立鑫等[11]提出的智能藥房中最小代價(jià)取藥原理是在綜合考慮了時(shí)間、機(jī)械臂承受能力等多個(gè)因素的基礎(chǔ)上提出的。但這個(gè)算法也只適用于大型藥房，因?yàn)橐话闼幏康膯螐執(zhí)幏絾尾粫?huì)有太多的藥，不會(huì)出現(xiàn)一次拿不完的情況。尤其是在學(xué)校醫(yī)院里，學(xué)生買(mǎi)藥的計(jì)量單位是粒、盒、瓶，所以取藥路線(xiàn)可以成為決定取藥效率的唯一因素。

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

1 藥架分析

在一般的中小型藥房?jī)?nèi)，藥品均是擺放在類(lèi)似于書(shū)架的藥架上，所以對(duì)于每一種藥都有一個(gè)平面坐標(biāo)，按此坐標(biāo)可以建立一個(gè)藥品坐標(biāo)網(wǎng)絡(luò)，且其中會(huì)有多種藥品擁有同一個(gè)坐標(biāo)。中小型藥房?jī)?nèi)的藥架分布格局示例見(jiàn)圖1。

圖1 中小型藥房?jī)?nèi)的藥架分布格局示例Fig 1Demonstration of drug shelves distribution in small and medium pharmacy

2 藥品網(wǎng)絡(luò)拓?fù)鋱D的構(gòu)建

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

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

藥品網(wǎng)絡(luò)拓?fù)鋱D的構(gòu)建：根據(jù)定義1、定義2、定義3確定各藥架之間的連通關(guān)系以及區(qū)域的劃分，并通過(guò)此劃分確定其各自的出入口坐標(biāo)。因?yàn)閳D1中藥架7獨(dú)立成為一個(gè)整體，根據(jù)其實(shí)際情況，可以對(duì)藥架7設(shè)定3個(gè)出入口坐標(biāo)。因此，可生成如圖2所示的藥房藥架分布格局的網(wǎng)絡(luò)拓?fù)鋱D。

圖2 藥房藥架分布格局的網(wǎng)絡(luò)拓?fù)鋱DFig 2Network topology of drug shelves distribution in pharmacy

在算法中，通過(guò)每個(gè)整體的邊界坐標(biāo)，確定所要取的藥品所在的區(qū)域，通過(guò)指定的出入口進(jìn)入?yún)^(qū)域后，可以直接通過(guò)直線(xiàn)距離判斷最短的路徑。

3 最佳路徑算法原理

最佳路徑算法首先將處方單中所有藥品根據(jù)藥架區(qū)域劃分的情況分成若干類(lèi)別，再確定每個(gè)劃分中取藥的順序，在完成某一劃分中取藥任務(wù)后，不再進(jìn)入該區(qū)域。通過(guò)各劃分之間的出入口之間的連通性進(jìn)入下一區(qū)域取藥，在完成所有取藥后，通過(guò)出入口回到起點(diǎn)。

3.1 區(qū)域間路徑選擇

所有的取藥路徑都是從起點(diǎn)開(kāi)始，到起點(diǎn)結(jié)束。在確定所有要經(jīng)過(guò)的區(qū)域后，通過(guò)回溯法找到最佳路徑。

從起點(diǎn)開(kāi)始，將起點(diǎn)定為擴(kuò)展點(diǎn)，記錄所有可擴(kuò)展點(diǎn)與擴(kuò)展點(diǎn)的距離，從所有下一步可擴(kuò)展的區(qū)域中選取距離擴(kuò)展點(diǎn)最近的一個(gè)未曾經(jīng)過(guò)的區(qū)域，選定區(qū)域的入口是距離擴(kuò)展點(diǎn)最近的入口，并累計(jì)此距離及選定的路徑，且此時(shí)擴(kuò)展點(diǎn)為剛剛選定的區(qū)域。通過(guò)已選定的路徑繼續(xù)對(duì)未擴(kuò)展的區(qū)域進(jìn)行擴(kuò)展，在此時(shí)路徑的累計(jì)長(zhǎng)度超過(guò)之前其他路徑的累計(jì)長(zhǎng)度，則選擇其他路徑繼續(xù)進(jìn)行擴(kuò)展，直到找到一條經(jīng)過(guò)所有需要經(jīng)過(guò)的區(qū)域的最短路徑。

3.2 區(qū)域內(nèi)部路徑選擇

在區(qū)域內(nèi)部，因?yàn)槊總€(gè)藥架之間是連通的，所有藥品之間都可以由直線(xiàn)相連，且區(qū)域間路徑確定后，每一個(gè)區(qū)域的入口及出口即已確定，所以路徑選擇的原則是：將入口定為初始擴(kuò)展點(diǎn)，首先選擇距離擴(kuò)展點(diǎn)最近的，如果存在多個(gè)可擴(kuò)展點(diǎn)與擴(kuò)展點(diǎn)距離相同，選擇距離出口最近的點(diǎn)擴(kuò)展，并將此點(diǎn)定位為下一擴(kuò)展點(diǎn)，繼續(xù)尋找路徑。

3.3 區(qū)域間路徑優(yōu)化

在確定區(qū)域內(nèi)部路徑后，每一個(gè)區(qū)域的內(nèi)部的終點(diǎn)與下一區(qū)域的起點(diǎn)之間經(jīng)過(guò)的出入口不一定是最佳的，如圖3所示。

根據(jù)算法之前的計(jì)算，各個(gè)區(qū)域的出入口的選擇是2個(gè)區(qū)域之間最接近的出入口，而不一定是距離區(qū)域內(nèi)部起點(diǎn)或終點(diǎn)最近的出入口，所以需要重新計(jì)算路徑選擇的出入口是距離區(qū)域內(nèi)部起點(diǎn)或終點(diǎn)最近點(diǎn)時(shí)的路徑長(zhǎng)度，通過(guò)與原路徑長(zhǎng)度進(jìn)行比較，如果路徑更短，則說(shuō)明區(qū)域間路徑需要優(yōu)化。

圖3 需要優(yōu)化的區(qū)域間路徑Fig 3 Interregional pathway in need of optimization

4 最佳取藥路徑算法實(shí)現(xiàn)

第1步：根據(jù)貨架的擺放確定區(qū)域的劃分，以及每個(gè)劃分的出入口。第2步：確定此次取藥所需要的所有劃分。第3步：將起點(diǎn)定為可擴(kuò)展點(diǎn)，通過(guò)寬度優(yōu)先遍歷確定回到起點(diǎn)并經(jīng)過(guò)所有需要區(qū)域的路線(xiàn)。第4步：在每個(gè)區(qū)域內(nèi)通過(guò)第3步中確定的路線(xiàn)確定區(qū)域內(nèi)的起點(diǎn)和終點(diǎn)。第5步：由區(qū)域內(nèi)起點(diǎn)出發(fā)，通過(guò)寬度優(yōu)先遍歷確定到達(dá)終點(diǎn)的最短路徑。第6步：如果所有區(qū)域內(nèi)的路線(xiàn)都已確定，繼續(xù)執(zhí)行第7步，否則選定下一個(gè)未被確定區(qū)域內(nèi)路線(xiàn)的劃分區(qū)域，繼續(xù)執(zhí)行第4步。第7步：選定2個(gè)相連的區(qū)域B1和B2，且路徑順序中B1在B2之前，如果B1中存在另一出口，使得從B1內(nèi)部終點(diǎn)到B2內(nèi)部起點(diǎn)的路線(xiàn)長(zhǎng)度更短，則B1中的出口被更新，B2入口也用同樣的方法確定其是否需要更新。第8步：若所有的出入口都已更新，則算法結(jié)束，否則繼續(xù)執(zhí)行第7步。

5 討論

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

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

[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] 謝建國(guó)，姜靈敏，陳松喬.VBR流式視頻的最短路徑率平滑傳輸算法[J].計(jì)算機(jī)學(xué)報(bào)，2004，27（3）：357.

[7] 劉耀林，范延平.最短路徑方法在土地定級(jí)中的應(yīng)用[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào)，2000，25（6）：510.

[8] 黃賢英，李玉桃，張本強(qiáng).最短路徑搜索算法在高速公路收費(fèi)系統(tǒng)中的應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)，2007，21（3）：44.

[9] 特日根，孫永雄，李雄飛，等.基于概率的增強(qiáng)型區(qū)分服務(wù)算法[J].計(jì)算機(jī)工程，2011，37（21）：71.

[11] 王立鑫，負(fù) 超，吳平龍，等.智能藥房中最小代價(jià)取藥原理算法及實(shí)現(xiàn)[J].計(jì)算機(jī)測(cè)量與控制，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）